610 Expert

Hylomorphism

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Hylomorphism" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. A hylomorphism (hylo) composes an anamorphism followed by a catamorphism — build then fold. Key difference from OCaml: 1. **HKT requirement**: These morphisms ideally require higher

Tutorial

The Problem

A hylomorphism (hylo) composes an anamorphism followed by a catamorphism — build then fold. This is the general recursive scheme: any recursive computation that builds an intermediate structure and then folds it is a hylomorphism. Mergesort is the canonical example: unfold the list into a tree of comparison results, then fold to produce the sorted list.

🎯 Learning Outcomes

• The categorical definition and the mathematical laws that must hold

• How to implement this pattern in Rust despite the lack of higher-kinded types

• The relationship to more familiar functional idioms (fold, unfold, map)

• Key concepts: hylo = cata . ana, build-then-fold, mergesort as hylo

• Where this pattern appears in production systems and when simpler alternatives suffice

Code Example

#![allow(clippy::all)]
//! # Hylomorphism
//! Unfold then fold - ana composed with cata.

pub fn hylo<S, A, B>(
    seed: S,
    next: impl Fn(S) -> Option<(A, S)>,
    nil: B,
    cons: impl Fn(A, B) -> B,
) -> B {
    let list: Vec<A> = {
        let mut result = Vec::new();
        let mut s = seed;
        while let Some((a, s2)) = next(s) {
            result.push(a);
            s = s2;
        }
        result
    };
    list.into_iter().rev().fold(nil, |acc, x| cons(x, acc))
}

pub fn factorial(n: u64) -> u64 {
    hylo(
        n,
        |k| if k == 0 { None } else { Some((k, k - 1)) },
        1,
        |x, acc| x * acc,
    )
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_factorial() {
        assert_eq!(factorial(5), 120);
    }
}

(* Hylomorphism in OCaml *)

(* Factorial as hylo *)
(* Coalgebra: unfold 5 -> [5;4;3;2;1] *)
(* Algebra: fold [5;4;3;2;1] -> 120 *)
let factorial n =
  let unfold_step k = if k <= 1 then None else Some (k, k-1) in
  let seeds = let rec go k = if k<=1 then [1] else k :: go (k-1) in go n in
  List.fold_left ( * ) 1 seeds

(* Merge sort as hylomorphism *)
let rec merge xs ys = match (xs, ys) with
  | ([], _) -> ys | (_, []) -> xs
  | (x::xt, y::yt) -> if x<=y then x::merge xt ys else y::merge xs yt

let split xs =
  let rec go a b = function
    | [] -> (a, b)
    | x :: rest -> go b (x::a) rest
  in go [] [] xs

let merge_sort xs =
  let rec hylo = function
    | [] | [_] as xs -> xs
    | xs -> let (a,b) = split xs in merge (hylo a) (hylo b)
  in hylo xs

let () =
  Printf.printf "5! = %d\n" (factorial 5);
  Printf.printf "sorted: %s\n"
    (String.concat "," (List.map string_of_int (merge_sort [3;1;4;1;5;9;2;6])))

Key Differences

HKT requirement: These morphisms ideally require higher-kinded types for full generality; Rust uses GATs or associated types as approximations.

Performance: Rust's implementations are more verbose but compile to efficient machine code; OCaml's implementations are more concise with similar runtime performance.

Practical adoption: In Haskell, recursive schemes from recursion-schemes are widely used; in Rust and OCaml, direct recursion is more common in practice.

Theoretical value: Understanding these patterns deepens intuition for all recursive programming, even when direct recursion is used in production code.

OCaml Approach

OCaml's pattern matching and recursive types make morphism implementations natural. The Fix type and F-algebra/coalgebra patterns translate directly, though without Haskell's typeclass machinery:

(* OCaml recursive schemes use:
   - Recursive variant types for F-algebras
   - Higher-order functions for the morphism
   - GADTs for type-safe fixed points in advanced cases *)

Full Source

#![allow(clippy::all)]
//! # Hylomorphism
//! Unfold then fold - ana composed with cata.

pub fn hylo<S, A, B>(
    seed: S,
    next: impl Fn(S) -> Option<(A, S)>,
    nil: B,
    cons: impl Fn(A, B) -> B,
) -> B {
    let list: Vec<A> = {
        let mut result = Vec::new();
        let mut s = seed;
        while let Some((a, s2)) = next(s) {
            result.push(a);
            s = s2;
        }
        result
    };
    list.into_iter().rev().fold(nil, |acc, x| cons(x, acc))
}

pub fn factorial(n: u64) -> u64 {
    hylo(
        n,
        |k| if k == 0 { None } else { Some((k, k - 1)) },
        1,
        |x, acc| x * acc,
    )
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_factorial() {
        assert_eq!(factorial(5), 120);
    }
}

(* Hylomorphism in OCaml *)

(* Factorial as hylo *)
(* Coalgebra: unfold 5 -> [5;4;3;2;1] *)
(* Algebra: fold [5;4;3;2;1] -> 120 *)
let factorial n =
  let unfold_step k = if k <= 1 then None else Some (k, k-1) in
  let seeds = let rec go k = if k<=1 then [1] else k :: go (k-1) in go n in
  List.fold_left ( * ) 1 seeds

(* Merge sort as hylomorphism *)
let rec merge xs ys = match (xs, ys) with
  | ([], _) -> ys | (_, []) -> xs
  | (x::xt, y::yt) -> if x<=y then x::merge xt ys else y::merge xs yt

let split xs =
  let rec go a b = function
    | [] -> (a, b)
    | x :: rest -> go b (x::a) rest
  in go [] [] xs

let merge_sort xs =
  let rec hylo = function
    | [] | [_] as xs -> xs
    | xs -> let (a,b) = split xs in merge (hylo a) (hylo b)
  in hylo xs

let () =
  Printf.printf "5! = %d\n" (factorial 5);
  Printf.printf "sorted: %s\n"
    (String.concat "," (List.map string_of_int (merge_sort [3;1;4;1;5;9;2;6])))

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_factorial() {
        assert_eq!(factorial(5), 120);
    }
}

Deep Comparison

Hylomorphism

Compose unfold with fold

Exercises

Laws verification: Write tests that verify the categorical laws for this morphism on a specific data type.

New data type: Apply the morphism to a different recursive data type (e.g., apply catamorphism to a rose tree instead of a binary tree).

Comparison: Implement the same computation using direct recursion and the morphism — measure whether the morphism version composes more cleanly.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust