Using Numerals to Map Functions to Arguments

The map function is one of the most useful functions in all of functional programming.  Pass a function, a list of arguments, apply the function to each argument, and return a new list of the results.

 

let list = [1;2;3;4;5]

let f1 = (fun a -> a)

let alist = List.map f1 list

 

>[1;2;3;4;5]

 

The map2 function does basically the same thing, except the function takes two arguments, hence we need two lists of arguments.

 

let list = [1;2;3;4;5]

let f2 = (fun a b -> a + b)

let alist2 = List.map2 f2 list list

 

>[2;4;6;8;10]

 

And I bet you can guess what the map3 function does.

 

let list = [1;2;3;4;5]

let f3 = (fun a b c -> a + b + c)

let alist3 = List.map3 f3 list list list

 

>[3;6;9;12;15]

 

But now we’ve got a problem for there is no Map4 function.

 

Extending the Map3 Function

 

The basic idea here is to put an end to the continued definitions of Map functions.  Let’s see if we can “extend” the Map3 function to take one more argument list.  Something like the following would be great.

 

let f4 = (fun a b c d -> a + b + c + d)

let alist4 = List.map3 f4 list list list << list

 

Where the << operator is defined as

 

let rec (<<) f a =

    match f, a with

    | fh :: ft, ah :: at -> fh ah :: (ft << at)

    | _ -> []

 

We pass a list of functions, and the next list of arguments to apply the function to.  For our f4 function we will have already applied f4 for the a b and c arguments by the time we use our << operator.  So after the use of our operator we’re left with

 

>[4;8;12;16;20]

 

And if you think about it, there’s not really any reason for the Map2 or Map3 functions.  Let’s “extend” our Map function for a function requiring 5 bound variables.

 

let f5 = (fun a b c d e -> a + b + c + d + e)

let alist5 = List.map f5 list << list << list << list << list

 

>[5;10;15;20;25]

 

Introducing Parametric Numerals

 

The above use of the << operator is ok.  It solves our problem of having to continually define Map functions, but it’s not very readable.  What if a very complex calculation requires 18 bound variables? Do you really want to count up the instances of << ? And wouldn’t it be great if there was a way to constrain the map function to precisely the number of bound varaibles you require in the first place?

 

Let’s define some parametric numerals.

 

let succ n fl al = n (fl << al)

let zero al = al

let one n a = succ zero n a

let two n a b = succ one n a b

let three n a b c = succ two n a b c

let four n a b c d = succ three n a b c d

let five n a b c d e = succ four n a b c d e

 

And a new map function that can use them.

 

let mapWith n f l = n (List.map f l)

 

Our map function suddenly becomes very readable and constrained to exactly the number of bound variables we require.

 

let blist = mapWith zero f1 list

let blist2 = mapWith one f2 list list

let blist3 = mapWith two f3 list list list

let blist4 = mapWith three f4 list list list list

let blist5 = mapWith four f5 list list list list list

 

The first parameter requires a parametric numeral that states how many additional bound variables our mapWith function requires.

 

let blist5 = mapWith four f5 list list list list list

 

can be read as map with four additional bound variables, if we try to write

 

let blist5 = mapWith four f5 list list list list list list

 

then the compiler catches the error of our ways.  Pretty handy!

 

An Odd Argument Indeed

 

The first argument to our mapWith function really is an odd argument.  Unlike traditional variables, which act as placeholders, it encodes information about how the function should behave.  We’ll take more in depth look at these “odd arguments” next time.

 

The ideas in the blog come from the following paper, which is a pretty easy read.