Sunday, August 23, 2015

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.


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.


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.


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