Yippee Ki-Yay, All the Functors!

More information on functors than you probably ever wanted, with all sorts of weird and wonderful examples.

Hullo! I hope you’ve all been finding a pleasant way to see out 2016. To add just a touch more to the merriment, let’s talk about functors!

What the Functor?

Let’s go over the map method for arrays, starting with a little curried function to help us out (I’ve written a blog post about currying if you’re unsure about it):

// map :: (a -> b) -> Array a -> Array b
const map = f => U => U.map(f)

So, we pass in a function (from some type a to some type b) and an array of type a, and get back an array of type b. Nothing scary, and we might notice:

• The identity function, id = x => x, has no effect when we map over an array. In other words, map(id) is exactly equal to id!

• If we define compose = (f, g) => x => f(g(x)), we can say that compose(map(f), map(g)) is no different to map(compose(f, g)).

compose(f, g)(x) basically means, “run g on x, then run f on the result”, so we can build up pipelines. Think of the shell pipe, |!

In formal language, we call these properties identity and composition, respectively. Take some time to convince yourself that these laws make sense for arrays - particularly the second one:

const compose = (f, g) => x => f(g(x))
const data = ['i', 'am', 'tom']

// Try them out - both should equal [2, 4, 6]!
compose(map(x => x * 2), map(x => x.length))(data)
map(compose(x => x * 2,      x => x.length))(data)

This actually gives us a cool property called loop fusion: any two neighbouring map calls can be combined into one, meaning we don’t have to loop over the data structure twice! In plain English (sort of), map f THEN map g is the same as map (f THEN g) .

By this point, we should be confident that arrays are structures with a map method that respect the identity and composition properties. Well, are there any other structures that do this? No prizes for guessing what we call them… Let’s update that type signature for map:

// map :: Functor f => (a -> b) -> f a -> f b
const map = f => U => U.map(f)

Instead of saying Array explicitly, we now just use any functor f. So, to prove that Array isn’t the only functor, let’s take a look at some favourites!

Identity

This is probably the easiest functor of them all.

const Identity = x => ({
  // Transform the inner value
  // map :: Identity a ~> (a -> b) -> Identity b
  map: f => Identity(f(x)),

  // Get the inner value
  // fold :: Identity a ~> (a -> b) -> b
  fold: f => f(x)
})

The value on the left of the squiggly arrow is how we’ll refer to the object with the method we’re using. Ignore the fold - it’s just there to give us a way to get the value out!

Does this satisfy identity? Let’s see:

Identity(X).map(id)

  // By definition of `map`
  === Identity(id(X))

  // By definition of `id`
  === Identity(X)

Yep! For any X, given that id just returns what it is given, we can see that Identity satisfies identity. Probably how it got its name, really. How about composition?

Identity(X).map(g).map(f)

  // By definition of `map`
  === Identity(g(X)).map(f)

  // By definition of `map`
  === Identity(f(g(X)))

  // By definition of `compose`
  === Identity(compose(f, g)(X))

  // By definition of `map`
  === Identity(X).map(compose(f, g))

We can see, just by swapping around sides of our definitions, that the two sides of composition are equivalent. Yay! So, we have map, identity, and composition, but it’s not really… useful, is it? Let’s look at something with more obvious utility:

Maybe

There are two constructors for Maybe: Just and Nothing. If you’re unfamiliar with type constructors: Bool has constructors True and False, String has constructors… well, every possible string! The point is that, for a given type, all its constructors have the same interface, albeit with different behaviours.

const Just = x => ({
  // Transform the inner value
  // map :: Maybe a ~> (a -> b) -> Maybe b
  map: f => Just(f(x)),

  // Get the inner value
  // fold :: Maybe a ~> (b, a -> b) -> b
  fold: (_, f) => f(x)
})

const Nothing = ({
  // Do nothing
  // map :: Maybe a ~> (a -> b) -> Maybe b
  map: f => Nothing,

  // Return the default value
  // fold :: Maybe a ~> (b, a -> b) -> b
  fold: (d, _) => d
})

We can see that, apart from an ignored value in fold, Just is the Identity functor with a different name!

Nothing, however, is a bit more interesting. If we map over it, nothing happens. If we fold a Nothing, we get the value that Just ignores (d is short for default; can you see why?)

Why would we ever want this? Well, let’s say you have the following:

const getLight = i => ['Red', 'Amber', 'Green'][i]
const choice = getLight(someUserInput)

console.log(
  choice == undefined
    ? 'Invalid choice!'
    : 'The light is ' + choice.toUpperCase()
)

This is a fairly simple program, but there is already some mess here. Because getLight might return undefined, we have to check for this before we do anything. That means we have to store it in some variable, and our program flow isn’t just top-to-bottom. Can Maybe help us out?

// A little helper method that we'll see a lot...
// fromNullable :: ?a -> Maybe a
const fromNullable = x =>
  x != null ? Just(x) : Nothing

// This now returns a Maybe
// getLight :: Int -> Maybe String
const getLight = i => fromNullable(
  ['Red', 'Amber', 'Green'][i]
)

console.log(
  getLight(someUserInputFromSomewhere)
    .map(x => x.toUpperCase())
    .map(x => 'The light is ' + x)
    .fold('Invalid choice!', id)
)

I’ll use the ?a style to mean “possibly null”.

What have we gained here? Well, for a start, we’ve used map to describe our algorithm step-by-step, which tidies up the logic. Secondly, we don’t have to save the getLight call result because we’re only using it once. Thirdly, and most importantly, we explicitly deal with the null - we can’t forget about it!

