-- 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.
There you have it again, yet another function which can be created using Fold. Showing once again that all you need is Fold.