1082 Advanced

Tail-Recursive Map with CPS

Higher-Order Functions

Tutorial Video

Text description (accessibility)

This video demonstrates the "Tail-Recursive Map with CPS" functional Rust example. Difficulty level: Advanced. Key concepts covered: Higher-Order Functions. Implement `List.map` in three ways: naive recursive (stack-unsafe), tail-recursive with an accumulator and reverse, and continuation-passing style (CPS). Key difference from OCaml: 1. **Tail

Tutorial

The Problem

Implement List.map in three ways: naive recursive (stack-unsafe), tail-recursive with an accumulator and reverse, and continuation-passing style (CPS). Show how each approach handles the stack-safety problem.

🎯 Learning Outcomes

• Understanding why naive recursive map overflows the stack on large inputs

• Translating OCaml's tail-recursive accumulator pattern to Rust's loop-based equivalent

• Building continuation chains with boxed closures as a Rust analog to OCaml CPS

• Recognizing that Rust's lack of TCO makes explicit loops the practical choice over structural tail recursion

🦀 The Rust Way

Rust does not guarantee TCO, so even structurally tail-recursive functions can overflow. The idiomatic Rust translation of OCaml's accumulator pattern is a for loop with Vec::push. The CPS version uses Box<dyn FnOnce> to build a closure chain, which is educational but applies the chain via nested calls (still O(n) stack). The truly idiomatic solution is iter().map().collect().

Code Example

pub fn map_idiomatic<T, U, F: Fn(&T) -> U>(f: F, list: &[T]) -> Vec<U> {
    list.iter().map(f).collect()
}

(* Naive — not tail-recursive *)
let rec map_naive f = function
  | [] -> []
  | h :: t -> f h :: map_naive f t

(* Tail-recursive with accumulator + reverse *)
let map_tr f lst =
  let rec go acc = function
    | [] -> List.rev acc
    | h :: t -> go (f h :: acc) t
  in go [] lst

(* CPS — tail-recursive, preserves order *)
let map_cps f lst =
  let rec go k = function
    | [] -> k []
    | h :: t -> go (fun rest -> k (f h :: rest)) t
  in go Fun.id lst

Key Differences

Tail-call optimization: OCaml guarantees TCO; Rust does not. Structural tail recursion in Rust still overflows.

List construction: OCaml cons (::) prepends in O(1), requiring List.rev at the end. Rust's Vec::push appends in O(1) amortized — no reverse needed.

Continuations: OCaml closures are lightweight GC-managed values. Rust requires Box<dyn FnOnce> heap allocation for each continuation in the chain.

Idiomatic solution: OCaml developers write List.map. Rust developers write iter().map(f).collect() — both are zero-overhead abstractions over the same pattern.

OCaml Approach

OCaml guarantees tail-call optimization, so rewriting map with an accumulator parameter (go acc = function ...) makes it stack-safe. The CPS version achieves the same by passing a continuation closure — all recursive calls are in tail position. Both map_tr and map_cps handle million-element lists without overflow.

Full Source

#![allow(clippy::all)]
// === Solution 1: Naive recursive map ===
// Direct translation of OCaml's `let rec map f = function | [] -> [] | h::t -> f h :: map f t`
// Not tail-recursive: the cons (`f h ::`) happens AFTER the recursive call returns.
// Will stack-overflow on large inputs — same problem as OCaml's naive version.
pub fn map_naive<T, U, F: Fn(&T) -> U>(f: &F, list: &[T]) -> Vec<U> {
    match list {
        [] => vec![],
        [head, tail @ ..] => {
            let mut result = vec![f(head)];
            result.extend(map_naive(f, tail));
            result
        }
    }
}

// === Solution 2: Accumulator-based map (loop) ===
// In OCaml, this is tail-recursive: `let rec go acc = function | [] -> List.rev acc | h::t -> go (f h :: acc) t`
// OCaml cons prepends (O(1)) building the list in reverse, then List.rev fixes order.
// Rust has no TCO guarantee, so the idiomatic translation is a loop.
// Vec::push appends (O(1) amortized) and builds in forward order — no reverse needed.
pub fn map_acc<T, U, F: Fn(&T) -> U>(f: &F, list: &[T]) -> Vec<U> {
    let mut acc = Vec::with_capacity(list.len());
    for item in list {
        acc.push(f(item));
    }
    acc
}

