MapFold OR Set Phasers to Fun

"Back to our brother of England."
-- Shakespeare, Henry V
Act II, Scene IV, Line 115.1

One of the things I love about functional programming is you can tell a lot about how a function works by just looking at its type signature.  In F# 4.0 there is a new function to work with collections, here is it type signature:

('State -> 'T -> 'U * 'State) -> 'State -> C<'T> -> C<'U> * 'State

What do you think it does?

That's right this is a MapFold.  Looking at its full definition we see the following:

let mapFold<'T,'State,'Result> 
  (f:'State -> 'T -> 'Result * 'State) acc list =

How does this work?

Looking at F#'s unit tests we see the following test name:

let ``mapFold works like map + fold`` () =

MapFold works like a map with a fold to maintain state.  I know what you are thinking maintaining state is bad, that's why functional programming is easier to reason about.  This is very true, but this is not a mutable state, this is an evolving state.

Let us look at an example, the Coin Changer kata:



The Coin Changer kata simulates one of those machines which give you back coins at a store.  It takes a list of coin values and the amount of change to be given.

The Coin Changer kata is interesting since it has two things going on at the same time: 1) state and 2) list processing.  In the Coin Changer kata you must maintain the amount of change you have left to give along with the amount of each coin to be given back.  An example would be 99 cents with an US register, you would get back 3 quarters, 2 dimes, 0 nickels, and 4 pennies.

How would this example of 99 cents with an US register work with MapFold?

changeFor [25; 10; 5; 1] 99

We'll use s to hold the state, r to hold the result, and x to hold the current coin value we are looking at .

Processing the first value: x = 25, s = 99, r = [] resulting in s = 24, r = [3]
Second value: x = 10, s = 24, r = [3] resulting in s = 4, r = [3; 2]
Third: x = 5, s = 4, r = [3; 2] resulting in s = 4, r = [3; 2; 0]
Last: x = 1, s = 4, r = [3; 2; 0] resulting in s = 0, r = [3; 2; 0; 4]

There you have it, step-by-step through the Coin Changer kata using MapFold.

Guess what the source code to MapFold looks for the most part like what we just experienced.  Here it is:



We see that it loops through each member of the collection, applying the function given against the state and current member.  Once there are no more members it returns a tuple of the result along with the state.  For the Coin Changer kata we do not care about the state (maybe we could use it verify that we have 0 cents) so we just drop it and get the result using fst.

There you have it the Coin Changer kata and MapFold seem to be made for each other.

Data Structures Matters

"I see thee yet, in form as palpable"
-- Shakespeare, Macbeth
Act II, Scene I, Line 31 

One of the katas we like to use at work while interviewing candidates is the Roman Numeral kata.  It is a simple kata in which you create a function which takes an integer and gives you back a string representing the roman numeral representation of the number.  It is fairly simple to explain but is deep enough to get a good idea of how the person works.

Here is a possible solution to the Roman Numeral kata in C#.



Looking at this solution we see a few things.  The solution is using C# 6.0 syntax but beyond that we see three major things.