This means that we write our program as if it works, and then deal with possible failure at the end. Our program isn’t littered with if checks for undefined; just one branch at the fold step. If we want to add more logic, we simply add more map steps!

How about those laws? Well, we know Just satisfies them, because it’s pretty much the same as Identity! But how about Nothing? If we map over Nothing, nothing happens. That means mapping with id does nothing (which means identity holds), and mapping twice over nothing still does nothing, which means composition holds!

Either

We’ll fly through this one! An Either is a Left or a Right:

const Right = x => ({
  // Transform the inner value
  // map :: Either a b ~> (b -> c) -> Either a c
  map: f => Right(f(x)),

  // Get the value with the right-hand function
  // fold :: Either a b ~> (a -> c, b -> c) -> c
  fold: (_, r) => r(x)
})

const Left = x => ({
  // Do nothing
  // map :: Either a b ~> (b -> c) -> Either a c
  map: f => Left(x),

  // Get the value with the left-hand function
  // fold :: Either a b ~> (a -> c, b -> c) -> c
  fold: (l, _) => l(x)
})

Note that we talked about Array a, Identity a, and Maybe a, but we’re now talking about Either a b. That’s because, whereas the others could (should) only hold one type, Either can hold two: the Left and Right branches can have different types!

We can immediately see that our Right looks almost identical to Just! The Left, however, is slightly different to Nothing. Whereas Nothing held no value, Left actually holds something. Still, when we map over a Left, the value is unchanged. Let’s modify our traffic light example to use Either:

// Now, we provide a "default" for null values
// fromNullable :: (a, ?b) -> Either a b
const fromNullable = (d, x) =>
  x != null ? Right(x) : Left(d)

// getLight :: Int -> Either String String
const getLight = i => fromNullable(
  i + ' is not a valid choice!',
  ['Red', 'Amber', 'Green'][i]
)

console.log(
  getLight(someUserInput)
    .map(x => x.toUpperCase())
    .map(x => 'The light is ' + x)
    .fold(
      e => 'ERROR: ' + e,
      s => 'SUCCESS: ' + s
    )
)

See how our fold step takes a function for each of the possible constructors to handle their individual values, so we can handle them separately. The map functions don’t touch the Left value at all, though.

See how the signature for the map implementations take Either a b to Either a c? If a map takes f b to f c, that means our functor must be Either a!

If Maybe helps us deal with null safely, what does Either deal with? Perhaps this function will help us see:

// tryCatch :: (* -> a) -> Either Error a
const tryCatch = f => {
  try {
    return Right(f())
  } catch (e) {
    return Left(e)
  }
}

Either models type-safe exceptions! At the fold step, we’re forced to deal with the “exception” by supplying a function for the Left value. If the original function does return a Left, that value can leap-frog over the rest of the map calls!

We’ll see how Either is actually more powerful than exceptions when we come to bifunctors and other concepts. For now, though, this is a pretty neat start.

Are the laws satisfied? I’ll leave that as an exercise!

Function

There are plenty of other examples, why don’t we end mind-bender? Functions are functors. Let’s look again at that type:

map :: Functor f => (a -> b) -> f a -> f b

Now, bear with me. Our Either a type was a functor because we could map over b (to get Either a b to Either a c). Our functions are a -> b; can we map over b to get a -> c?

// (a -> b) ~> (b -> c) -> a -> c
Function.prototype.map = function (that) {
  return x => that(this(x))
}

Yes, omgwtf, we can write a map implementation. Does it satisfy identity?

f.map(id)

  // By definition function's `map`
  === x => id(f(x))

  // By definition of `id`
  === x => f(x)

  // We're there!
  === f

Yes. OMGwtf. What about composition? Brace yourself:

compose(map(h), map(g))(f)

  // By composition's definition
  === map(h)(map(g)(f))

  // By map's definition
  === (map(g)(f)).map(h)

  // ... and again...
  === f.map(g).map(h)

  // By function's map definition
  === (x => g(f(x))).map(h)

  // ... and again... eep...
  === y => h((x => g(f(x)))(y))

  // Applying y to (x => g(f(x)))...
  === y => h(g(f(y)))

  // By composition's definition...
  === y => compose(h, g)(f(y))

  // By function's map definition...
  === (y => f(y)).map(compose(h, g))

  // YAY!
  === f.map(compose(h, g))

It’s a pretty big and ugly proof, but we can indeed see that composition holds. The question remains, though: why would we ever want this? Well, why would we ever want map? To build up processing pipelines!

const toUpper = x => x.toUpperCase()
const exclaim = x => x + '!'
const greet   = x => 'Hello, ' + x
const log     = console.log.bind(console)

// Ok, cheating a little bit...
const getUserInput = () => 'Tom'

const myProgram =
  getUserInput
    .map(greet)
    .map(exclaim)
    .map(toUpper)
    .map(log)

myProgram() // logs "HELLO, TOM!"

Mapping over functions lets us compose big processes from small building blocks. This gives us some wonderful opportunities for code reuse and simplified testing: many functions can be simplified to this style, and then we can reuse the code they have in common without duplication.

Less duplication obviously means less code means less to test! Everyone wins :)

Well, sorry if that’s an awful lot to take in! In summary, functors are probably one of the most simple types of structure (we call these types typeclasses) that you’ll see regularly in FP, but you can hopefully already see their power. Imagine what we could do with a bit more freedom? We’ll find out when we talk about applicatives.

Until then, have a wonderful new year!

Enjoy yourself, and take care ♥