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

*. As Conal Elliott puts it: while*

**folds****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

**and give it a value**

*g**. Let’s see an example to illustrate this definition! E.g., if we want a list [b, b+1, b+2, …, 9] then:*

**b**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!

## Leave a Reply