611 Expert

Paramorphism

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Paramorphism" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. A paramorphism (para) is a generalization of a catamorphism where the fold function also receives the original substructure in addition to the folded result. Key difference from OCaml: 1. **HKT requirement**: These morphisms ideally require higher

Tutorial

The Problem

A paramorphism (para) is a generalization of a catamorphism where the fold function also receives the original substructure in addition to the folded result. This enables patterns like Fibonacci (needs both current and previous values), factorial (needs both n and (n-1)!), and pretty-printing with parentheses around specific forms. It is strictly more powerful than cata for certain patterns.

🎯 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: para, fold with original substructure, F-algebra with pair

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

Code Example

#![allow(clippy::all)]
//! # Paramorphism
//! Fold with access to original substructure.

pub fn para<A: Clone, B>(xs: &[A], nil: B, cons: impl Fn(&A, &[A], B) -> B) -> B {
    let mut acc = nil;
    for i in (0..xs.len()).rev() {
        acc = cons(&xs[i], &xs[i + 1..], acc);
    }
    acc
}

pub fn tails<A: Clone>(xs: &[A]) -> Vec<Vec<A>> {
    para(xs, vec![vec![]], |_, rest, mut acc| {
        acc.insert(0, rest.to_vec());
        acc
    })
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_tails() {
        let result = tails(&[1, 2, 3]);
        assert_eq!(result.len(), 4); // [1,2,3], [2,3], [3], []
    }
}

(* Paramorphism in OCaml *)
(* Para on lists: f receives (head, tail, folded_tail) *)

let para_list nil cons xs =
  let rec go = function
    | []      -> nil
    | x :: xs -> cons x xs (go xs)
  in go xs

(* Insert into sorted list *)
let insert_sorted x xs =
  para_list
    [x]
    (fun h t folded_t -> if x <= h then x :: h :: t else h :: folded_t)
    xs

let insertion_sort xs =
  List.fold_left (fun acc x -> insert_sorted x acc) [] xs

(* Get suffix context *)
let tails xs = para_list [[]] (fun x _ rest -> (x :: List.hd rest) :: rest) xs

let () =
  Printf.printf "insert 3 into [1;2;4;5]: %s\n"
    (String.concat "," (List.map string_of_int (insert_sorted 3 [1;2;4;5])));
  Printf.printf "insertion_sort [3;1;4;1;5]: %s\n"
    (String.concat "," (List.map string_of_int (insertion_sort [3;1;4;1;5])));
  Printf.printf "tails [1;2;3]: %d sublists\n" (List.length (tails [1;2;3]))

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)]
//! # Paramorphism
//! Fold with access to original substructure.

pub fn para<A: Clone, B>(xs: &[A], nil: B, cons: impl Fn(&A, &[A], B) -> B) -> B {
    let mut acc = nil;
    for i in (0..xs.len()).rev() {
        acc = cons(&xs[i], &xs[i + 1..], acc);
    }
    acc
}

pub fn tails<A: Clone>(xs: &[A]) -> Vec<Vec<A>> {
    para(xs, vec![vec![]], |_, rest, mut acc| {
        acc.insert(0, rest.to_vec());
        acc
    })
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_tails() {
        let result = tails(&[1, 2, 3]);
        assert_eq!(result.len(), 4); // [1,2,3], [2,3], [3], []
    }
}

(* Paramorphism in OCaml *)
(* Para on lists: f receives (head, tail, folded_tail) *)

let para_list nil cons xs =
  let rec go = function
    | []      -> nil
    | x :: xs -> cons x xs (go xs)
  in go xs

(* Insert into sorted list *)
let insert_sorted x xs =
  para_list
    [x]
    (fun h t folded_t -> if x <= h then x :: h :: t else h :: folded_t)
    xs

let insertion_sort xs =
  List.fold_left (fun acc x -> insert_sorted x acc) [] xs

(* Get suffix context *)
let tails xs = para_list [[]] (fun x _ rest -> (x :: List.hd rest) :: rest) xs

let () =
  Printf.printf "insert 3 into [1;2;4;5]: %s\n"
    (String.concat "," (List.map string_of_int (insert_sorted 3 [1;2;4;5])));
  Printf.printf "insertion_sort [3;1;4;1;5]: %s\n"
    (String.concat "," (List.map string_of_int (insertion_sort [3;1;4;1;5])));
  Printf.printf "tails [1;2;3]: %d sublists\n" (List.length (tails [1;2;3]))

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_tails() {
        let result = tails(&[1, 2, 3]);
        assert_eq!(result.len(), 4); // [1,2,3], [2,3], [3], []
    }
}

Deep Comparison

Paramorphism

Fold that also sees remaining structure

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