Sunday, November 17, 2013

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!


2 comments:

  1. @Oranadoz tweeted, "Let's not confuse functional programming with lazy evaluation."

    Here's the thing.
    The essence of functional programming is writing and manipulating pure (referentially transparent) functions. That is, functions without side effects. Functions that have no impact on the rest of the world.
    What follows from this is: the order of evaluation of the functions does not matter.
    What follows from that is: we can separate the construction of a calculation from its carrying-out.
    That leads to the possibility of lazy evaluation. Of storing functions up to execute at whatever point of time is convenient, because the creator of the functions doesn't care about the order, because the order of execution is invisible from outside the abstraction, because there are no effects on the outside world.

    Therefore, lazy evaluation makes sense because functional programming.
    And lazy evaluation is one aspect of the un-ordering of functional programming, the decoupling from lifelike timelines. In imperative programming we execute functions, we specify the order by gluing our statements to the page from top to bottom. We must retrieve the Order from the database before we can extract the Amount. It feels "duh" because that's how life works. Cause before effect. First this, then that.

    Functional programming drops that restriction. We define operations in terms of their input, then manipulate and compose those operations directly, postponing until some future time the gathering of the input. Our programming style is no longer tied to a straight timeline. Functional programming says "If this, then that." Derive our conclusions without waiting for the premises.

    Lazy evaluation embodies one of the key decouplings that functional programming gives us: separating what to do from when to do it. As such, it is a path to understanding the mental freedom that comes with functional programming.

    Functional programming and lazy evaluation are not the same thing, but they are important to each other.

    ReplyDelete
    Replies
    1. I agree that *pure* functional programming calls for lazy evaluation, but all functional programming languages do not come with lazy evaluation, as they also allow for imperative constructions (e.g. OCaml). They remain functional, even though not pure. In the post, the difference was not that evident and I saw a possible confusion for the reader.

      Delete