1076 Expert

Y Combinator — Anonymous Recursion

Higher-Order Functions

Tutorial Video

Text description (accessibility)

This video demonstrates the "Y Combinator — Anonymous Recursion" functional Rust example. Difficulty level: Expert. Key concepts covered: Higher-Order Functions. Implement the Y combinator — a fixed-point combinator that enables recursion without named function bindings. Key difference from OCaml: 1. **Recursive types:** OCaml uses `type 'a fix = Fix of ('a fix

Tutorial

The Problem

Implement the Y combinator — a fixed-point combinator that enables recursion without named function bindings. Use it to define factorial and fibonacci as anonymous recursive functions.

🎯 Learning Outcomes

• How Rust handles recursive types with Rc<RefCell> vs OCaml's algebraic type wrapper

• Interior mutability patterns for self-referencing closures

• Trait objects (dyn Fn) as the Rust equivalent of OCaml's first-class functions

• Three different approaches to anonymous recursion in Rust

🦀 The Rust Way

Rust cannot have direct cyclic references due to ownership rules. We use Rc<RefCell<Option<...>>> to create a shared mutable cell that holds the closure after construction. The Fix-based approach uses Arc and boxed trait objects. A third trait-based approach avoids heap allocation entirely.

Code Example

pub fn y<A: Copy + 'static, R: 'static>(
    f: impl Fn(&dyn Fn(A) -> R, A) -> R + 'static,
) -> Box<dyn Fn(A) -> R> {
    let holder: Rc<RefCell<Option<Rc<dyn Fn(A) -> R>>>> = Rc::new(RefCell::new(None));
    let f = Rc::new(f);
    let holder_clone = Rc::clone(&holder);
    let closure: Rc<dyn Fn(A) -> R> = Rc::new(move |a: A| -> R {
        let self_fn = Rc::clone(holder_clone.borrow().as_ref().unwrap());
        drop(holder_clone.borrow()); // release before recursing
        f(&*self_fn, a)
    });
    *holder.borrow_mut() = Some(Rc::clone(&closure));
    Box::new(move |a: A| closure(a))
}

let factorial = y(|self_fn: &dyn Fn(u64) -> u64, n: u64| {
    if n == 0 { 1 } else { n * self_fn(n - 1) }
});

type 'a fix = Fix of ('a fix -> 'a)

let y f =
  let g (Fix x as w) = f (fun a -> x w a) in
  g (Fix g)

let factorial = y (fun self n ->
  if n = 0 then 1 else n * self (n - 1))

Key Differences

Recursive types: OCaml uses type 'a fix = Fix of ('a fix -> 'a) directly; Rust needs Rc/Box indirection

Self-reference: OCaml's GC handles cycles naturally; Rust needs RefCell for interior mutability

Type erasure: OCaml functions are first-class; Rust needs dyn Fn trait objects for dynamic dispatch

Memory management: OCaml's GC cleans up the cycle; Rust's Rc reference counting handles it

OCaml Approach

OCaml uses an algebraic type Fix to wrap the recursive function reference, then builds the fixed-point by pattern matching on the wrapper. The type system handles the recursion through the Fix constructor, and garbage collection manages the cyclic reference.

Full Source

#![allow(clippy::all)]
/// Y Combinator — Fixed-point combinator for anonymous recursive functions.
///
/// The Y combinator enables recursion without named function bindings.
/// In OCaml, a recursive type wrapper (`Fix`) is needed because the type
/// system doesn't allow infinite types directly. In Rust, we use a similar
/// approach with a newtype wrapper and `Fn` trait objects.
use std::cell::RefCell;
use std::rc::Rc;

// ── Solution 1: Idiomatic Rust — using Rc<RefCell> for self-reference ──

/// Y combinator: takes a "template" function that receives a self-reference
/// as its first argument, and returns a closure that is fully recursive.
///
/// OCaml: `val y : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b`
///
/// In OCaml, `type 'a fix = Fix of ('a fix -> 'a)` wraps the recursive type.
/// In Rust, we use `Rc<dyn Fn>` to erase the recursive type behind a pointer.
pub fn y<A: Copy + 'static, R: 'static>(
    f: impl Fn(&dyn Fn(A) -> R, A) -> R + 'static,
) -> Box<dyn Fn(A) -> R> {
    // Store the final closure in a RefCell so it can reference itself
    type DynFn<A, R> = Rc<dyn Fn(A) -> R>;
    let holder: Rc<RefCell<Option<DynFn<A, R>>>> = Rc::new(RefCell::new(None));
    let f = Rc::new(f);

    let holder_clone = Rc::clone(&holder);
    let closure: Rc<dyn Fn(A) -> R> = Rc::new(move |a: A| -> R {
        let self_ref = holder_clone.borrow();
        let self_fn = Rc::clone(self_ref.as_ref().expect("closure initialized"));
        drop(self_ref); // Release borrow before calling (f may recurse)
        f(&*self_fn, a)
    });

    *holder.borrow_mut() = Some(Rc::clone(&closure));

    Box::new(move |a: A| closure(a))
}