1. translation are being applied using the higher order function Fold (in C# Aggregate)
2. mutation of the input value is used to maintain state through iterations
3. translations are held in a Dictionary

Let us look at the Dictionary data structure which is the main focus of this post.  In general a Dictionary is not ordered, now some implementations are ordered in the order in which the key value pairs are inserted (this is the case with the C# implementation), but this is not a property of the Dictionary data structure (see also the NIST entry).

Here is a possible solution to the Roman Numeral kata in Clojure.

Looking at this solution we see a few things.

1. translations are being applied using the higher order function Fold (in Clojure reduce) 
2. hash maps are used to maintain state through iterations
3. translations are held in a vector of vectors

We see that we cannot use a Dictionary (called maps in Clojure) to hold the translation.  Clojure's HashMap uses Phil Bagwell's Hash Array Mapped Trie which makes no claim about order, in fact we see that maps (and sets) are unordered while vectors (lists and seq) are ordered.  Since our algorithm requires that the translations be in the order we insert them we must use a data structure which preserves this order.  Thus we must used something that is ordered like a vector.

How about F#?  Here is a possible solution to the Roman Numeral kata in F#.

Looking at this solution we see a few things.

1. translations are being applied using the higher order function Fold (using F#'s List.fold)
2. tuples are used to maintain state through iterations
3. translations are held in a List

For the same reasons that we found in the Clojure solution we cannot use a Dictionary (called a Map in F#) since they are ordered by F#'s generic comparison and not in the ordered in which they were inserted.  Luckily we can use a List which is ordered.

There you have it, the Roman Numeral kata in three different languages.  Despite being a simple kata we have learned something about the Dictionary data structure, mainly that it does not have an order and thus should not be used in cases in which order matters.

On the Fusion Property of Fold

"If I break time, or flinch in property"
-- Shakespeare, All's Well That Ends Well
Act II, Scene I, Line 187

In Dr. Hutton's excellent paper, "A tutorial on the universality and expressiveness of fold", he gives the following definition of the fusion property of Fold:

h · fold g w = fold f v

Great, but what does this mean to me?  Well if we go on in the paper we find the following application of the fusion property of Fold:

(+1) · sum = fold (+) 1

Interesting, we see that adding 1 to the sum (defined as, fold (+) 0) of a collection is the same as folding over that collection with 1 as the seed value.  Further down in the paper we see that we can simplify and generalize the application above as:

(⊕ a) · fold (⊕) b = fold (⊕) (b ⊕ a)

Now this is really cool.  We can apply an associative binary operation with a value against the results of folding that operation against a collection is the same as applying that binary operation with a value against the seed.

As an aside, an associative binary operation is an operation which takes two values from the same type and outputs a value of that type, examples would be +, -, *, /, min, max, ...  We say an operation is associative if and only if:

a ⊕ b = b ⊕ a

This means addition is associative while subtraction is not (2 - 1 != 1 - 2, but 2 + 1 = 1 + 2).

How about looking at some examples of the fusion property?

First we'll look at examples in Clojure.



We see in the Clojure example that we are using reduce to fold over a collection of integers (integers are easier to use in examples but this idea is not limited to integers) applying an associative binary operation against each member.  We see that applying the operation with a value against the result is the same as applying that operation and value against the seed.

Next we'll look at examples in ECMAScript 2015 (JavaScript) using Immutable.js.



We see in the ECMAScript example that we are using Immutable's reduce to fold over a List of integers (again this could be applied against any type) applying the associative binary operation against the members.  Like the Clojure example we see that applying the operation with a value against the result is the same as applying that operation and value against the seed.

We can go further with this idea but I feel this is a good overview of the concept.

Folding Up the Coin Changer Kata

"Whate'er the course, the end is the renown."
-- Shakespeare, All's Well That Ends Well
Act IV Scene IV, Line 36

Coin Changer Kata

The Coin Changer kata has three things which make it a good kata.

1. easy to understand
2. rich set of features
3. lots of realistic possible implementations

Even in today's cashless society, most people understand the idea of handing someone over some money and get change back.  This handing back of change requires the breaking down of the change over coins of different denominations.  Finding which coins to hand back has lots of possible implementations which translate over to things which programmers do every day.

The user story is very simple:

Given a collection of coins of different denominational value
When an amount of change is given
Then it will give back the number of coins for each denomination needed using the least amount of coins possible

A type signature for the function needed could look like the following:

changeFor(coins: int[], amount: int): int[]

We are expecting an array of integers which have different denomination of coins (in the US something like: [25, 10, 5, 1]) and the amount of change needed (something like: 99) giving a resulting array of integers showing how many of each denomination (something like: [3, 2, 0, 4]).

What would we need to be able to do this kata using just Fold?

We'll need to use a tuple (or something like one) to manage the state of the amount of change needed and the resulting array of integers.

Now lets look at an example using a typical full US register with quarters, dimes, nickels, and pennies.  We'll look at getting change for 99 cents.

First Memorize has (99, empty) and X has 25 giving the result of (24, [3]).

Next Memorize has (24, [3]) and X has 10 giving the result of (4, [3, 2]).

Then Memorize has (4, [3, 2]) and X has 5 giving the result of (4, [3, 2, 0]).

Last Memorize has (4, [3, 2, 0]) and X has 1 giving the result of (0, [3, 2, 0, 4]).

Finally obtaining the tuple item with the resulting array of integers to get the change.

Clojure

We see with the Clojure code that we seed with a map with a key for the :amount and one for the :result.  We fold over the coins using reduce destructing the memoize value into the amount and result.  We then just calculate the new amount using: amount % coin, follow by inserting the number of coins we get using: amount / coin.  We use cons to show off the coolness that is the thread-last macro (at least that is why I think I coded it this way, it was a little bit ago that I did the gist and I cannot remember why I code with cons over conj).

C#

We see with the C# code that we seed using a Tuple (which I think has very ugly syntax in C#).  We then fold over the coins using aggregate just like the Clojure code above.  We calculate the changer results and place them into a new Tuple which we return as the memoize.

ECMAScript 2015

In this ECAMScript 2015 example we use lodash's foldl to fold over the coins just like the two examples above.  The seed value is a simple JavaScript object with the members of amount and result given.  We are a bit dirty and mutate the memoize on each call with the changer results but we could argue that this is still "pure" since the mutation happens to an item which is created and used only in side the function.

ECMAScript 2015 and Immutable.js

Last we look at Facebook's open source Immutable.js.  We create an immutable List with the coins which we use to fold over the values using reduce.  The seed value we give it is a simple JavaScript array with an immutable List to hold the results and the amount passed in.  We could use an immutable Map if we wanted to keep it purely immutable.  Like this:



I am not a huge fan of stringly typed accessors, but I understand why they use them.  Both ways are good and would really come down to to performance and readability.

The End

Thus ends our tour of All You Need is Fold, but this is not the end of the uses of Fold, for Fold is universal.

Folding into Map

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

Map

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.

Clojure

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.

C#

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.

Displanting a Function OR Folding a Reverse

"Displant a town, reverse a prince's doom"
-- Shakespeare, Romeo and Juliet
Act III, Scene III, Line 60

Reverse

The interesting thing about the Reverse function is that it is not really doing anything.  With a small clerical error in a visit and recombine function you have reverse.

In Dr. Hutton's excellent paper, "A tutorial on the universality and expressiveness of fold", the following definition is given for reversing:

reverse :: [α] → [α]
reverse = fold (λx xs → xs ++ [x]) [ ]

We see that we concat the memoize with the member, in that order, thus reversing the collection.

Since I like advertising myself, let us go through an example with my name (someone has to advertise for me).

First time the Memoize has nothing and X has M.

Second time the Memoize has M and X is i.

Third time Memoize has i and M and X has k.

Fourth time Memoize has k, i, and M while X has e.

Leaving us with ekiM.

Let us look at some code examples.

Clojure

We see with the Clojure code we are using the cons function to place the current member in the front of the memoize.  We do this for the whole collection thus giving us the collection in reverse.

C#

With the C# code we see that we need to create something to contain the resulting collection, in this case we'll create a List.  We create the reversed collection in an immutable way by creating a new List every time in the lambda.

ECMAScript 2015

With JavaScript (ECMAScript 2015) we us the unshift method on the array.  Since unshift returns the length of the array after the member is added to the head of the array (which I totally did not expect) we need to manually return the memoize after applying unshift.

Fin

There you have it again, yet another function which can be created using Fold.  Showing once again that all you need is Fold.

Think About Length OR How Fold Can Do Everything, Even Count

"Leave nothing out for length, and make us think"
-- Shakespeare, Coriolanus
Act II, Scene II, Line 47

How Long is It?

I am not sure why but before I start reading a chapter or watching something I've recorded I almost always check to see how long it is.  Today's post will be using Fold to find the length of a collection.  In Dr. Hutton's excellent paper, "A tutorial on the universality and expressiveness of fold", the following definition is given for finding the length:

length :: [α] → Int
length = fold (λx n → 1 + n) 0

We see with this definition we do nothing with the current member of the collection (x above) and instead only act on the memoize (n above).

In the simple example below we will see that the string "Mike" has 4 characters in it.

At the start we have a Seed of 0 and a collection with the members M, i, k, and e.

First time Memoize has 0 in it and X has M.

Second time Memoize has 1 in it and X has i.

Third time Memoize has 2 in it and X has the letter k.

Last time Memoize has 3 and X has e.

There you have it (maybe I should have used my sister Kim name instead).  Let us see some code.

Clojure

We see in the clojure example that function we give the reduce must have two parameters, so we call the second one _ to denote that it is not used.

C#

With the C# code the lambda we give Aggregate has two values of which we give the second one the name of _ to denote not using it.

JavaScript (ECMAScript 2015)

With ECMAScript 2015 we use lodash's foldl and see that the lambda only has to have one value which is the memoize.

Fin

There you have it counting with Fold, showing that you need is Fold.

If True or False I Know Not

"I idly heard; if true or false I know not."

-- Shakespeare, King John
Act IV, Scene II, Line 124

Welcome Back

This is the next in the series of post on Dr. Graham Hutton's excellent paper, "A tutorial on the universality and expressiveness of fold", this time around we'll look at Oring.  Dr. Hutton has given Oring the following definition:

or :: [Bool] → Bool
or = fold (∨) False

The idea is that we Fold an Or function with a seed value of False.  If one of the members of the collection is True we Or it with False giving us True, else if none of the members of the collection are True we will end up with the value of False.

In the simple example below we'll see that if we have a single value of True then the end result will be True.

At the start we have a Seed value of False with collection containing False, True, and False.

First time the Memorize has False and X has False.

Second time the Memorize has False and X has True.

Third time the Memorize has True and X has False giving use the finally value of True.

Let us now look at this in sweet, sweet code.

Clojure

In the Clojure code that we use the or macro and a seed value of false in order to create an Oring function using the higher order function of reduce.  Since reduce is expecting a function and not a macro we need to create a lambda function to wrap the or macro.

C#

We see in the C# code that we can use the LINQ aggregate method on the collection we are folding.  We give the aggregate a seed value of false and in the lambda we simply takes the memorize and the current member and or them.

JavaScript (ECMAScript 2015)

Using lodash's foldl function along with Babel.js we are able to create an Oring function by folding over the collection and passing it to a lambda function which ors the current member of the collection with the memorize value.  We give a seed value of false thus causing the initial value of the memorize to be false.

Until Next Time

There you have it an Oring function using nothing but Fold.  Thus "proving" that all you need is Fold.

Approaching the Fold

"Approach the fold and cull th' infected forth"
-- Shakespeare, Timon of Athens
Act V, Scene IV, Line 43

Welcome

In Graham Hutton's excellent paper, "A tutorial on the universality and expressiveness of fold", the first function that is looked at is And.  Dr. Hutton gives And the following definition:

and :: [Bool] → Bool
and = fold (∧) True

The idea being that we give Fold an And function with a seed value of True.  If one of the members of the collection given is False the Anding it with True will yield a value of False and thus the end result will be False.  If no member of the collection given is False then the end result will be True.

Let us look at this in code.

Clojure

To create an Anding function we'll use reduce along with the and macro with a seed of true.  Since and is a macro, we'll need to wrap it in a function in order to be able to use it in reduce.

C#

We'll use the LINQ function Aggregate along && and a value of true to create an Anding function.

JavaScript

We see that by using lodash's foldl function with && and the value true we can create an Anding function.

ECMAScript 2015

Since we live in the future, we'll use Babel to allow us to use ECMAScript 2015.  We see again that by using lodash's foldl with && along with the value true we now have an Anding function.

Fin

There you have it the And function using Fold, showing once again that all you need is Fold.

Intro to Higher Order Functions

"Plucking the grass to know where sits the wind"
-- Shakespeare, The Merchant of Venice
Act I, Scene I, Line 19

Intro

Step on up.  Come one, come all. See the amazing function which produces other functions.  See the marvelous function which consumes other functions.  See things which you will tell your grandkids about.

Functions Producing Functions

Our first sight is the amazing function which produces other functions.

In JavaScript and Clojure we would have the following:



We see in repl.js that we are having a return b which returns the string 'Bilbo'.  Likewise in repl_es6.js we see the first lambda return another lambda which returns the string 'Bilbo'.  In repl.clj we see the function a returns the function b which returns the string "Bilbo".  Three examples of a function producing another function.

Functions Consuming Functions

Our next sight is a function which consumes another function.

In JavaScript and Clojure we would have the following:



We see in repl.js that we are having function a consume function b which when invoked returns the string 'Bilbo'.  Likewise in repl_es6.js we see the first lambda consumes the lambda passed in which when invoked returns the string 'Bilbo'.  In repl.clj we see the function a consumes the function b which when invoked returns the string "Bilbo".  Three examples of a function consuming another function.

Pluck

The next sight we see Pluck taking apart a dwarf.

In JavaScript and Clojure we would have the following:



We see in repl.js and repl_es6.js we can use lodash's Pluck function extract the name property from our dwarves.  Likewise in repl.clj we can use the Map function with the :name keyword to extract the name value form our dwarves.

Reduce

This last sight to see is a function which will Reduce its input to a single value.

In JavaScript and Clojure we would have the following:



In repl.js and repl_es6.js we can use lodash's Reduce / Foldl function to sum up the values of 1, 2, 3, and 4 to get the value of 10, we can leave out the seed value and still get 10, or we can use a seed value of 100 to get 110.  Likewise in repl.clj we can use the Reduce function to sum up the values of 1, 2, 3, and 4 to get again 10, we can also not give a seed value or given it a different value just as before.

Fin

Thank you and watch your step on the way out.

Roman Numeral Kata in One Line with C#

"When in one line two crafts directly meet."
-- Shakespeare, Hamlet
Act III, Scene IV, Line 211

The idea of the Roman Numeral kata is that given a number between 1 and we'll say 4999, the number will be converted into the Roman numeral form.

f(1) = "I"
f(2) = "II"
f(3) = "III"
f(4) = "IV"
f(5) = "V"
...
f(4999) = "MMMMCMXCIX"

You can test a value using Google's search by typing the number and "to roman".  Try searching for "299 to roman" to test it out.

At work, we have been using the Roman Numeral kata for interviewing candidates.  The idea is that we get an idea of what it is like to work with the person and they get an idea of what it is like to work with us.  As an added bonus there is a good chance that we will learn something new from each other in the process.

On one such interview recently, we had a candidate do something rather interesting.  Typically a candidate will just start with a series of if statements, some candidates will replace the ifs with an associative data structure (called dictionary in C#), but most will not.  This candidate did a transformation of the input into a string of "I"s and then replace those with the Roman numeral.  They did not ended up finishing or even coming to a general pattern, but I found this idea interesting and ran with it coming up with a C# one liner.



We see in the code above a few different things.

To make this a REPL one liner we create a Func which takes an integer and returns a string, we then start the lambda expression with the bond variable of number.  (In the refactoring done on the candidates code this was all in a single return statement in a method not a Func variable, but when I redid it for this post I did it on the Mono REPL as a Func variable.)

Func<int, string> toRoman = (number) =>

After that we have our associative array, which allows us to look up each of the transformation that we will be doing, this is very useful since to add another transformation we just need to add an entry to the associative array.  (I've done this kind of thing in real world application but I normally will make the look up be a private member of the class.)

new Dictionary<int, string>


{


{1000,  "M"},


{ 900, "CM"},


{ 500,  "D"},


{ 400, "CD"},


{ 100,  "C"},


{  90, "XC"},


{  50,  "L"},


{  40, "XL"},


{  10,  "X"},


{   9, "IX"},


{   5,  "V"},


{   4, "IV"},


{   1,  "I"}


}

**Note, you do not need the "I" entry in the associative array do the the seed value of the fold, but we'll leave it in there since it is from the more general way of doing this kata.**

We then take this and run it through a fold (called Aggregate in C#).

.Aggregate(

In the seed value to the Aggregate we create a transformation string of the "I"s equal to the value given by the caller.

t(1) = "I"
t(2) = "II"
t(3) = "III"
t(4) = "IIII"
...
t(20) = "IIIIIIIIIIIIIIIIIIII"

To do this we use the string constructor that takes a character and the number of times you wish that character to repeat.

new string('I', number),

We then have the lambda of the Aggregate in which we simply take the current Key and Value from the associative array and call Replace on the transformed string replacing the number of "I"s given in the Value with the Roman numeral given in the Key.

(m, _) => m.Replace(new string('I', _.Key), _.Value));

This is not the "best" implementation of the Roman Numeral kata, but it is a one liner!



"The one I'll slay; the other slayeth me."
-- Shakespeare, A Midsummer Night's Dream

Act II, Scene I, Line 190

Reducing Filter to Reduce OR All You Need is Fold

"All springs reduce their currents to mine eyes"
-- Shakespeare, Richard III
Act II, Scene II, Line 68

Intro

Last time we look at using the ideas presented in Graham Hutton's paper "A tutorial on the universality and expressiveness of fold" around mapping map to a fold.  This post will look at filtering filter down to a fold.

Filter

Filter goes by many different names, to those who speak Clojure, Haskell, and Underscore.js it is called Filter, to others that speak C# it is know as Where, while those that speak C++ know it as Remove, ... we could go on like this for a bit.

The point is that this is the same idea called by different names.  With a Filter what you are doing is taking a collection and applying a predict which state which members of the collection to let into the resulting collection and which members to not allow.  Think of it as a bouncer at a club, some of the people looking to get in will be admitted to the club others will be turned away, the bouncer is the predict, the people are the collection, and those few that get into the club are the resulting collection.

An easy example is to filter out all members of a collection of integers which are not odd.  In Clojure and C# we could use the following code to do this.



We see in both languages that we can use a higher order function to filter our collection down to the resulting collection with the property of oddness that we are looking for.  Clojure has a built in predicate function to check for oddness of a number while in C# we have to roll our own with a lambda function.

Fold

We talk about Fold last time, but we'll review it really quick.

When we are talking about Fold we are talking about taking a collection and applying a function against each member of the collection resulting in a result of a single "value".

Hmm, this sounds kind of similar to what we are doing with Filter...

Folding Filter into a Fold

When we looked at Filter we saw some similarities to Fold.

1. apply a function to each member of a collection
2. building a result

In fact we could look at Filter in the following way:

If we take a Fold (aka Reduce), a predicate function, and a collection to hold the resulting collection, we end up with a Filter.  We can looking at the following examples in Clojure and C# using our friend isOdd with a Fold to produce a Filter



In the Clojure code we see that we have a predicate function testing if a value is odd and if it is we conj it to a memorized resulting collection else we just pass along the memorized result collection.  We seed the Reduce (aka Fold) with an empty vector was is used to hold the memorized result collection.  Note, the memorized result collection is %1 in the lambda function while the current member we are looking at is %2, this pattern is typical in Folds across different languages (I cannot think of one which does not have this as the order, but maybe one exist).

In the C# code we new up a List to hold our resulting collection and in our lambda we test the current member we are looking at, if it passes we add it to the memorized result collection, then we always pass the memorized result collection along to the next call of Aggregate (aka Fold).  Since we had an array of integers as our input, we need to reshape the result collection with a call to ToArray.

By looking at this simple example we see that all we really need is Fold.  :)

Reducing Map to Reduce OR All You Need is Fold

"That would reduce these bloody days again"
-- 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.

1. applying a function against each member of a collection
2. 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.  :)