057 Intermediate

fold_left — Tail-Recursive Accumulator

Higher-Order Functions

Tutorial Video

Text description (accessibility)

This video demonstrates the "fold_left — Tail-Recursive Accumulator" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Higher-Order Functions. Implement `fold_left`, the tail-recursive fold that processes a list left to right with an accumulator: `fold_left f init [a; b; c] = f (f (f init a) b) c`. Key difference from OCaml: 1. **TCO:** OCaml guarantees tail

Tutorial

The Problem

Implement fold_left, the tail-recursive fold that processes a list left to right with an accumulator: fold_left f init [a; b; c] = f (f (f init a) b) c. Use it to implement sum, product, maximum, and reverse.

🎯 Learning Outcomes

• Understand fold_left as a tail-recursive accumulator pattern

• See why fold_left is stack-safe for large lists (tail recursion)

• Map OCaml's fold_left to Rust's Iterator::fold

• Implement reverse using fold_left (classic trick)

• Compare fold_left vs fold_right evaluation order

🦀 The Rust Way

Idiomatic: iter().sum(), iter().product(), iter().max(), .reverse()

Functional: Custom fold_left function using a for loop (Rust doesn't guarantee TCO)

Iterator::fold: Rust's built-in left fold — iter().fold(init, |acc, x| ...)

Code Example

pub fn sum_idiomatic(xs: &[i64]) -> i64 { xs.iter().sum() }
pub fn product_idiomatic(xs: &[i64]) -> i64 { xs.iter().product() }
pub fn maximum_idiomatic(xs: &[i64]) -> Option<i64> { xs.iter().copied().max() }
pub fn reverse_idiomatic(xs: &[i64]) -> Vec<i64> {
    let mut v = xs.to_vec();
    v.reverse();
    v
}

let rec fold_left f acc = function
  | []     -> acc
  | h :: t -> fold_left f (f acc h) t

let sum     lst = fold_left ( + ) 0 lst
let product lst = fold_left ( * ) 1 lst
let maximum lst = fold_left max (List.hd lst) (List.tl lst)
let reverse lst = fold_left (fun acc x -> x :: acc) [] lst

Key Differences

TCO: OCaml guarantees tail-call optimization; Rust does not, so our "recursive" fold_left uses an iterative loop

Maximum safety: OCaml's maximum panics on empty list (List.hd); Rust returns Option<T>

Mutability: Rust's fold accumulator is moved on each step (ownership transfer); OCaml's is copied/shared

Specialization: Rust's .sum() and .product() use traits (Sum, Product) for type-safe folding

Reverse: OCaml reverses by consing (x :: acc); Rust can reverse in-place with .reverse() (O(1) extra space)

Accumulator pattern: fold_left is the direct encoding of the accumulator pattern — instead of returning from the base case and building the result on the way up, it carries the result forward as an argument.

Tail recursive: Because the recursive call is in tail position (fold_left f (f acc head) tail), OCaml can optimize this to a loop. Rust's iter.fold() is already implemented as a loop — no recursion.

Universal: fold_left can implement map, filter, reverse, length, and sum — it is computationally complete for list operations. Understanding this demonstrates the power of the abstraction.

Non-commutative order: fold_left (+) 0 [1;2;3] = ((0+1)+2)+3 = 6. For addition it doesn't matter, but for subtraction: fold_left (-) 0 [1;2;3] = ((0-1)-2)-3 = -6 vs fold_right (-) [1;2;3] 0 = 1-(2-(3-0)) = 2.

OCaml Approach

OCaml's fold_left is tail-recursive — the recursive call is in tail position, so the compiler can optimize it to a loop. This makes it safe for arbitrarily large lists, unlike fold_right.

Full Source

#![allow(clippy::all)]
//! # fold_left — Tail-Recursive Accumulator
//!
//! OCaml's `fold_left` processes a list left to right with an accumulator:
//!   fold_left f init [a; b; c] = f (f (f init a) b) c
//!
//! This is tail-recursive in OCaml (and maps directly to Rust's `Iterator::fold`).

// ---------------------------------------------------------------------------
// Approach A: Idiomatic Rust — iterator methods
// ---------------------------------------------------------------------------

pub fn sum_idiomatic(xs: &[i64]) -> i64 {
    xs.iter().sum()
}

pub fn product_idiomatic(xs: &[i64]) -> i64 {
    xs.iter().product()
}

/// Maximum element. Returns `None` for empty slices.
/// Uses `iter().copied().max()` which returns `Option<i64>`.
pub fn maximum_idiomatic(xs: &[i64]) -> Option<i64> {
    // Unlike OCaml's version which panics on empty list, we return Option
    xs.iter().copied().max()
}

pub fn reverse_idiomatic(xs: &[i64]) -> Vec<i64> {
    let mut v = xs.to_vec();
    v.reverse();
    v
}

// ---------------------------------------------------------------------------
// Approach B: Functional / explicit fold_left (recursive, tail-recursive style)
// ---------------------------------------------------------------------------

/// A generic left fold mirroring OCaml's `fold_left`.
///
/// Rust doesn't guarantee TCO, but the structure is identical to OCaml's
/// tail-recursive fold_left. For large inputs, the iterative version is safer.
pub fn fold_left<T, A>(f: impl Fn(A, &T) -> A, mut acc: A, xs: &[T]) -> A {
    for x in xs {
        acc = f(acc, x);
    }
    acc
}

pub fn sum_functional(xs: &[i64]) -> i64 {
    fold_left(|acc, &x| acc + x, 0, xs)
}

pub fn product_functional(xs: &[i64]) -> i64 {
    fold_left(|acc, &x| acc * x, 1, xs)
}

pub fn maximum_functional(xs: &[i64]) -> Option<i64> {
    // Safe version: use first element as initial accumulator
    let (&first, rest) = xs.split_first()?;
    Some(fold_left(
        |acc, &x| if x > acc { x } else { acc },
        first,
        rest,
    ))
}

pub fn reverse_functional(xs: &[i64]) -> Vec<i64> {
    // Mirrors OCaml: fold_left (fun acc x -> x :: acc) [] lst
    fold_left(
        |mut acc: Vec<i64>, &x| {
            acc.push(x); // push + final reverse, or insert(0, x) like OCaml's cons
            acc
        },
        Vec::new(),
        xs,
    )
    .into_iter()
    .rev()
    .collect()
}

// ---------------------------------------------------------------------------
// Approach C: Iterator::fold — Rust's built-in left fold
// ---------------------------------------------------------------------------

/// Sum using Iterator::fold — explicitly showing the fold call.
/// We add a type annotation to show fold's signature clearly.
pub fn sum_iter_fold(xs: &[i64]) -> i64 {
    xs.iter().copied().fold(0i64, i64::wrapping_add)
}

/// Product using Iterator::fold.
pub fn product_iter_fold(xs: &[i64]) -> i64 {
    xs.iter().copied().fold(1i64, i64::wrapping_mul)
}

pub fn reverse_iter_fold(xs: &[i64]) -> Vec<i64> {
    // fold left, prepending each element
    xs.iter().fold(Vec::new(), |mut acc, &x| {
        acc.insert(0, x);
        acc
    })
}

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

    #[test]
    fn test_sum_basic() {
        let xs = [3, 1, 4, 1, 5, 9, 2, 6];
        assert_eq!(sum_idiomatic(&xs), 31);
        assert_eq!(sum_functional(&xs), 31);
        assert_eq!(sum_iter_fold(&xs), 31);
    }

    #[test]
    fn test_sum_empty() {
        let xs: &[i64] = &[];
        assert_eq!(sum_idiomatic(xs), 0);
        assert_eq!(sum_functional(xs), 0);
        assert_eq!(sum_iter_fold(xs), 0);
    }

    #[test]
    fn test_product_single() {
        let xs = [7];
        assert_eq!(product_idiomatic(&xs), 7);
        assert_eq!(product_functional(&xs), 7);
        assert_eq!(product_iter_fold(&xs), 7);
    }

    #[test]
    fn test_product_basic() {
        let xs = [3, 1, 4, 1, 5, 9, 2, 6];
        assert_eq!(product_idiomatic(&xs), 6480);
        assert_eq!(product_functional(&xs), 6480);
        assert_eq!(product_iter_fold(&xs), 6480);
    }

    #[test]
    fn test_maximum() {
        let xs = [3, 1, 4, 1, 5, 9, 2, 6];
        assert_eq!(maximum_idiomatic(&xs), Some(9));
        assert_eq!(maximum_functional(&xs), Some(9));
    }

    #[test]
    fn test_maximum_empty() {
        let xs: &[i64] = &[];
        assert_eq!(maximum_idiomatic(xs), None);
        assert_eq!(maximum_functional(xs), None);
    }

    #[test]
    fn test_maximum_single() {
        assert_eq!(maximum_idiomatic(&[42]), Some(42));
        assert_eq!(maximum_functional(&[42]), Some(42));
    }

    #[test]
    fn test_reverse() {
        let xs = [3, 1, 4, 1, 5, 9, 2, 6];
        let expected = vec![6, 2, 9, 5, 1, 4, 1, 3];
        assert_eq!(reverse_idiomatic(&xs), expected);
        assert_eq!(reverse_functional(&xs), expected);
        assert_eq!(reverse_iter_fold(&xs), expected);
    }

    #[test]
    fn test_reverse_empty() {
        let xs: &[i64] = &[];
        let empty: Vec<i64> = vec![];
        assert_eq!(reverse_idiomatic(xs), empty);
        assert_eq!(reverse_functional(xs), empty);
        assert_eq!(reverse_iter_fold(xs), empty);
    }

    #[test]
    fn test_fold_left_generic() {
        // Build a string: "((init+3)+1)+4"
        let xs = [3, 1, 4];
        let result = fold_left(|acc, x| format!("({acc}+{x})"), "init".to_string(), &xs);
        assert_eq!(result, "(((init+3)+1)+4)");
    }
}

(* fold_left — Tail-Recursive Accumulator *)

(* Implementation 1: Direct tail-recursive fold_left *)
let rec fold_left f acc = function
  | []     -> acc
  | h :: t -> fold_left f (f acc h) t

(* Implementation 2: Using List.fold_left from stdlib *)
let fold_left_stdlib f acc lst = List.fold_left f acc lst

(* Classic uses *)
let sum     lst = fold_left ( + ) 0 lst
let product lst = fold_left ( * ) 1 lst
let maximum lst = fold_left max (List.hd lst) (List.tl lst)
let reverse lst = fold_left (fun acc x -> x :: acc) [] lst

(* Tests *)
let () =
  let nums = [3; 1; 4; 1; 5; 9; 2; 6] in
  assert (sum nums = 31);
  assert (product nums = 6480);
  assert (maximum nums = 9);
  assert (reverse [1; 2; 3] = [3; 2; 1]);
  assert (sum [] = 0);
  assert (reverse [] = []);
  Printf.printf "All fold_left tests passed!\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_sum_basic() {
        let xs = [3, 1, 4, 1, 5, 9, 2, 6];
        assert_eq!(sum_idiomatic(&xs), 31);
        assert_eq!(sum_functional(&xs), 31);
        assert_eq!(sum_iter_fold(&xs), 31);
    }

    #[test]
    fn test_sum_empty() {
        let xs: &[i64] = &[];
        assert_eq!(sum_idiomatic(xs), 0);
        assert_eq!(sum_functional(xs), 0);
        assert_eq!(sum_iter_fold(xs), 0);
    }

    #[test]
    fn test_product_single() {
        let xs = [7];
        assert_eq!(product_idiomatic(&xs), 7);
        assert_eq!(product_functional(&xs), 7);
        assert_eq!(product_iter_fold(&xs), 7);
    }

    #[test]
    fn test_product_basic() {
        let xs = [3, 1, 4, 1, 5, 9, 2, 6];
        assert_eq!(product_idiomatic(&xs), 6480);
        assert_eq!(product_functional(&xs), 6480);
        assert_eq!(product_iter_fold(&xs), 6480);
    }

    #[test]
    fn test_maximum() {
        let xs = [3, 1, 4, 1, 5, 9, 2, 6];
        assert_eq!(maximum_idiomatic(&xs), Some(9));
        assert_eq!(maximum_functional(&xs), Some(9));
    }

    #[test]
    fn test_maximum_empty() {
        let xs: &[i64] = &[];
        assert_eq!(maximum_idiomatic(xs), None);
        assert_eq!(maximum_functional(xs), None);
    }

    #[test]
    fn test_maximum_single() {
        assert_eq!(maximum_idiomatic(&[42]), Some(42));
        assert_eq!(maximum_functional(&[42]), Some(42));
    }

    #[test]
    fn test_reverse() {
        let xs = [3, 1, 4, 1, 5, 9, 2, 6];
        let expected = vec![6, 2, 9, 5, 1, 4, 1, 3];
        assert_eq!(reverse_idiomatic(&xs), expected);
        assert_eq!(reverse_functional(&xs), expected);
        assert_eq!(reverse_iter_fold(&xs), expected);
    }

    #[test]
    fn test_reverse_empty() {
        let xs: &[i64] = &[];
        let empty: Vec<i64> = vec![];
        assert_eq!(reverse_idiomatic(xs), empty);
        assert_eq!(reverse_functional(xs), empty);
        assert_eq!(reverse_iter_fold(xs), empty);
    }

    #[test]
    fn test_fold_left_generic() {
        // Build a string: "((init+3)+1)+4"
        let xs = [3, 1, 4];
        let result = fold_left(|acc, x| format!("({acc}+{x})"), "init".to_string(), &xs);
        assert_eq!(result, "(((init+3)+1)+4)");
    }
}

