From lists to trains to functors

The first useful bit of functional programming is the map method on List. It gives us a new List, which contains the results of the mapped function applied to each item in the list. We might think of it like this, mapping f over a List of a single item of type A:

That’s the equivalent of, in Java:

  public static <A, B> List<B> map(List<A> oldList, 
                                   Function<A,B> f) {
    List<B> newList = new LinkedList<B>();
    for(A item: oldList) {
      newList.add(f.apply(item));
    }
    return newList;
  }

Except… that’s a naive picture of what map does. That’s one possible implementation which works for Lists. There are others. Consider a lazy list. The lazy list does not evaluate a mapped function until its result is requested. So what we get is more like this:

From the outside, the two Lists of type B are identical. When you get the values out of the list, they’re the same.

The transformation is encapsulated inside the lazy list. It’s guaranteed to be used before we can see the value from inside, but it doesn’t have to be used immediately.
It’s kind of like, the List holds its value in a train car, and the train car always has a hook to which another train car can attach.

Map hooks the function up like another train car.

When you pull the value out of the train, it passes through all the cars.

The key is: no matter how many cars you hook up, you still have exactly one train. And there’s always a hook at the end that can attach more cars.

This means that a function passed to map doesn’t have to be applied immediately. The list implementation can hook it up and save it for later. This kind of temporal distortion, of “you told me what to do, and I’ll do it when I’m good and ready” is part of the power and mystery of functional programming. It gets more magical in places other than list. Consider Future.

Future represents a value that we might not have yet. Maybe it’s being fetched by a process on another thread. It’s a container like List, except that it might not have that original value yet. Future has a map method just like list, and we can hook up functions like train cars in the same way.
Perhaps your Future is waiting for something to retrieve an Order from the database, and what you really care about is the total amount of the order. You can hook up a train car for that.

Here’s the Future waiting for an Order:

Map that across a function to attach a train car. (in Scala)
val extractAmount: Order => Amount = (o: Order) => o.totalAmount
val futureAmount = Future.map(futureOrder, extractAmount)

Now you have a Future waiting for an Amount. After the database-accessing thread finishes its work, the Future will have a value for you, and when you get it out, it passes through all the train cars (all the mapped functions).

This is that time-warping thing again. When we chose to map the Future across the amount-extracting function, that was before there was an Order to extract the amount from. We can specify what to do before we can possibly do it.

If this makes sense, if you can see the commonality and usefulness of hooking up new functions that will transform a value before we can see it, then it’s time to give a name to it: Functor. A functor is any type with a map method that works like this. Whatever sort of value it has for you, or may have later, you can hook up the train cars to transform that value. And what you get back from map is always another of the same kind of Functor, now holding a different type of value. Add all the cars you like, it’s still a train.

Functor. Map over it. Because it always has a hook, ready to attach another train car.
Choo! Choo!