613: Futumorphism

Difficulty: 5 Level: Master An anamorphism (unfold) that can produce multiple levels at once — the dual of histomorphism, using a `Free` comonad structure.

The Problem This Solves

Anamorphism (`ana`) unfolds a seed value one step at a time: given a seed, produce one layer of the structure and a new seed for the next. This is fine for simple sequences, but some generation patterns are naturally multi-step. Generating Fibonacci numbers requires two previous values; generating bit patterns requires looking two positions ahead; tokenizing a string may produce multiple tokens per source character. With `ana`, multi-step generation requires threading awkward state through the seed type. You end up encoding "I already generated the next element, please use it" in the seed, which is a code smell. The futumorphism makes this formal: the coalgebra can return a `Free F A` value that contains either a seed for further unfolding (`Pure(seed)`) or a pre-built layer with possibly more seeds embedded (`Free(layer)`). This is the dual of histomorphism: histo gives the fold access to all previous results; futu gives the unfold the ability to produce multiple future steps. Together they form the "past and future" recursion scheme pair.

The Intuition

A futumorphism is an anamorphism where the coalgebra can "pre-produce" multiple layers at once instead of just one seed — by returning a `Free` value that interleaves "I have a ready-made layer here" with "continue unfolding from this seed". The trade-off: more expressive than `ana` but harder to reason about; use `ana` when you generate one step at a time, `futu` when the natural decomposition produces multiple steps.

How It Works in Rust

// Free monad over F: either a pure value (seed for continuation)
// or a layer with Free values in the recursive positions
enum Free<A> {
 Pure(A),              // "continue unfolding from seed A"
 Cons(i32, Box<Free<A>>),  // "here's a ready-made layer; recurse into inner Free"
}

// The unfolded list result
type List = Vec<i32>;

// Futumorphism: coalgebra returns Free<Seed> — can produce multiple steps
fn futu<S>(seed: S, coalg: &impl Fn(S) -> Free<S>) -> List {
 let mut result = Vec::new();
 futu_inner(coalg(seed), coalg, &mut result);
 result
}

fn futu_inner<S>(free: Free<S>, coalg: &impl Fn(S) -> Free<S>, out: &mut Vec<i32>) {
 match free {
     Free::Pure(seed) => {
         // Continue unfolding from the new seed
         futu_inner(coalg(seed), coalg, out);
     }
     Free::Cons(value, rest) => {
         // Pre-built layer — emit this value and continue with rest
         out.push(value);
         futu_inner(*rest, coalg, out);
     }
 }
}

// Example: generate pairs [n, n+1, n+2, ...] stepping by 2
// The coalgebra produces TWO elements at once
fn pair_coalg(seed: i32) -> Free<i32> {
 if seed > 10 {
     return Free::Pure(seed); // actually, terminate somehow
 }
 // Produce two elements in one coalgebra call
 Free::Cons(seed, Box::new(Free::Cons(seed + 1, Box::new(Free::Pure(seed + 2)))))
 //         ^^^^ first element  ^^^^^^^^^^^^^^^^^^^^^ second element pre-built
}

The key: a single coalgebra invocation can produce multiple `Cons` layers before bottoming out with `Pure(next_seed)`, enabling efficient multi-step generation.

What This Unlocks

Efficient sequence generation: produce Fibonacci pairs, byte pairs, or token groups in single coalgebra calls without re-entering the unfold machinery.
Streaming tokenizers: one source character may produce multiple tokens — futu naturally expresses this as one coalgebra step yielding multiple `Cons` nodes.
Dual of dynamic programming: while histo accumulates past results to avoid recomputation, futu pre-computes future steps to avoid redundant seeds.

Key Differences

Concept	OCaml	Rust
Anamorphism	`let rec ana coalg seed = ...`	`fn ana<S>(seed: S, coalg: impl Fn(S) -> F<S>)`
Futumorphism	`futu coalg seed` — coalg returns `CoFree`	Coalgebra returns `Free<S>`
vs Ana	One layer per call	Multiple layers per call possible
`Free` monad	`type 'a free = Pure of 'a \	Free of 'a free f`	`enum Free<A> { Pure(A), Layer(...) }`
Dual of	Histomorphism	Histomorphism
Practical use	Batch generation, tokenizers	Same