Deep Comparison

Comparison: fold_left — OCaml vs Rust

OCaml — Tail-Recursive

let rec fold_left f acc = function
  | []     -> acc
  | h :: t -> fold_left f (f acc h) t

let sum     lst = fold_left ( + ) 0 lst
let product lst = fold_left ( * ) 1 lst
let maximum lst = fold_left max (List.hd lst) (List.tl lst)
let reverse lst = fold_left (fun acc x -> x :: acc) [] lst

Rust — Idiomatic

pub fn sum_idiomatic(xs: &[i64]) -> i64 { xs.iter().sum() }
pub fn product_idiomatic(xs: &[i64]) -> i64 { xs.iter().product() }
pub fn maximum_idiomatic(xs: &[i64]) -> Option<i64> { xs.iter().copied().max() }
pub fn reverse_idiomatic(xs: &[i64]) -> Vec<i64> {
    let mut v = xs.to_vec();
    v.reverse();
    v
}

Rust — Functional (Custom fold_left)

pub fn fold_left<T, A>(f: impl Fn(A, &T) -> A, mut acc: A, xs: &[T]) -> A {
    for x in xs { acc = f(acc, x); }
    acc
}

pub fn maximum_functional(xs: &[i64]) -> Option<i64> {
    let (&first, rest) = xs.split_first()?;
    Some(fold_left(|acc, &x| if x > acc { x } else { acc }, first, rest))
}

