Sunday, April 26, 2009

Applicative functors: mapping a function to more than 3 lists

Hello

Here is a short post that illustrates the power of higher level functions.

Everybody knows the List.map function that applies an arbitrary function to a list, producing a new list.

#light

List.map (fun x -> 2*x) [1;2]
List.map takes a function of one argument but there also exist List.map2 and List.map3 that take, respectively, a function of 2 and 3 arguments.
List.map2(fun x y -> x+y) [1;2] [1;2]

List.map3 (fun x y z -> x+y+z) [1;2] [1;2] [1;2]
But how do we do if we need a function List.map4 or List.map5 ? The straightforward solution is to explicitly write these functions.

I will show that List.map3, List.map4 or even List.map45 are not needed and with the help of a little operator, we can get the same functionality by simple composition.

First, let's try to evaluate the expression:

List.map (fun x y -> x+y) [1;2]
We get the signature:
val it : (int -> int) list
A list of functions. Clearly, if we combined this list with a list of int (i.e. [3;4]) , making sure that each function is applied to its corresponding integer, we could obtain the same result as the expression:
List.map2 (fun x y -> x+y)  [1;2]  [3;4]
That is precisely what the operator <$> below does:
let (<$>) fctList list = List.map2 (fun fct elem -> fct elem) fctList list
Using both List.map and <$>, we can implement any mapping we want. I.e.
let r = List.map (fun x y z -> x+y+z) [1;2] <$> [1;2] <$> [1;2]
is equivalent to
List.map3 (fun x y z -> x+y+z) [1;2] [1;2] [1;2]
We can also, if we want, explicitly define the equivalent of List.map4
let map4 f l1 l2 l3 l4 = List.map f l1 <$> l2 <$> l3 <$> l4
This technique works also for other types than list. It works with sequence, array... In short it works with any type supporting a map like function.

In the litterature (and more specifically in Haskell) all the types that support a mapping function form the class of Functors.

The types that support both a mapping function and the operator <> belong to the class of gt; belong to the class of Applicative Functors.

1 comment:

dimka said...

Simple and elegant