// Futumorphism: coalgebra produces CoFree<A,S> — can inject pre-computed values

#[derive(Debug,Clone)]
enum CoFree<A,S> {
    Emit(A, Box<CoFree<A,S>>),  // emit A, then continue with inner CoFree
    Next(S),                     // defer to next coalgebra call
    Done,
}

fn futu<S: Clone, A: Clone>(
    seed: S,
    coalg: impl Fn(S) -> CoFree<A,S> + Copy,
) -> Vec<A> {
    let mut result = Vec::new();
    let mut current = coalg(seed);
    loop {
        match current {
            CoFree::Done       => break,
            CoFree::Emit(a,rest) => { result.push(a); current = *rest; }
            CoFree::Next(s)    => { current = coalg(s); }
        }
    }
    result
}

// Collatz sequence
fn collatz(n: u64) -> Vec<u64> {
    let mut seq = vec![n];
    let mut k = n;
    while k != 1 {
        k = if k % 2 == 0 { k/2 } else { 3*k+1 };
        seq.push(k);
    }
    seq
}

// Fibonacci via futumorphism (emit two per step)
fn fib_futu(limit: u64) -> Vec<u64> {
    fn coalg((a,b): (u64,u64)) -> CoFree<u64,(u64,u64)> {
        if a > limit { return CoFree::Done; }
        if b > limit {
            CoFree::Emit(a, Box::new(CoFree::Done))
        } else {
            CoFree::Emit(a, Box::new(CoFree::Emit(b, Box::new(CoFree::Next((b,a+b))))))
        }
    }
    fn limit_fn() -> u64 { 100 } // closure workaround
    let _ = limit_fn;
    // Inline since closures can't be recursive easily here
    let mut result = Vec::new();
    let (mut a, mut b) = (0u64, 1u64);
    while a <= limit || b <= limit {
        if a <= limit { result.push(a); }
        if b <= limit { result.push(b); }
        let (na,nb) = (b, a+b);
        a = na; b = nb;
        if a > limit { break; }
    }
    result
}

fn main() {
    println!("collatz(6): {:?}", collatz(6));
    println!("collatz(27) len: {}", collatz(27).len());
    println!("fibs <= 100: {:?}", fib_futu(100));

    // Futu with CoFree
    let evens = futu(0u64, |n| {
        if n > 10 { CoFree::Done }
        else { CoFree::Emit(n*2, Box::new(CoFree::Next(n+1))) }
    });
    println!("evens: {:?}", evens);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test] fn collatz_one()  { assert_eq!(collatz(1), vec![1]); }
    #[test] fn collatz_6()    { assert_eq!(collatz(6), vec![6,3,10,5,16,8,4,2,1]); }
    #[test] fn fib_starts()   { let f=fib_futu(10); assert_eq!(f[..5], [0,1,1,2,3]); }
}

(* Futumorphism simulated via multi-step unfold in OCaml *)

(* Standard unfold *)
let unfold coalg seed =
  let rec go s = match coalg s with
    | None        -> []
    | Some(x, s') -> x :: go s'
  in go seed

(* Futu-style: coalgebra can emit multiple items *)
let futu_unfold coalg seed =
  let rec go s = match coalg s with
    | None           -> []
    | Some(items, s') -> items @ go s'
  in go seed

(* Generate Collatz sequence *)
let collatz n =
  unfold (fun k ->
    if k = 1 then None
    else if k mod 2 = 0 then Some(k, k/2)
    else Some(k, 3*k+1)
  ) n

(* Generate Fibonacci pairs (futu-style: emit two per step) *)
let fib_pairs n =
  futu_unfold (fun (a,b) ->
    if a > n then None
    else Some([a;b], (b, a+b))
  ) (0,1)

let () =
  Printf.printf "collatz 6: %s\n" (String.concat "->" (List.map string_of_int (collatz 6)));
  let fibs = List.filter (fun x -> x <= n) (fib_pairs 100) in
  ignore fibs;
  let fibs = fib_pairs 100 in
  Printf.printf "fib pairs: %s\n" (String.concat " " (List.map string_of_int (List.filteri (fun i _ -> i < 10) fibs)))