// ── Solution 2: Struct-based approach (closer to OCaml's Fix type) ──

/// Wrapper type analogous to OCaml's `type 'a fix = Fix of ('a fix -> 'a)`.
/// The struct wraps a function that takes a reference to itself.
type FixFn<'a, A, R> = Box<dyn Fn(&Fix<'a, A, R>, A) -> R + 'a>;

struct Fix<'a, A, R> {
    f: FixFn<'a, A, R>,
}

/// Y combinator using the Fix wrapper — mirrors the OCaml implementation directly.
///
/// OCaml:
/// ```text
/// let y f =
///   let g (Fix x as w) = f (fun a -> x w a) in
///   g (Fix g)
/// ```
pub fn y_fix<A: Copy + 'static, R: 'static>(
    f: impl Fn(&dyn Fn(A) -> R, A) -> R + 'static,
) -> Box<dyn Fn(A) -> R> {
    let f = std::sync::Arc::new(f);
    let f_clone = std::sync::Arc::clone(&f);

    let fix = Fix {
        f: Box::new(move |fix: &Fix<A, R>, a: A| {
            let self_fn = |arg: A| (fix.f)(fix, arg);
            f_clone(&self_fn, a)
        }),
    };

    Box::new(move |a: A| (fix.f)(&fix, a))
}

// ── Solution 3: Trait-based approach — using a helper trait ──

/// Helper trait that makes a function callable with self-reference.
pub trait Recursive<A, R> {
    fn call(&self, arg: A) -> R;
}

/// Wrapper that ties the recursive knot via a trait implementation.
pub struct RecFn<F>(pub F);

impl<A: Copy, R, F> Recursive<A, R> for RecFn<F>
where
    F: Fn(&dyn Fn(A) -> R, A) -> R,
{
    fn call(&self, arg: A) -> R {
        (self.0)(&|a| self.call(a), arg)
    }
}

/// Create factorial using the Y combinator.
/// OCaml: `let factorial = y (fun self n -> if n = 0 then 1 else n * self (n - 1))`
pub fn factorial_y() -> Box<dyn Fn(u64) -> u64> {
    y(|self_fn: &dyn Fn(u64) -> u64, n: u64| -> u64 {
        if n == 0 {
            1
        } else {
            n * self_fn(n - 1)
        }
    })
}

