Abstracting the Map Function

When pitching functional programming to an imperative friend, the “map” function is the canonical example of the obvious advantages of the functional approach.  And once our backwoods imperative friend has begrudgingly accepted “map” as a neat party trick, we can really amaze them by abstracting “map” over any mappable structure.  That is as long as brand of functional magic is something besides F#.

 

A Map over Trees

 

Let’s start with an example from Real World Haskell.

 

type Tree<’a> =

    | Node of (Tree<’a>) * (Tree<’a>)

    | Leaf of ‘a

 

let tree = Node ((Leaf “foo”),(Node((Leaf “x”),(Leaf “quux”))))

 

And we can write a function to calculate the length of the string at each node.

   

let rec tree_lengths = function

    | Leaf s -> Leaf (String.length s)

    | Node (l,r) -> Node (tree_lengths l,tree_lengths r)

 

> tree_lengths tree;;

val it : Tree<int> = Node ((Leaf 3),(Node((Leaf 1),(Leaf 4))))

 

But we prefer to use our party trick wherever we can and so we write.

 

let rec tree_map f tree =

    match tree with

    | Leaf a -> Leaf (f a)

    | Node (l,r) -> Node (tree_map f l,tree_map f r)

 

> tree_map String.length tree;;

val it : Tree<int> = Node ((Leaf 3),(Node((Leaf 1),(Leaf 4))))

 

Then impress them with our combinations.

 

let odd = (fun x -> x % 2 <> 0)

 

> tree_map (odd << String.length) tree;;

val it : Tree<bool> = Node ((Leaf true),(Node((Leaf true),(Leaf false))))

 

And finally define an operator for our tree_map mapping function.

 

let (<$>) f tree = tree_map f tree

 

> String.length <$> tree;;

val it : Tree<int> = Node ((Leaf 3),(Node((Leaf 1),(Leaf 4))))

 

> (odd << String.length) <$> tree;;

val it : Tree<bool> = Node ((Leaf true),(Node((Leaf true),(Leaf false))))

 

A Map over Type<_>

 

Now that we’ve defined a map function for Tree types let’s compare it to our familiar map function over lists.

 

// val tree_map : (’a -> ‘b) -> Tree<’a> -> Tree<’b>  

let rec tree_map f tree =

    match tree with

    | Leaf a -> Leaf (f a)

    | Node (l,r) -> Node (tree_map f l,tree_map f r)

 

// val list_map : (’a -> ‘b) -> List<’a> -> List<’b>

let rec list_map f list =

    match list with

    | [] -> []

    | h::t -> (f h) :: list_map f t

 

In both cases we’re taking a function over ordinary types and lifting it into a function over container types. If a is a Type then our Tree and List types are related in that they are both Type<_>.  And because we prefer to codify the relationship between apparently disparate structures, we write the following map function  

 

// val list_map : (’a -> ‘b) -> Type<’a> -> Type<’b>

let type_map f t =

    match t with

    | :? List<’a> -> list_map f t.a

    | :? Tree<’a> -> tree_map f t.a

 

let (<$>) f t = type_map f t

 

Of course the compiler screams about our attempt to relate trees and lists.  Our type_map function requires 4 concepts the F# compiler does not support.

 

1.    Higher kinded polymorphism

2.    Pattern matching over higher kinds

3.    Static type tests

4.    Polymorphic return types

 

In plain English this means we want the compiler to differentiate between ordinary types and parameterized types, pattern match over parameterized types, provide a standard way to extract the underlying type, catch invalid type tests at compile time instead of runtime, and allow us to return specific instances of Type<_> from a function.

 

Because F# has to use the type system of .Net, I wouldn’t expect any of these any time soon, if ever. 

 

A Connection between Trees and Lists

 

Unfortunately, F# brains will never make the connection between trees and lists. Trees and lists will forever remain separate unrelated concepts.  How important you regard this connection depends on your tolerance for redundant code.  I guess we’ll have to learn to have a high tolerance indeed.