Monday, September 7, 2015

Folding into Map

"I have forgot the map."
-- Shakespeare, Henry IV Part I
Act III, Scene I, Line 5


Map is the first of the big three Higher Order Function we will looking at Folding using Dr. Hutton's excellent paper, "A tutorial on the universality and expressiveness of fold", as a guide.  The idea of a Map is simple, you have a collection which you wish to apply some translation function against every member of the collection.

We can look at a few simple examples, the first of which would be the identity function.

 Next we can look at a constant function which maps turtle for any value given to it.

Last we can look at a function which shifts everything given to it.

All of this these functions have something in common, they all apply a function against every single member of the collection they are given, thus the resulting collection is the exact same size as the collection given to it.

We can now look at how we would implement Map using a Fold.  We see that Dr. Hutton gives Map the following definition:

map :: (α → β) → ([α] → [β])
map f = fold (λx xs → f x : xs) [ ]

Folding a Map we'll need a collection to seed with then we just apply the given function against each member concatenating it with the seed.

(similar to Reverse from last time)

Let us look at an example of upper casing Mike.

First Memoize has nothing and X has M.

Second Memoize has M and X has i.

Third time Memoize has MI and X has k.

Finally Memoize has MIK and X has e.

Giving the final result of MIKE.  Now let us look at some code examples.


In Clojure we use the reduce function to Fold.  We give the reduce a seed of an empty collection and use conj to join applying the function given with the resulting collection.


With C# we use the aggregate LINQ function to Fold.  We give the aggregate a List and add the result of applying each member of the given collection against the function we are mapping with.

ECMAScript 2015

Using ECMAScript 2015 (aka JavaScript), we use lodash's foldl to Fold.  We give the foldl an empty array and push the result of applying the function given against the member we are mapping against.

To End All

There you have it by folding with an empty collection and applying the given function against each member adding the result against the seed and you have a Map.