// === Solution 3: CPS (Continuation-Passing Style) ===
// OCaml: `let rec go k = function | [] -> k [] | h::t -> go (fun rest -> k (f h :: rest)) t`
// Each step wraps the previous continuation, building a chain of closures.
// In OCaml this is tail-recursive (go is the last call). In Rust we build the
// continuation chain with a loop (since no TCO), then apply it.
// Note: applying the chain still uses O(n) stack frames from nested closures.
pub fn map_cps<T, U, F: Fn(&T) -> U>(f: &F, list: &[T]) -> Vec<U> {
    // Identity continuation — base case returns its argument unchanged
    let mut cont: Box<dyn FnOnce(Vec<U>) -> Vec<U>> = Box::new(|v| v);

    // Build the chain in reverse so the first element's continuation is outermost.
    // Each layer pushes its mapped value, then delegates to the previous continuation.
    for item in list.iter().rev() {
        let mapped = f(item);
        let prev = cont;
        cont = Box::new(move |mut rest: Vec<U>| {
            rest.push(mapped);
            prev(rest)
        });
    }

    cont(Vec::new())
}

// === Solution 4: Idiomatic Rust ===
// How a Rust developer actually writes map — iterator adaptor chain.
// No recursion, no manual accumulation. The compiler optimizes this into a tight loop.
pub fn map_idiomatic<T, U, F: Fn(&T) -> U>(f: F, list: &[T]) -> Vec<U> {
    list.iter().map(f).collect()
}

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

    // --- map_naive ---
    #[test]
    fn naive_empty() {
        assert_eq!(map_naive(&|x: &i32| x * 2, &[]), Vec::<i32>::new());
    }

    #[test]
    fn naive_single() {
        assert_eq!(map_naive(&|x: &i32| x + 1, &[5]), vec![6]);
    }

    #[test]
    fn naive_multiple() {
        assert_eq!(map_naive(&|x: &i32| x * 2, &[1, 2, 3, 4]), vec![2, 4, 6, 8]);
    }

    #[test]
    fn naive_strings() {
        let words = ["hello", "world"];
        assert_eq!(
            map_naive(&|s: &&str| s.to_uppercase(), &words),
            vec!["HELLO", "WORLD"]
        );
    }

    // --- map_acc ---
    #[test]
    fn acc_empty() {
        assert_eq!(map_acc(&|x: &i32| x * 2, &[]), Vec::<i32>::new());
    }

    #[test]
    fn acc_single() {
        assert_eq!(map_acc(&|x: &i32| x + 1, &[5]), vec![6]);
    }

    #[test]
    fn acc_multiple() {
        assert_eq!(map_acc(&|x: &i32| x * 2, &[1, 2, 3, 4]), vec![2, 4, 6, 8]);
    }

    #[test]
    fn acc_preserves_order() {
        assert_eq!(map_acc(&|x: &i32| *x, &[10, 20, 30]), vec![10, 20, 30]);
    }

    #[test]
    fn acc_large_input() {
        let big: Vec<i32> = (0..1_000_000).collect();
        let result = map_acc(&|x: &i32| x * 2, &big);
        assert_eq!(result.len(), 1_000_000);
        assert_eq!(result[0], 0);
        assert_eq!(result[999_999], 1_999_998);
    }

    // --- map_cps ---
    #[test]
    fn cps_empty() {
        assert_eq!(map_cps(&|x: &i32| x * 2, &[]), Vec::<i32>::new());
    }

    #[test]
    fn cps_single() {
        assert_eq!(map_cps(&|x: &i32| x + 1, &[5]), vec![6]);
    }

    #[test]
    fn cps_multiple() {
        assert_eq!(map_cps(&|x: &i32| x * 2, &[1, 2, 3, 4]), vec![2, 4, 6, 8]);
    }

    #[test]
    fn cps_preserves_order() {
        assert_eq!(map_cps(&|x: &i32| *x, &[10, 20, 30]), vec![10, 20, 30]);
    }

    // --- map_idiomatic ---
    #[test]
    fn idiomatic_empty() {
        assert_eq!(map_idiomatic(|x: &i32| x * 2, &[]), Vec::<i32>::new());
    }

    #[test]
    fn idiomatic_single() {
        assert_eq!(map_idiomatic(|x: &i32| x + 1, &[5]), vec![6]);
    }

    #[test]
    fn idiomatic_multiple() {
        assert_eq!(
            map_idiomatic(|x: &i32| x * 2, &[1, 2, 3, 4]),
            vec![2, 4, 6, 8]
        );
    }

    #[test]
    fn idiomatic_type_transform() {
        assert_eq!(
            map_idiomatic(|x: &i32| x.to_string(), &[1, 2, 3]),
            vec!["1", "2", "3"]
        );
    }

    #[test]
    fn idiomatic_large_input() {
        let big: Vec<i32> = (0..1_000_000).collect();
        let result = map_idiomatic(|x: &i32| x * 2, &big);
        assert_eq!(result.len(), 1_000_000);
        assert_eq!(result[0], 0);
        assert_eq!(result[999_999], 1_999_998);
    }

    // --- Cross-implementation consistency ---
    #[test]
    fn all_implementations_agree() {
        let input = [1, 2, 3, 4, 5];
        let f = |x: &i32| x * x;
        let expected = vec![1, 4, 9, 16, 25];
        assert_eq!(map_naive(&f, &input), expected);
        assert_eq!(map_acc(&f, &input), expected);
        assert_eq!(map_cps(&f, &input), expected);
        assert_eq!(map_idiomatic(f, &input), expected);
    }
}