/// Create fibonacci using the Y combinator.
/// OCaml: `let fibonacci = y (fun self n -> if n <= 1 then n else self (n-1) + self (n-2))`
pub fn fibonacci_y() -> Box<dyn Fn(u64) -> u64> {
    y(|self_fn: &dyn Fn(u64) -> u64, n: u64| -> u64 {
        if n <= 1 {
            n
        } else {
            self_fn(n - 1) + self_fn(n - 2)
        }
    })
}

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

    #[test]
    fn test_factorial_zero() {
        let fact = factorial_y();
        assert_eq!(fact(0), 1);
    }

    #[test]
    fn test_factorial_ten() {
        let fact = factorial_y();
        assert_eq!(fact(10), 3_628_800);
    }

    #[test]
    fn test_fibonacci_base_cases() {
        let fib = fibonacci_y();
        assert_eq!(fib(0), 0);
        assert_eq!(fib(1), 1);
    }

    #[test]
    fn test_fibonacci_ten() {
        let fib = fibonacci_y();
        assert_eq!(fib(10), 55);
    }

    #[test]
    fn test_y_fix_factorial() {
        let fact = y_fix(|self_fn: &dyn Fn(u64) -> u64, n: u64| -> u64 {
            if n == 0 {
                1
            } else {
                n * self_fn(n - 1)
            }
        });
        assert_eq!(fact(5), 120);
        assert_eq!(fact(10), 3_628_800);
    }

    #[test]
    fn test_trait_based_factorial() {
        let rec_fact = RecFn(|self_fn: &dyn Fn(u64) -> u64, n: u64| -> u64 {
            if n == 0 {
                1
            } else {
                n * self_fn(n - 1)
            }
        });
        assert_eq!(rec_fact.call(0), 1);
        assert_eq!(rec_fact.call(5), 120);
        assert_eq!(rec_fact.call(10), 3_628_800);
    }

    #[test]
    fn test_trait_based_fibonacci() {
        let rec_fib = RecFn(|self_fn: &dyn Fn(u64) -> u64, n: u64| -> u64 {
            if n <= 1 {
                n
            } else {
                self_fn(n - 1) + self_fn(n - 2)
            }
        });
        assert_eq!(rec_fib.call(0), 0);
        assert_eq!(rec_fib.call(1), 1);
        assert_eq!(rec_fib.call(10), 55);
    }
}

(* Y Combinator — Anonymous Recursion *)

(* OCaml needs a recursive type wrapper *)
type 'a fix = Fix of ('a fix -> 'a)

let y f =
  let g (Fix x as w) = f (fun a -> x w a) in
  g (Fix g)

let factorial = y (fun self n ->
  if n = 0 then 1 else n * self (n - 1))

let fibonacci = y (fun self n ->
  if n <= 1 then n else self (n - 1) + self (n - 2))

let () =
  assert (factorial 0 = 1);
  assert (factorial 10 = 3628800);
  assert (fibonacci 0 = 0);
  assert (fibonacci 1 = 1);
  assert (fibonacci 10 = 55);
  Printf.printf "10! = %d\n" (factorial 10);
  Printf.printf "fib(10) = %d\n" (fibonacci 10);
  print_endline "ok"

✓ Tests Rust test suite

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

    #[test]
    fn test_factorial_zero() {
        let fact = factorial_y();
        assert_eq!(fact(0), 1);
    }

    #[test]
    fn test_factorial_ten() {
        let fact = factorial_y();
        assert_eq!(fact(10), 3_628_800);
    }

    #[test]
    fn test_fibonacci_base_cases() {
        let fib = fibonacci_y();
        assert_eq!(fib(0), 0);
        assert_eq!(fib(1), 1);
    }

    #[test]
    fn test_fibonacci_ten() {
        let fib = fibonacci_y();
        assert_eq!(fib(10), 55);
    }

    #[test]
    fn test_y_fix_factorial() {
        let fact = y_fix(|self_fn: &dyn Fn(u64) -> u64, n: u64| -> u64 {
            if n == 0 {
                1
            } else {
                n * self_fn(n - 1)
            }
        });
        assert_eq!(fact(5), 120);
        assert_eq!(fact(10), 3_628_800);
    }

    #[test]
    fn test_trait_based_factorial() {
        let rec_fact = RecFn(|self_fn: &dyn Fn(u64) -> u64, n: u64| -> u64 {
            if n == 0 {
                1
            } else {
                n * self_fn(n - 1)
            }
        });
        assert_eq!(rec_fact.call(0), 1);
        assert_eq!(rec_fact.call(5), 120);
        assert_eq!(rec_fact.call(10), 3_628_800);
    }

    #[test]
    fn test_trait_based_fibonacci() {
        let rec_fib = RecFn(|self_fn: &dyn Fn(u64) -> u64, n: u64| -> u64 {
            if n <= 1 {
                n
            } else {
                self_fn(n - 1) + self_fn(n - 2)
            }
        });
        assert_eq!(rec_fib.call(0), 0);
        assert_eq!(rec_fib.call(1), 1);
        assert_eq!(rec_fib.call(10), 55);
    }
}

