Hylomorphism

A function that unfolds a seed into a recursive structure and folds that structure into a result, written so the structure is never built: hylo f g = f . fmap (hylo f g) . g. The call tree of the recursion is the intermediate structure.

For a functor $F$ with least fixed point $μ F$ and $in : F μ F \to μ F$ with inverse $out$ , a catamorphism is determined by an algebra $f : F A \to A$ and an anamorphism by a coalgebra $g : B \to F B$ :

cata f = f \circ F (cata f) \circ out ana g = in \circ F (ana g) \circ g

Composing them builds a $μ F$ value only to take it apart. Since $out \circ in = id$ and $F$ preserves composition,

cata f \circ ana g = f \circ F (cata f \circ ana g) \circ g

so the composite satisfies the equation of the hylomorphism, which does both in one recursion and allocates no $μ F$ at all:

hylo f g = f \circ F (hylo f g) \circ g

Hylomorphisms over the list functor and over the leaf-tree functor.

(* The base functor of lists: one layer, with the recursive position abstracted. *)
type ('a, 'r) listf = Nil | Cons of 'a * 'r
let map_list f = function Nil -> Nil | Cons (a, r) -> Cons (a, f r)
 
(* hylo alg coalg = alg . fmap (hylo alg coalg) . coalg *)
let rec hylo_list alg coalg x = alg (map_list (hylo_list alg coalg) (coalg x))
 
(* factorial: unfold n into n, n-1, ..., 1 and fold with multiplication,
   without ever building the list. *)
let fact =
  hylo_list
    (function Nil -> 1 | Cons (a, r) -> a * r)
    (fun n -> if n = 0 then Nil else Cons (n, n - 1))
 
(* The base functor of binary trees with values at the leaves. *)
type ('a, 'r) treef = Empty | Single of 'a | Split of 'r * 'r
let map_tree f = function Empty -> Empty | Single a -> Single a | Split (l, r) -> Split (f l, f r)
let rec hylo_tree alg coalg x = alg (map_tree (hylo_tree alg coalg) (coalg x))
 
let rec merge xs ys =
  match (xs, ys) with
  | [], l | l, [] -> l
  | x :: xs', y :: ys' -> if x <= y then x :: merge xs' ys else y :: merge xs ys'
 
(* Merge sort: the call tree of the recursion is the intermediate tree. *)
let msort =
  hylo_tree
    (function Empty -> [] | Single a -> [ a ] | Split (l, r) -> merge l r)
    (function
      | [] -> Empty
      | [ a ] -> Single a
      | xs ->
          let n = List.length xs / 2 in
          Split (List.filteri (fun i _ -> i < n) xs, List.filteri (fun i _ -> i >= n) xs))

Running it.

fact 10                 ->  3628800
msort [5;2;8;3;7;1;4]   ->  [1; 2; 3; 4; 5; 7; 8]

Factorial unfolds $n$ into $n, n - 1, \dots, 1$ and multiplies, and no list exists. Merge sort splits a list in half as its coalgebra and merges as its algebra, and the tree is only the shape of the recursive calls. Quicksort is the same with a split around a pivot and concatenation as the algebra.

Meijer, Fokkinga and Paterson named these schemes and gave the laws relating them.^[1] The fusion law, $h \circ cata f = cata g$ whenever $h \circ f = g \circ F h$ and $h$ is strict, is the basis of deforestation in compilers.