(* Naive map — not tail-recursive, stack overflow on large lists *)
let rec map_naive f = function
  | [] -> []
  | h :: t -> f h :: map_naive f t

(* Tail-recursive with reverse — accumulates in reverse, then flips *)
let map_tr f lst =
  let rec go acc = function
    | [] -> List.rev acc
    | h :: t -> go (f h :: acc) t
  in go [] lst

(* CPS — tail-recursive, preserves order without reversing *)
let map_cps f lst =
  let rec go k = function
    | [] -> k []
    | h :: t -> go (fun rest -> k (f h :: rest)) t
  in go Fun.id lst

(* Tests *)
let () =
  (* Basic functionality *)
  assert (map_naive (fun x -> x * 2) [1;2;3;4] = [2;4;6;8]);
  assert (map_tr (fun x -> x * 2) [1;2;3;4] = [2;4;6;8]);
  assert (map_cps (fun x -> x * 2) [1;2;3;4] = [2;4;6;8]);

  (* Empty list *)
  assert (map_naive (fun x -> x + 1) [] = []);
  assert (map_tr (fun x -> x + 1) [] = []);
  assert (map_cps (fun x -> x + 1) [] = []);

  (* Single element *)
  assert (map_naive (fun x -> x + 1) [5] = [6]);
  assert (map_tr (fun x -> x + 1) [5] = [6]);
  assert (map_cps (fun x -> x + 1) [5] = [6]);

  (* Large input — only tail-recursive versions survive *)
  let big = List.init 1_000_000 Fun.id in
  let result = map_tr (fun x -> x * 2) big in
  assert (List.length result = 1_000_000);
  assert (List.hd result = 0);
  assert (List.nth result 999_999 = 1_999_998);

  let result_cps = map_cps (fun x -> x * 2) big in
  assert (List.length result_cps = 1_000_000);
  assert (List.hd result_cps = 0);

  print_endline "ok"