Deep Comparison

OCaml vs Rust: Y Combinator — Anonymous Recursion

Side-by-Side Code

OCaml

type 'a fix = Fix of ('a fix -> 'a)

let y f =
  let g (Fix x as w) = f (fun a -> x w a) in
  g (Fix g)

let factorial = y (fun self n ->
  if n = 0 then 1 else n * self (n - 1))

Rust (idiomatic — Rc<RefCell>)

pub fn y<A: Copy + 'static, R: 'static>(
    f: impl Fn(&dyn Fn(A) -> R, A) -> R + 'static,
) -> Box<dyn Fn(A) -> R> {
    let holder: Rc<RefCell<Option<Rc<dyn Fn(A) -> R>>>> = Rc::new(RefCell::new(None));
    let f = Rc::new(f);
    let holder_clone = Rc::clone(&holder);
    let closure: Rc<dyn Fn(A) -> R> = Rc::new(move |a: A| -> R {
        let self_fn = Rc::clone(holder_clone.borrow().as_ref().unwrap());
        drop(holder_clone.borrow()); // release before recursing
        f(&*self_fn, a)
    });
    *holder.borrow_mut() = Some(Rc::clone(&closure));
    Box::new(move |a: A| closure(a))
}

let factorial = y(|self_fn: &dyn Fn(u64) -> u64, n: u64| {
    if n == 0 { 1 } else { n * self_fn(n - 1) }
});

Rust (trait-based — zero heap allocation)

pub trait Recursive<A, R> {
    fn call(&self, arg: A) -> R;
}

pub struct RecFn<F>(pub F);

impl<A: Copy, R, F> Recursive<A, R> for RecFn<F>
where F: Fn(&dyn Fn(A) -> R, A) -> R {
    fn call(&self, arg: A) -> R {
        (self.0)(&|a| self.call(a), arg)
    }
}

Type Signatures

Concept	OCaml	Rust
Y combinator	`val y : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b`	`fn y<A, R>(f: impl Fn(&dyn Fn(A)->R, A)->R) -> Box<dyn Fn(A)->R>`
Recursive wrapper	`type 'a fix = Fix of ('a fix -> 'a)`	`struct Fix { f: Box<dyn Fn(&Fix, A) -> R> }`
Self-reference	Pattern match on `Fix x`	`Rc<RefCell<Option<Rc<dyn Fn>>>>`
Function type	`'a -> 'b` (first-class)	`dyn Fn(A) -> R` (trait object)

Key Insights

OCaml's algebraic types make recursive types trivial — type 'a fix = Fix of ('a fix -> 'a) is a one-liner. Rust needs pointer indirection (Box/Rc) to break the infinite size.

Rust's ownership prevents natural cyclic references — the Rc<RefCell<Option<...>>> pattern is the idiomatic workaround for creating self-referencing closures.

The trait-based approach is uniquely Rust — by using &dyn Fn in the trait method, we get stack-based self-reference without any heap allocation.

OCaml's GC vs Rust's Rc — OCaml's garbage collector handles the cyclic reference between Fix and the closure transparently. Rust's Rc requires explicit setup.

Both languages need type-level tricks — OCaml needs the Fix wrapper to satisfy the type checker; Rust needs trait objects to erase the recursive type.

When to Use Each Style

Use idiomatic Rust (Rc<RefCell>) when: You need a heap-allocated recursive closure that can be stored, passed around, and called multiple times from different contexts. Use trait-based Rust when: You want zero-cost abstraction and the recursive function is used locally — the RecFn approach avoids all heap allocation.

Exercises

Use the Y combinator to implement a recursive sum function that adds all integers from 1 to n without defining a named recursive function.

Implement a memoized Y combinator variant: wrap the fixed-point combinator so that results for previously computed arguments are cached in a HashMap.

Compare the Y combinator implementation with Rust's explicit recursive closures using a Box<dyn Fn> self-reference; benchmark both for computing Fibonacci(30) and explain the overhead difference.

Open Source Repos

functional-rust

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

Rust