Saturday, August 29, 2015

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


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.


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.


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.


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