✓ Tests Rust test suite

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

    // --- map_naive ---
    #[test]
    fn naive_empty() {
        assert_eq!(map_naive(&|x: &i32| x * 2, &[]), Vec::<i32>::new());
    }

    #[test]
    fn naive_single() {
        assert_eq!(map_naive(&|x: &i32| x + 1, &[5]), vec![6]);
    }

    #[test]
    fn naive_multiple() {
        assert_eq!(map_naive(&|x: &i32| x * 2, &[1, 2, 3, 4]), vec![2, 4, 6, 8]);
    }

    #[test]
    fn naive_strings() {
        let words = ["hello", "world"];
        assert_eq!(
            map_naive(&|s: &&str| s.to_uppercase(), &words),
            vec!["HELLO", "WORLD"]
        );
    }

    // --- map_acc ---
    #[test]
    fn acc_empty() {
        assert_eq!(map_acc(&|x: &i32| x * 2, &[]), Vec::<i32>::new());
    }

    #[test]
    fn acc_single() {
        assert_eq!(map_acc(&|x: &i32| x + 1, &[5]), vec![6]);
    }

    #[test]
    fn acc_multiple() {
        assert_eq!(map_acc(&|x: &i32| x * 2, &[1, 2, 3, 4]), vec![2, 4, 6, 8]);
    }

    #[test]
    fn acc_preserves_order() {
        assert_eq!(map_acc(&|x: &i32| *x, &[10, 20, 30]), vec![10, 20, 30]);
    }

    #[test]
    fn acc_large_input() {
        let big: Vec<i32> = (0..1_000_000).collect();
        let result = map_acc(&|x: &i32| x * 2, &big);
        assert_eq!(result.len(), 1_000_000);
        assert_eq!(result[0], 0);
        assert_eq!(result[999_999], 1_999_998);
    }

    // --- map_cps ---
    #[test]
    fn cps_empty() {
        assert_eq!(map_cps(&|x: &i32| x * 2, &[]), Vec::<i32>::new());
    }

    #[test]
    fn cps_single() {
        assert_eq!(map_cps(&|x: &i32| x + 1, &[5]), vec![6]);
    }

    #[test]
    fn cps_multiple() {
        assert_eq!(map_cps(&|x: &i32| x * 2, &[1, 2, 3, 4]), vec![2, 4, 6, 8]);
    }

    #[test]
    fn cps_preserves_order() {
        assert_eq!(map_cps(&|x: &i32| *x, &[10, 20, 30]), vec![10, 20, 30]);
    }

    // --- map_idiomatic ---
    #[test]
    fn idiomatic_empty() {
        assert_eq!(map_idiomatic(|x: &i32| x * 2, &[]), Vec::<i32>::new());
    }

    #[test]
    fn idiomatic_single() {
        assert_eq!(map_idiomatic(|x: &i32| x + 1, &[5]), vec![6]);
    }

    #[test]
    fn idiomatic_multiple() {
        assert_eq!(
            map_idiomatic(|x: &i32| x * 2, &[1, 2, 3, 4]),
            vec![2, 4, 6, 8]
        );
    }

    #[test]
    fn idiomatic_type_transform() {
        assert_eq!(
            map_idiomatic(|x: &i32| x.to_string(), &[1, 2, 3]),
            vec!["1", "2", "3"]
        );
    }

    #[test]
    fn idiomatic_large_input() {
        let big: Vec<i32> = (0..1_000_000).collect();
        let result = map_idiomatic(|x: &i32| x * 2, &big);
        assert_eq!(result.len(), 1_000_000);
        assert_eq!(result[0], 0);
        assert_eq!(result[999_999], 1_999_998);
    }

    // --- Cross-implementation consistency ---
    #[test]
    fn all_implementations_agree() {
        let input = [1, 2, 3, 4, 5];
        let f = |x: &i32| x * x;
        let expected = vec![1, 4, 9, 16, 25];
        assert_eq!(map_naive(&f, &input), expected);
        assert_eq!(map_acc(&f, &input), expected);
        assert_eq!(map_cps(&f, &input), expected);
        assert_eq!(map_idiomatic(f, &input), expected);
    }
}

Deep Comparison

OCaml vs Rust: Tail-Recursive Map with CPS

Side-by-Side Code

OCaml

(* Naive — not tail-recursive *)
let rec map_naive f = function
  | [] -> []
  | h :: t -> f h :: map_naive f t

(* Tail-recursive with accumulator + reverse *)
let map_tr f lst =
  let rec go acc = function
    | [] -> List.rev acc
    | h :: t -> go (f h :: acc) t
  in go [] lst

(* CPS — tail-recursive, preserves order *)
let map_cps f lst =
  let rec go k = function
    | [] -> k []
    | h :: t -> go (fun rest -> k (f h :: rest)) t
  in go Fun.id lst

Rust (idiomatic)

