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 unfolds. This time I’m covering envelopes, which refer to 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