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. I also discussed lenses before, which refer to

**anamorphisms**or

**. This time I’m covering envelopes, which refer to**

*unfolds***hylomorphisms**.

## What is Hylomorphism?

**Hylomorphism is the composition of anamorphism ( unfold) and catamorphism (fold).** Hylomorphism (for lists) puts the result of an unfold (a list) into a

*fold*, which takes a list as an input and output a single result.

The **factorial function** is the classic example. Using *unfold*, one can generate a list of integers starting from 1, up to n. The generated list is then input to a *fold* such that the integers of the list are multiplied to give the factorial of n.

## Factorial In Haskell with Hylomorphisms

In Haskell, we can write the factorial function with hylomorphism using *foldr* and *unfoldr*:

Running *runhaskell fact.hs* in a terminal (in the directory your *fact.hs* file is in) should return 120, the factorial of 5.

The above nicely illustrates hylomorphism in action. Writing it with pattern matching is shorter and more standard though:

## In OCaml

In OCaml, as mentioned in this post, unfold is not in the standard library. I use the unfold function that I wrote earlier to write the factorial function in OCaml:

In the terminal:

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

One can also use pattern matching to write this in OCaml, using point-free style and *function*:

utop#let rec fact = function 0 -> 1 | n -> n * fact (n - 1);; val fact : int -> int = <fun>utop#fact 5;; - : int = 120

Note that the above only works for positive integers.

## Leave a Reply