pub fn map_idiomatic<T, U, F: Fn(&T) -> U>(f: F, list: &[T]) -> Vec<U> {
    list.iter().map(f).collect()
}

Rust (accumulator loop — equivalent of OCaml's tail-recursive version)

pub fn map_acc<T, U, F: Fn(&T) -> U>(f: &F, list: &[T]) -> Vec<U> {
    let mut acc = Vec::with_capacity(list.len());
    for item in list {
        acc.push(f(item));
    }
    acc
}

Rust (CPS with boxed closures)

pub fn map_cps<T, U, F: Fn(&T) -> U>(f: &F, list: &[T]) -> Vec<U> {
    let mut cont: Box<dyn FnOnce(Vec<U>) -> Vec<U>> = Box::new(|v| v);
    for item in list.iter().rev() {
        let mapped = f(item);
        let prev = cont;
        cont = Box::new(move |mut rest: Vec<U>| {
            rest.push(mapped);
            prev(rest)
        });
    }
    cont(Vec::new())
}

Type Signatures

Concept	OCaml	Rust
Naive map	`val map_naive : ('a -> 'b) -> 'a list -> 'b list`	`fn map_naive<T, U, F: Fn(&T) -> U>(f: &F, list: &[T]) -> Vec<U>`
Accumulator map	`val map_tr : ('a -> 'b) -> 'a list -> 'b list`	`fn map_acc<T, U, F: Fn(&T) -> U>(f: &F, list: &[T]) -> Vec<U>`
CPS map	`val map_cps : ('a -> 'b) -> 'a list -> 'b list`	`fn map_cps<T, U, F: Fn(&T) -> U>(f: &F, list: &[T]) -> Vec<U>`
Continuation type	`'b list -> 'b list` (implicit)	`Box<dyn FnOnce(Vec<U>) -> Vec<U>>` (explicit heap allocation)
List type	`'a list` (singly-linked, immutable)	`&[T]` input / `Vec<U>` output (contiguous, mutable)

Key Insights

TCO is the fundamental difference. OCaml guarantees tail-call optimization, making structural recursion with an accumulator genuinely stack-safe. Rust does not — the same recursive structure still grows the call stack. Rust's equivalent is an explicit loop.

Cons vs push inverts accumulation order. OCaml's :: prepends to a linked list in O(1), naturally building in reverse. That's why List.rev is needed at the end. Rust's Vec::push appends in O(1) amortized, building in forward order — the reverse step disappears entirely.

Continuations require explicit heap allocation in Rust. OCaml closures are lightweight GC-managed values — building a chain of continuations is cheap. In Rust, each continuation must be Box<dyn FnOnce(...)>, requiring a heap allocation per list element. This makes CPS a poor fit for performance-sensitive Rust code.

CPS in Rust is educational, not practical. Applying the continuation chain still involves O(n) nested function calls (each continuation calls the previous one), so it can still overflow. The technique demonstrates the concept but doesn't solve the stack-safety problem the way it does in OCaml.

Iterator chains are Rust's zero-cost abstraction for this pattern. iter().map(f).collect() is the idiomatic Rust solution — it compiles to a tight loop with no recursion, no heap-allocated closures, and no intermediate allocations beyond the output Vec.

When to Use Each Style

**Use the accumulator loop (map_acc) when:** you need an explicit loop body with complex logic that doesn't fit a single closure — e.g., conditional mapping, stateful transforms, or early termination.

**Use CPS (map_cps) when:** you're teaching or studying continuation-passing style. It's valuable for understanding how OCaml achieves tail recursion through continuations, but it's not the right tool for production Rust.

**Use idiomatic Rust (map_idiomatic) when:** this is the default choice. Iterator chains are the Rust way — zero-cost, composable, and optimized by the compiler.

Exercises

Rewrite filter in CPS style so it is tail-recursive without relying on Rust's stack; verify it handles a list of 100,000 elements without stack overflow.

Implement fold_left using CPS transformation, then compare its performance to the direct iterative version on a list of one million integers.

Combine CPS-style map and filter into a single CPS filter_map that applies a T -> Option<U> function and collects Some results, avoiding intermediate allocations.

Open Source Repos

functional-rust

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

Rust