218 Expert

Anamorphism — Unfold to Build Recursive Structures

Functional Programming

Tutorial

The Problem

The dual of a catamorphism is the anamorphism (ana) — it unfolds a seed into a recursive structure. Where cata tears down a structure bottom-up, ana builds one top-down. unfold for lists is an anamorphism: starting from a seed, repeatedly apply a coalgebra to produce the next element and the new seed, until reaching the base case. This is how infinite streams, number sequences, and tree generation are expressed functionally.

🎯 Learning Outcomes

• Understand anamorphisms as the dual of catamorphisms (unfold vs. fold)

• Learn how a coalgebra seed -> F<seed> drives top-down unfolding

• See examples: unfolding an integer range into a list, unfolding a tree from a specification

• Understand the connection to codata (potentially infinite structures) in functional programming

Code Example

fn ana<S>(coalg: &dyn Fn(S) -> ListF<S>, seed: S) -> FixList {
    FixList(Box::new(coalg(seed).map(|s| ana(coalg, s))))
}

let rec ana coalg seed =
  FixL (map_lf (ana coalg) (coalg seed))

Key Differences

Duality: ana and cata are mathematical duals — cata = fold (teardown), ana = unfold (buildup); this symmetry appears throughout category theory.

Infinite structures: Anamorphisms naturally express codata (infinite lists, streams); in strict languages, lazy evaluation is needed to prevent infinite unfolding.

**OCaml Seq**: OCaml's Seq.unfold : ('b -> ('a * 'b) option) -> 'b -> 'a Seq.t is the standard anamorphism for lazy sequences — directly matching the coalgebra pattern.

Rust iterators: Rust's std::iter::successors(init, f) and unfold(init, f) (in itertools) implement the iterator version of anamorphisms.

OCaml Approach

OCaml's anamorphism:

let rec ana coalg seed = Fix (map_list_f (ana coalg) (coalg seed))
(* Range example: *)
let range_coalg n = if n <= 0 then NilF else ConsF (n, n-1)
let range n = ana range_coalg n

OCaml's lazy sequences (Seq.t) provide the standard mechanism for anamorphism-style generation — each Seq.cons is one step of an anamorphism with the continuation as the tail thunk.

Full Source

#![allow(clippy::all)]
// Example 218: Anamorphism — Unfold to Build Recursive Structures

// ana : (seed -> F<seed>) -> seed -> Fix<F>

#[derive(Debug, Clone)]
enum ListF<A> {
    NilF,
    ConsF(i64, A),
}

impl<A> ListF<A> {
    fn map<B>(self, f: impl Fn(A) -> B) -> ListF<B> {
        match self {
            ListF::NilF => ListF::NilF,
            ListF::ConsF(x, a) => ListF::ConsF(x, f(a)),
        }
    }
    fn map_ref<B>(&self, f: impl Fn(&A) -> B) -> ListF<B> {
        match self {
            ListF::NilF => ListF::NilF,
            ListF::ConsF(x, a) => ListF::ConsF(*x, f(a)),
        }
    }
}

#[derive(Debug, Clone)]
struct FixList(Box<ListF<FixList>>);

fn ana<S>(coalg: &dyn Fn(S) -> ListF<S>, seed: S) -> FixList {
    FixList(Box::new(coalg(seed).map(|s| ana(coalg, s))))
}

fn cata<A>(alg: &dyn Fn(ListF<A>) -> A, FixList(f): &FixList) -> A {
    alg(f.map_ref(|child| cata(alg, child)))
}

fn to_vec(fl: &FixList) -> Vec<i64> {
    cata(
        &|l| match l {
            ListF::NilF => vec![],
            ListF::ConsF(x, mut acc) => {
                acc.insert(0, x);
                acc
            }
        },
        fl,
    )
}

// Approach 1: Range [lo..=hi]
fn range(lo: i64, hi: i64) -> FixList {
    ana(
        &|s: (i64, i64)| {
            if s.0 > s.1 {
                ListF::NilF
            } else {
                ListF::ConsF(s.0, (s.0 + 1, s.1))
            }
        },
        (lo, hi),
    )
}

