-- Shakespeare, Richard III
Act V, Scene V, Line 36
Intro
Have you heard the tale of the madman who came running into the town late at night, screaming that all you need is fold?
In Graham Hutton's paper "A tutorial on the universality and expressiveness of fold" it is shown that we can reduce recursive functions into a definition using fold. Let's take a look reducing map to a fold.
(O-the tale of the madman is about me and not Dr. Hutton.)
Map
Map goes by a few different names, to those who speak Clojure, Haskell, or Underscore.js it goes by the name Map, to those which speak C# it goes by the name Select, those who speak C++ call it Transform, ... we could go on like this for a bit.
The point is that idea of the higher order function Map goes by different names in different language but performs the same function of taking a collection and applying a function against each member and placing it into the resulting collection.
The easiest example that actual does something is to apply an increment function with a Map. Looking above we see that when we Map the increment function against a collection with the members of 1, 2, 3, 4 we get a resulting collection with the members of 2, 3, 4, 5.
In Clojure and C# it would look like this:
Fold
Fold goes by a few different names too, to those that speak Clojure or Underscore.js it goes by the name Reduce, to those which speak C# it is known as Aggregate, in Haskell it is known as Fold, in C++ it goes by the name Accumulate, ... we could go on like this for a while. Again the point is that these names are all for the same idea of the higher order function Fold.
A Fold takes a collection and applies one function against each member of the collection and an accumulated result (also known as a memorize).
A very simple example of Fold would be summing.
We see in the image above that we are taking the collection 1, 2, 3, 4 and summing it up to the value of 10. We do this by taking member 1 and the seed value of 0 and adding them together to get 1. Next, we take the accumulated value of 1 and add the next member 2 to it giving us 3. Then, we take the accumulated value of 3 and the member 3 add them and get 6. Last, we take the accumulated value of 6 and the member of 4 giving us the final result of 10.
In Clojure and C# this would look like the following:
Mapping Map to Fold
... and birds go tweet, what is the point? Glad you asked, we see with both Map and Fold some similarities.
- applying a function against each member of a collection
- building a resulting collection
Let's look at the first Map example again. We see that we applying a function against each member of a collection and are accumulating a resulting collection, this sounds very similar to Fold.
In fact I would say that if we had an empty collection in which we accumulated the results of applying the function against the members of the collection we would have the same functionality. That was a lot of words lets have some code.
In Clojure and C# we would have the following:
We see that both Map and the Fold give the exact same result. In both the Clojure and C# code we see that we need an initial empty collection to store the resulting collection in and place the result of applying the function against a member into the resulting collection (using conj in Clojure and Add in C#). For the C# code since we are using a List to accumulated the resulting collection instead of an array we need to reshape the resulting collection using the ToArray method.
By looking at this simple example we see that we can reduce Map to a Fold and thus all we need is Fold. :)
