611: Paramorphism

Difficulty: 5 Level: Master A fold where the algebra receives both the computed result and the original sub-structure — enabling context-aware recursion like sorted insertion.

The Problem This Solves

Catamorphism (`fold`) gives your algebra only the accumulated result so far. But some algorithms need to see the original recursive structure at each step, not just what it computed to. Consider inserting into a sorted list: at each `Cons(head, tail)` node, you need to compare with `head` and potentially prepend to the original tail — but cata has already replaced the tail with a folded value. The workaround with `cata` is to carry both the original and the result as a tuple, but this is ad-hoc. A paramorphism makes it structural: the algebra receives `F<(original, result)>` — both the sub-structure and the fold result at each recursive position. This is the formal version of "sometimes you need to look at what you're folding, not just what you've computed." The canonical example is `tails :: [a] -> [[a]]` — at each step you need the original tail to add to the results list.

The Intuition

A paramorphism is like catamorphism, except the algebra gets a pair `(sub-structure, fold-result)` at each recursive position — it "keeps the original around" so context-aware decisions can use it. The trade-off: more powerful than cata but slightly harder to reason about; use cata when you only need the result, para when you need both.

How It Works in Rust

// A simple natural number type as a recursive structure
enum Nat {
 Zero,
 Succ(Box<Nat>),
}

impl Nat {
 fn to_usize(&self) -> usize {
     match self {
         Nat::Zero    => 0,
         Nat::Succ(n) => 1 + n.to_usize(),
     }
 }

 // Paramorphism: algebra gets (original_sub, fold_result) pairs
 fn para<A>(self, zero_case: A, succ_case: impl Fn(Nat, A) -> A) -> A
 {
     match self {
         Nat::Zero       => zero_case,
         Nat::Succ(pred) => {
             // para the predecessor — get its result
             let pred_result = pred.para(zero_case, &succ_case);
             // But we've consumed pred — in a real para we'd clone or use &
             // The key idea: algebra receives (original_pred, pred_result)
             succ_case(*pred, pred_result)
             //         ^^^^^ original sub-structure
             //                       ^^^^^^^^^^^ computed result
         }
     }
 }
}

// Example: factorial — needs the original number at each step
// fact(n) = n * fact(n-1)
// With para: succ case gets (pred_nat, fact_of_pred)
// so we can do (pred_nat.to_usize() + 1) * fact_of_pred

// Contrast with cata — can only do running_product * 1 (loses the index)

For lists, paramorphism enables `tails`, sorted insertion, and "insert at position N" — all require the original tail at each step.

What This Unlocks

Sorted insertion: at each `Cons(head, tail)`, compare insertion value with `head` and either prepend using original `tail` or recurse — needs the original, not just the result.
`tails` function: `[[1,2,3], [2,3], [3], []]` — each step prepends the original sub-list.
Index-aware folds: algorithms where the fold result depends on the depth or original size at each position.

Key Differences

Concept	OCaml	Rust
Paramorphism	`let rec para alg = function ...`	`fn para(self, alg: impl Fn(F<(T,R)>) -> R)`
Algebra input (cata)	`F<R>` — only fold result	`F<R>`
Algebra input (para)	`F<(T, R)>` — original + result	`F<(T, R)>`
Use case	Context-aware folds	Sorted insert, `tails`, index-dependent
Relationship to cata	Para is strictly more powerful	`cata alg = para (alg . fmap snd)`
Ownership challenge	GC handles copying	Need `Clone` or reference to keep original

// Paramorphism: algebra receives (current_elem, original_rest, folded_rest)
fn para_list<A: Clone, R>(
    xs: &[A],
    nil: R,
    cons: impl Fn(&A, &[A], R) -> R + Copy,
) -> R {
    match xs {
        []            => nil,
        [head, rest @ ..] => {
            let folded_rest = para_list(rest, nil, cons);
            cons(head, rest, folded_rest)
        }
    }
}

// Insert into sorted list — needs original tail for correctness
fn insert_sorted(x: i32, xs: &[i32]) -> Vec<i32> {
    para_list(
        xs,
        vec![x],
        |&head, tail, folded| {
            if x <= head {
                let mut v = vec![x, head];
                v.extend_from_slice(tail);
                v
            } else {
                let mut v = vec![head];
                v.extend(folded);
                v
            }
        },
    )
}

fn insertion_sort(mut xs: Vec<i32>) -> Vec<i32> {
    let items = xs.clone();
    xs.clear();
    for x in items { xs = insert_sorted(x, &xs); }
    xs
}

// Tails: paramorphism exposing original sublist
fn tails<A: Clone>(xs: &[A]) -> Vec<Vec<A>> {
    para_list(
        xs,
        vec![vec![]],
        |head, _rest, mut folded| {
            let first = folded[0].clone();
            let mut new_first = vec![head.clone()];
            new_first.extend(first);
            folded.insert(0, new_first);
            folded
        },
    )
}

fn main() {
    let sorted = insert_sorted(3, &[1,2,4,5]);
    println!("insert 3 into [1,2,4,5]: {:?}", sorted);
    println!("insertion_sort: {:?}", insertion_sort(vec![3,1,4,1,5,9,2,6]));
    let t = tails(&[1i32,2,3]);
    println!("tails: {:?}", t);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test] fn insert_test() { assert_eq!(insert_sorted(3,&[1,2,4,5]), vec![1,2,3,4,5]); }
    #[test] fn sort_test()   { assert_eq!(insertion_sort(vec![3,1,2]),  vec![1,2,3]); }
    #[test] fn tails_test()  { assert_eq!(tails(&[1i32,2]).len(), 3); /* [1,2],[2],[] */ }
}

(* 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]))