In this post, I continue going through the famous paper “Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire” by Meijer et al.  They show that we can treat recursions as separate higher order functions known as recursion schemes.  Each of the four things in the paper title corresponds to a type of recursion scheme.  Bananas refer to catamorphisms or folds, which I covered in a few earlier posts.  This time I’m covering lenses, which refer to anamorphisms.

Fold and Unfold

Anamorphisms, also referred to as unfolds, can be thought of as the dual of folds.  As Conal Elliott puts it: while folds contract a structure down to a value, unfolds expand a structure up from a value!

How are they dual to each other?  Folds output a value from a list while unfolds output a list from a value.  They both take a function as an input which describes the fold/unfold process.  In folds, the function is applied to elements of the input list.  The elements are folded into a value as the function applies to each element.  In unfolds, the function is applied to the input value and is unfolded to a whole list.

Both folds and unfolds also take an input that is related to the empty list.  For folds, the base case value is the output when the input list is empty.  For unfold, the predicate describes the condition when the function should return an empty list.  If no predicate is given, what do we get?  That’s right!  An infinite list!  Both Haskell and OCaml are capable of handling infinite list!  We will talk about that in another post.  We focus on unfolds with a predicate for this post.

The Formal Definition of Unfolds

The formal definition of unfolds is:

Given

(1) a predicate p which returns a bool. I.e., p b = true or p b = false.

(2) a function g which returns a pair (a, b’).  I.e., g b = (a, b’).

A list-anamorphism h is

When p b = true, h b = Nil,

otherwise, h b = Cons (a, h b’).

That is, for each unfold we just need to specify p and g and give it a value b.  Let’s see an example to illustrate this definition!  E.g., if we want a list [b, b+1, b+2, …, 9] then:

Let p b = b > 9 and g c = (c, c + 1), so:

When b > 9 h b = Nil,

otherwise, h b = Cons (b, h (b + 1)).

E.g., when b = 7:

h 7 = Cons (7, h 8) because 7 > 9 evaluates to false

= [7, Cons (8, h 9)] because 8 > 9 evaluates to false

= [7, 8, Cons (9, h 10)] because 9 > 9 evaluates to false

= [7, 8, 9] because 10 > 9 evaluates to true and thus h 10 = Nil.

Let’s implement these in Haskell and OCaml!

In Haskell, unfold is in the Data.List module as unfoldr. To implement the above:

In a terminal, run runhaskell on the file with the above code.  (runhaskell runs the .hs file you specify.)  You will see the lists you created:

[7,8,9]
[0,1,2,3,4,5,6,7,8,9]

In OCaml, unfold is not in the standard library, we have to write it by hand. The below code uses the above definition: 

It’s not as simple as in Haskell to print a list, so we just run the code in utop to see the results:

utop # #use "unfold.ml";;
val unfold : ('a -> bool) -> ('a -> 'b * 'a) -> 'a -> 'b list = <fun>
val example : int -> int list = <fun>

utop # example 7;;
- : int list = [7; 8; 9]

utop # example 0;;
- : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]

We just expanded a single value to a list!  You can imagine how powerful this can be as we use various p and g.  We will see more examples in the next post!