// Approach 2: Countdown
fn countdown(n: i64) -> FixList {
    ana(
        &|s| {
            if s <= 0 {
                ListF::NilF
            } else {
                ListF::ConsF(s, s - 1)
            }
        },
        n,
    )
}

// Approach 3: Collatz sequence
fn collatz(n: i64) -> FixList {
    ana(
        &|s| {
            if s <= 0 {
                ListF::NilF
            } else if s == 1 {
                ListF::ConsF(1, 0)
            } else if s % 2 == 0 {
                ListF::ConsF(s, s / 2)
            } else {
                ListF::ConsF(s, 3 * s + 1)
            }
        },
        n,
    )
}

// Tree anamorphism
#[derive(Debug, Clone)]
enum TreeF<A> {
    LeafF(i64),
    BranchF(A, A),
}

impl<A> TreeF<A> {
    fn map<B>(self, f: impl Fn(A) -> B) -> TreeF<B> {
        match self {
            TreeF::LeafF(n) => TreeF::LeafF(n),
            TreeF::BranchF(l, r) => TreeF::BranchF(f(l), f(r)),
        }
    }
    fn map_ref<B>(&self, f: impl Fn(&A) -> B) -> TreeF<B> {
        match self {
            TreeF::LeafF(n) => TreeF::LeafF(*n),
            TreeF::BranchF(l, r) => TreeF::BranchF(f(l), f(r)),
        }
    }
}

#[derive(Debug, Clone)]
struct FixTree(Box<TreeF<FixTree>>);

fn ana_tree<S>(coalg: &dyn Fn(S) -> TreeF<S>, seed: S) -> FixTree {
    FixTree(Box::new(coalg(seed).map(|s| ana_tree(coalg, s))))
}

fn balanced_tree(depth: u32) -> FixTree {
    ana_tree(
        &|s: (u32, i64)| {
            if s.0 == 0 {
                TreeF::LeafF(s.1)
            } else {
                TreeF::BranchF((s.0 - 1, s.1), (s.0 - 1, s.1 + (1i64 << (s.0 - 1))))
            }
        },
        (depth, 1),
    )
}

fn tree_to_vec(t: &FixTree) -> Vec<i64> {
    fn go(t: &FixTree) -> Vec<i64> {
        match t.0.as_ref() {
            TreeF::LeafF(n) => vec![*n],
            TreeF::BranchF(l, r) => {
                let mut v = go(l);
                v.extend(go(r));
                v
            }
        }
    }
    go(t)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_range() {
        assert_eq!(to_vec(&range(1, 3)), vec![1, 2, 3]);
    }

    #[test]
    fn test_countdown() {
        assert_eq!(to_vec(&countdown(3)), vec![3, 2, 1]);
    }

    #[test]
    fn test_collatz_1() {
        assert_eq!(to_vec(&collatz(1)), vec![1]);
    }

    #[test]
    fn test_balanced_tree() {
        assert_eq!(tree_to_vec(&balanced_tree(1)), vec![1, 2]);
    }
}

(* Example 218: Anamorphism — Unfold to Build Recursive Structures *)

