613 Fundamental

Futumorphism

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Futumorphism" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. A futumorphism (futu) is the dual of a histomorphism — an anamorphism that can look ahead multiple levels into the future structure being built. Key difference from OCaml: 1. **HKT requirement**: These morphisms ideally require higher

Tutorial

The Problem

A futumorphism (futu) is the dual of a histomorphism — an anamorphism that can look ahead multiple levels into the future structure being built. It uses a free monad of the base functor as the coalgebra target, allowing the generator to produce multiple levels of structure at once. This is useful for expanding macros, generating tree structures, and producing ahead-of-need outputs.

🎯 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: futu, look-ahead unfold, Free monad coalgebra

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

Code Example

#![allow(clippy::all)]
//! # Futumorphism
//! Unfold that can produce multiple layers at once.

pub fn futu<S, A>(seed: S, step: impl Fn(S) -> FutuStep<A, S>) -> Vec<A> {
    let mut result = Vec::new();
    let mut s = seed;
    loop {
        match step(s) {
            FutuStep::Done => break,
            FutuStep::One(a, next) => {
                result.push(a);
                s = next;
            }
            FutuStep::Two(a, b, next) => {
                result.push(a);
                result.push(b);
                s = next;
            }
        }
    }
    result
}

pub enum FutuStep<A, S> {
    Done,
    One(A, S),
    Two(A, A, S),
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_futu() {
        let xs = futu(0, |n| {
            if n >= 4 {
                FutuStep::Done
            } else {
                FutuStep::One(n, n + 1)
            }
        });
        assert_eq!(xs, vec![0, 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)))

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)]
//! # Futumorphism
//! Unfold that can produce multiple layers at once.

pub fn futu<S, A>(seed: S, step: impl Fn(S) -> FutuStep<A, S>) -> Vec<A> {
    let mut result = Vec::new();
    let mut s = seed;
    loop {
        match step(s) {
            FutuStep::Done => break,
            FutuStep::One(a, next) => {
                result.push(a);
                s = next;
            }
            FutuStep::Two(a, b, next) => {
                result.push(a);
                result.push(b);
                s = next;
            }
        }
    }
    result
}

pub enum FutuStep<A, S> {
    Done,
    One(A, S),
    Two(A, A, S),
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_futu() {
        let xs = futu(0, |n| {
            if n >= 4 {
                FutuStep::Done
            } else {
                FutuStep::One(n, n + 1)
            }
        });
        assert_eq!(xs, vec![0, 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)))

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_futu() {
        let xs = futu(0, |n| {
            if n >= 4 {
                FutuStep::Done
            } else {
                FutuStep::One(n, n + 1)
            }
        });
        assert_eq!(xs, vec![0, 1, 2, 3]);
    }
}

Deep Comparison

Futumorphism

Unfold producing multiple layers

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