Comparison Table

Aspect	OCaml	Rust
Type signature	`('b -> 'a -> 'b) -> 'b -> 'a list -> 'b`	`fn fold_left<T, A>(f: Fn(A, &T) -> A, acc: A, xs: &[T]) -> A`
Tail-call optimization	Guaranteed by compiler	Not guaranteed (we use a loop instead)
Empty list max	`List.hd` raises exception	Returns `None` (safe)
Reverse mechanism	Cons to front: `x :: acc`	`v.reverse()` in-place or `insert(0, x)`
Built-in	`List.fold_left`	`Iterator::fold`
Accumulator	Passed by value (GC'd)	Moved by ownership

Type Signatures Explained

OCaml: val fold_left : ('b -> 'a -> 'b) -> 'b -> 'a list -> 'b

• Accumulator type 'b comes first in the function parameter

• The accumulator is threaded through each recursive call

Rust: fn fold_left<T, A>(f: impl Fn(A, &T) -> A, acc: A, xs: &[T]) -> A

• A is the accumulator type, T is the element type

• &T: elements are borrowed from the slice

• mut acc: the accumulator is mutably rebound on each iteration

Takeaways

fold_left is Rust's natural fold — Iterator::fold processes left to right, matching fold_left's semantics exactly

Safety improvement: Rust's maximum returns Option instead of panicking on empty input

No TCO needed: Rust's for loop is already iterative — no tail-call optimization concern

Ownership makes fold natural — the accumulator is moved into each step, not shared

**OCaml's function keyword** combines fun + match; Rust uses match explicitly or for loops

Exercises

Implement running_sum using fold_left that returns a Vec of prefix sums (e.g., [1,2,3] → [1,3,6]).

Use fold_left to implement group_by_first_char that builds a HashMap<char, Vec<String>> grouping strings by their first character.

Implement a left fold over a binary tree (not a list) and use it to compute the sum of all node values; compare with a right fold version and explain the traversal order difference.

Running maximum: Use fold_left to compute the running maximum of a list — at each step, the accumulator is the maximum seen so far. Return both the final maximum and the position where it first occurred.

Grouping via fold: Implement group_by<T: Clone, K: Eq + Hash>(list: &[T], key: impl Fn(&T) -> K) -> HashMap<K, Vec<T>> using a single fold call — no loops, no explicit iteration.

Open Source Repos

functional-rust

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

Rust