(* ana : ('a -> 'f 'a) -> 'a -> fix
   The dual of cata: builds UP a structure from a seed. *)

type 'a list_f = NilF | ConsF of int * 'a

let map_lf f = function NilF -> NilF | ConsF (x, a) -> ConsF (x, f a)

type fix_list = FixL of fix_list list_f

let rec ana coalg seed =
  FixL (map_lf (ana coalg) (coalg seed))

let rec cata alg (FixL f) =
  alg (map_lf (cata alg) f)

(* Approach 1: Build a range [lo..hi] *)
let range_coalg (lo, hi) =
  if lo > hi then NilF
  else ConsF (lo, (lo + 1, hi))

let range lo hi = ana range_coalg (lo, hi)

(* Approach 2: Build countdown *)
let countdown_coalg n =
  if n <= 0 then NilF
  else ConsF (n, n - 1)

let countdown n = ana countdown_coalg n

(* Approach 3: Collatz sequence *)
let collatz_coalg n =
  if n <= 1 then ConsF (1, 0)  (* terminal *)
  else if n = 0 then NilF
  else if n mod 2 = 0 then ConsF (n, n / 2)
  else ConsF (n, 3 * n + 1)

let collatz n = ana collatz_coalg n

(* Convert fix_list to OCaml list *)
let to_list fl = cata (function NilF -> [] | ConsF (x, acc) -> x :: acc) fl

(* Tree anamorphism *)
type 'a tree_f = LeafF of int | BranchF of 'a * 'a

let map_tf f = function LeafF n -> LeafF n | BranchF (l, r) -> BranchF (f l, f r)

type fix_tree = FixT of fix_tree tree_f

let rec ana_tree coalg seed =
  FixT (map_tf (ana_tree coalg) (coalg seed))

let rec cata_tree alg (FixT f) = alg (map_tf (cata_tree alg) f)

(* Build a balanced binary tree of depth d *)
let balanced_coalg (d, start) =
  if d <= 0 then LeafF start
  else BranchF ((d - 1, start), (d - 1, start + (1 lsl (d - 1))))

let balanced_tree d = ana_tree balanced_coalg (d, 1)

let tree_to_list t = cata_tree (function LeafF n -> [n] | BranchF (l, r) -> l @ r) t

(* === Tests === *)
let () =
  assert (to_list (range 1 5) = [1; 2; 3; 4; 5]);
  assert (to_list (range 3 3) = [3]);
  assert (to_list (range 5 3) = []);

  assert (to_list (countdown 5) = [5; 4; 3; 2; 1]);
  assert (to_list (countdown 0) = []);

  let c = to_list (collatz 6) in
  assert (c = [6; 3; 10; 5; 16; 8; 4; 2; 1]);

  let t = balanced_tree 2 in
  assert (tree_to_list t = [1; 2; 3; 4]);

  let t3 = balanced_tree 3 in
  assert (List.length (tree_to_list t3) = 8);

  print_endline "✓ All tests passed"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_range() {
        assert_eq!(to_vec(&range(1, 3)), vec![1, 2, 3]);
    }

    #[test]
    fn test_countdown() {
        assert_eq!(to_vec(&countdown(3)), vec![3, 2, 1]);
    }

    #[test]
    fn test_collatz_1() {
        assert_eq!(to_vec(&collatz(1)), vec![1]);
    }

    #[test]
    fn test_balanced_tree() {
        assert_eq!(tree_to_vec(&balanced_tree(1)), vec![1, 2]);
    }
}

Deep Comparison

Comparison: Example 218 — Anamorphism

ana Definition

OCaml

let rec ana coalg seed =
  FixL (map_lf (ana coalg) (coalg seed))

Rust

fn ana<S>(coalg: &dyn Fn(S) -> ListF<S>, seed: S) -> FixList {
    FixList(Box::new(coalg(seed).map(|s| ana(coalg, s))))
}

Coalgebra: Range

OCaml

let range_coalg (lo, hi) =
  if lo > hi then NilF
  else ConsF (lo, (lo + 1, hi))

let range lo hi = ana range_coalg (lo, hi)

Rust

fn range(lo: i64, hi: i64) -> FixList {
    ana(&|s: (i64, i64)| {
        if s.0 > s.1 { ListF::NilF }
        else { ListF::ConsF(s.0, (s.0 + 1, s.1)) }
    }, (lo, hi))
}

Coalgebra: Collatz

OCaml

let collatz_coalg n =
  if n <= 1 then ConsF (1, 0)
  else if n mod 2 = 0 then ConsF (n, n / 2)
  else ConsF (n, 3 * n + 1)

Rust

ana(&|s| {
    if s <= 0 { ListF::NilF }
    else if s == 1 { ListF::ConsF(1, 0) }
    else if s % 2 == 0 { ListF::ConsF(s, s / 2) }
    else { ListF::ConsF(s, 3 * s + 1) }
}, n)

Exercises

Implement take_n(coalg, seed, n) that generates at most n elements — preventing infinite loops.

Write an anamorphism that generates a binary tree from a list of values (each level takes the next value).

Use ana to implement repeat(x) — an infinite list of the same value.

Open Source Repos

functional-rust

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

Rust