1217 Intermediate GitHub

List Fold Left — Accumulate a Result

ListsHOF

Tutorial

The Problem

Walk a list left-to-right, threading an accumulator through a combining function f : 'acc -> 'elt -> 'acc, and return the final accumulator. Classic applications: sum, product, and building a labelled string from a list of integers.

🎯 Learning Outcomes

• Translating List.fold_left to Rust's Iterator::fold combinator.

• Seeing why the accumulator is passed by value and returned (pure fold), not mutated in place.

• How OCaml's operator-as-function ((+), ( * )) becomes a Rust closure |acc, x| acc + x.

• Left vs right associativity: subtraction and string concatenation both expose the direction.

• Tail-recursive pattern matching as a mirror of let rec fold_left f acc = function ....

🦀 The Rust Way

Rust exposes the same shape as Iterator::fold(init, f). The closure takes the accumulator by value and returns the new one, so the type A need not be Copy or Clone. For specialised cases (sum, product) the stdlib iterator adapters already exist, but the generic fold is the direct translation. A slice pattern match ([] | [h, rest @ ..]) mirrors the OCaml recursive definition exactly, and the recursive call stays in tail position.

Code Example

pub fn fold_left<T, A, F>(f: F, init: A, items: &[T]) -> A
where
    F: Fn(A, &T) -> A,
{
    items.iter().fold(init, f)
}

// usage
let numbers = [1, 2, 3, 4, 5];
let sum     = fold_left(|acc, x| acc + x, 0, &numbers);
let product = fold_left(|acc, x| acc * x, 1, &numbers);
let concat  = fold_left(
    |acc: String, x| acc + " " + &x.to_string(),
    String::from("Numbers:"),
    &numbers,
);

let numbers = [1; 2; 3; 4; 5]

let sum     = List.fold_left (+) 0 numbers
let product = List.fold_left ( * ) 1 numbers
let concat  =
  List.fold_left
    (fun acc x -> acc ^ " " ^ string_of_int x)
    "Numbers:"
    numbers

(* Explicit recursive definition — what the stdlib does internally *)
let rec fold_left f acc = function
  | [] -> acc
  | x :: xs -> fold_left f (f acc x) xs

Key Differences

Accumulator ownership: OCaml passes a value; Rust also passes A by value — the closure returns the new accumulator, so nothing is mutated aliasing-wise.

Operators as functions: OCaml writes (+) and ( * ); Rust must wrap them in closures |acc, x| acc + x.

String building: OCaml's ^ copies; Rust prefers String + &str or String::push_str to avoid extra allocations.

Tail recursion: OCaml guarantees TCO; Rust does not, so fold (which loops internally) is preferred over the recursive variant for long lists.

OCaml Approach

List.fold_left f init lst starts with init and applies f successively to the running accumulator and the next element: f (f (f init x1) x2) x3. Operators curry and can be passed as values ((+)), so List.fold_left (+) 0 is already a summing function. List.fold_left is implemented tail-recursively in the stdlib, so it runs in constant stack space.

Full Source

#![allow(dead_code)]
//! `List.fold_left` — accumulate a result by walking a list left-to-right.
//!
//! Given a combining function `f : 'acc -> 'elt -> 'acc`, a seed
//! `init : 'acc`, and a list `[x1; x2; ...; xn]`, fold_left computes
//! `f (... (f (f init x1) x2) ...) xn`.
//!
//! Three Rust translations are shown:
//!   * idiomatic iterator chain using `Iterator::fold`,
//!   * explicit pattern-matched recursion (closest to OCaml),
//!   * a plain `for` loop with a mutable accumulator (imperative baseline).
//!
//! The combining function takes the accumulator **by value** and returns a
//! new one, mirroring OCaml's pure fold rather than a mutate-in-place
//! `for_each`.

/// Idiomatic Rust: `iter().fold(init, f)`.
///
/// `Iterator::fold` is the exact structural analogue of OCaml's
/// `List.fold_left`.  The closure consumes the accumulator and an element
/// reference and returns the new accumulator.
pub fn fold_left<T, A, F>(f: F, init: A, items: &[T]) -> A
where
    F: Fn(A, &T) -> A,
{
    items.iter().fold(init, f)
}

/// Functional / recursive translation — the direct OCaml parallel.
/// Matches on the slice shape `[] | [h, rest @ ..]`, mirroring
/// `let rec fold_left f acc = function [] -> acc | x :: xs -> ...`.
///
/// Note the tail-recursive shape: the recursive call is the outermost
/// expression, so an optimising compiler can reuse the stack frame.
pub fn fold_left_recursive<T, A, F>(f: &F, acc: A, items: &[T]) -> A
where
    F: Fn(A, &T) -> A,
{
    match items {
        [] => acc,
        [h, rest @ ..] => fold_left_recursive(f, f(acc, h), rest),
    }
}

/// Imperative translation — explicit mutable accumulator and `for` loop.
/// Clippy will normally push you towards `fold`, but this form makes the
/// "left-to-right threading of state" visible for pedagogy.
pub fn fold_left_loop<T, A, F>(f: F, init: A, items: &[T]) -> A
where
    F: Fn(A, &T) -> A,
{
    let mut acc = init;
    for x in items {
        acc = f(acc, x);
    }
    acc
}

// --- Concrete applications matching the OCaml example -------------------

/// Sum of a slice of integers — `List.fold_left (+) 0 numbers`.
pub fn sum(numbers: &[i32]) -> i32 {
    fold_left(|acc, x| acc + x, 0, numbers)
}

/// Product of a slice of integers — `List.fold_left ( * ) 1 numbers`.
pub fn product(numbers: &[i32]) -> i32 {
    fold_left(|acc, x| acc * x, 1, numbers)
}

/// Concatenate integers into a labelled string — mirrors the OCaml
/// `fold_left (fun acc x -> acc ^ " " ^ string_of_int x) "Numbers:" numbers`.
pub fn concat_labelled(label: &str, numbers: &[i32]) -> String {
    fold_left(
        |acc, x| acc + " " + &x.to_string(),
        label.to_string(),
        numbers,
    )
}

/// Reverse a slice via fold — the canonical demonstration that `fold_left`
/// can build structure, not just reduce to a scalar.
/// Equivalent to `List.fold_left (fun acc x -> x :: acc) [] lst`.
pub fn reverse<T: Copy>(items: &[T]) -> Vec<T> {
    fold_left(
        |mut acc, x| {
            acc.insert(0, *x);
            acc
        },
        Vec::new(),
        items,
    )
}

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

    const NUMBERS: &[i32] = &[1, 2, 3, 4, 5];

    // --- generic fold_left --------------------------------------------

    #[test]
    fn test_fold_left_sum_empty() {
        let empty: [i32; 0] = [];
        assert_eq!(fold_left(|acc, x| acc + x, 0, &empty), 0);
    }

    #[test]
    fn test_fold_left_sum_single() {
        assert_eq!(fold_left(|acc, x| acc + x, 0, &[7]), 7);
    }

    #[test]
    fn test_fold_left_sum_many() {
        assert_eq!(fold_left(|acc, x| acc + x, 0, NUMBERS), 15);
    }

    #[test]
    fn test_fold_left_product() {
        assert_eq!(fold_left(|acc, x| acc * x, 1, NUMBERS), 120);
    }

    #[test]
    fn test_fold_left_order_is_left_to_right() {
        // subtraction is not associative — left fold computes
        // ((((0 - 1) - 2) - 3) - 4) - 5 = -15
        assert_eq!(fold_left(|acc, x| acc - x, 0, NUMBERS), -15);
    }

    #[test]
    fn test_fold_left_with_non_commutative_concat() {
        // String concatenation exposes fold direction.
        let out = fold_left(|acc, x: &&str| acc + x, String::from("<"), &["a", "b", "c"]);
        assert_eq!(out, "<abc");
    }

    // --- concrete helpers ---------------------------------------------

    #[test]
    fn test_sum_helper() {
        assert_eq!(sum(NUMBERS), 15);
        assert_eq!(sum(&[]), 0);
    }

    #[test]
    fn test_product_helper() {
        assert_eq!(product(NUMBERS), 120);
        assert_eq!(product(&[]), 1);
    }

    #[test]
    fn test_concat_labelled_matches_ocaml() {
        assert_eq!(concat_labelled("Numbers:", NUMBERS), "Numbers: 1 2 3 4 5");
    }

    #[test]
    fn test_concat_labelled_empty_numbers() {
        assert_eq!(concat_labelled("Numbers:", &[]), "Numbers:");
    }

    #[test]
    fn test_reverse_via_fold() {
        assert_eq!(reverse(NUMBERS), vec![5, 4, 3, 2, 1]);
        assert_eq!(reverse::<i32>(&[]), Vec::<i32>::new());
    }

    // --- recursive variant --------------------------------------------

    #[test]
    fn test_fold_left_recursive_sum() {
        assert_eq!(fold_left_recursive(&|acc, x| acc + x, 0, NUMBERS), 15);
    }

    #[test]
    fn test_fold_left_recursive_empty() {
        let empty: [i32; 0] = [];
        assert_eq!(fold_left_recursive(&|acc, x| acc + x, 42, &empty), 42);
    }

    // --- loop variant -------------------------------------------------

    #[test]
    fn test_fold_left_loop_product() {
        assert_eq!(fold_left_loop(|acc, x| acc * x, 1, NUMBERS), 120);
    }

    // --- cross-check --------------------------------------------------

    #[test]
    fn test_all_implementations_agree() {
        let a = fold_left(|acc, x| acc - x, 100, NUMBERS);
        let b = fold_left_recursive(&|acc, x| acc - x, 100, NUMBERS);
        let c = fold_left_loop(|acc, x| acc - x, 100, NUMBERS);
        assert_eq!(a, b);
        assert_eq!(b, c);
        assert_eq!(a, 85);
    }
}

(* Idiomatic OCaml — List.fold_left accumulates left-to-right *)
let numbers = [1; 2; 3; 4; 5]

let sum = List.fold_left (+) 0 numbers
let product = List.fold_left ( * ) 1 numbers
let concat =
  List.fold_left
    (fun acc x -> acc ^ " " ^ string_of_int x)
    "Numbers:"
    numbers

(* Recursive OCaml — explicit fold_left, tail-recursive *)
let rec fold_left_rec f acc = function
  | [] -> acc
  | x :: xs -> fold_left_rec f (f acc x) xs

let () =
  assert (sum = 15);
  assert (product = 120);
  assert (concat = "Numbers: 1 2 3 4 5");
  assert (fold_left_rec (+) 0 numbers = 15);
  assert (List.fold_left (-) 0 numbers = -15);
  Printf.printf "Sum: %d\n" sum;
  Printf.printf "Product: %d\n" product;
  Printf.printf "%s\n" concat;
  print_endline "ok"

✓ Tests Rust test suite

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

    const NUMBERS: &[i32] = &[1, 2, 3, 4, 5];

    // --- generic fold_left --------------------------------------------

    #[test]
    fn test_fold_left_sum_empty() {
        let empty: [i32; 0] = [];
        assert_eq!(fold_left(|acc, x| acc + x, 0, &empty), 0);
    }

    #[test]
    fn test_fold_left_sum_single() {
        assert_eq!(fold_left(|acc, x| acc + x, 0, &[7]), 7);
    }

    #[test]
    fn test_fold_left_sum_many() {
        assert_eq!(fold_left(|acc, x| acc + x, 0, NUMBERS), 15);
    }

    #[test]
    fn test_fold_left_product() {
        assert_eq!(fold_left(|acc, x| acc * x, 1, NUMBERS), 120);
    }

    #[test]
    fn test_fold_left_order_is_left_to_right() {
        // subtraction is not associative — left fold computes
        // ((((0 - 1) - 2) - 3) - 4) - 5 = -15
        assert_eq!(fold_left(|acc, x| acc - x, 0, NUMBERS), -15);
    }

    #[test]
    fn test_fold_left_with_non_commutative_concat() {
        // String concatenation exposes fold direction.
        let out = fold_left(|acc, x: &&str| acc + x, String::from("<"), &["a", "b", "c"]);
        assert_eq!(out, "<abc");
    }

    // --- concrete helpers ---------------------------------------------

    #[test]
    fn test_sum_helper() {
        assert_eq!(sum(NUMBERS), 15);
        assert_eq!(sum(&[]), 0);
    }

    #[test]
    fn test_product_helper() {
        assert_eq!(product(NUMBERS), 120);
        assert_eq!(product(&[]), 1);
    }

    #[test]
    fn test_concat_labelled_matches_ocaml() {
        assert_eq!(concat_labelled("Numbers:", NUMBERS), "Numbers: 1 2 3 4 5");
    }

    #[test]
    fn test_concat_labelled_empty_numbers() {
        assert_eq!(concat_labelled("Numbers:", &[]), "Numbers:");
    }

    #[test]
    fn test_reverse_via_fold() {
        assert_eq!(reverse(NUMBERS), vec![5, 4, 3, 2, 1]);
        assert_eq!(reverse::<i32>(&[]), Vec::<i32>::new());
    }

    // --- recursive variant --------------------------------------------

    #[test]
    fn test_fold_left_recursive_sum() {
        assert_eq!(fold_left_recursive(&|acc, x| acc + x, 0, NUMBERS), 15);
    }

    #[test]
    fn test_fold_left_recursive_empty() {
        let empty: [i32; 0] = [];
        assert_eq!(fold_left_recursive(&|acc, x| acc + x, 42, &empty), 42);
    }

    // --- loop variant -------------------------------------------------

    #[test]
    fn test_fold_left_loop_product() {
        assert_eq!(fold_left_loop(|acc, x| acc * x, 1, NUMBERS), 120);
    }

    // --- cross-check --------------------------------------------------

    #[test]
    fn test_all_implementations_agree() {
        let a = fold_left(|acc, x| acc - x, 100, NUMBERS);
        let b = fold_left_recursive(&|acc, x| acc - x, 100, NUMBERS);
        let c = fold_left_loop(|acc, x| acc - x, 100, NUMBERS);
        assert_eq!(a, b);
        assert_eq!(b, c);
        assert_eq!(a, 85);
    }
}

Deep Comparison

OCaml vs Rust: List Fold Left (accumulate a result)

Side-by-Side Code

OCaml

let numbers = [1; 2; 3; 4; 5]

let sum     = List.fold_left (+) 0 numbers
let product = List.fold_left ( * ) 1 numbers
let concat  =
  List.fold_left
    (fun acc x -> acc ^ " " ^ string_of_int x)
    "Numbers:"
    numbers

(* Explicit recursive definition — what the stdlib does internally *)
let rec fold_left f acc = function
  | [] -> acc
  | x :: xs -> fold_left f (f acc x) xs

Rust (idiomatic)

pub fn fold_left<T, A, F>(f: F, init: A, items: &[T]) -> A
where
    F: Fn(A, &T) -> A,
{
    items.iter().fold(init, f)
}

// usage
let numbers = [1, 2, 3, 4, 5];
let sum     = fold_left(|acc, x| acc + x, 0, &numbers);
let product = fold_left(|acc, x| acc * x, 1, &numbers);
let concat  = fold_left(
    |acc: String, x| acc + " " + &x.to_string(),
    String::from("Numbers:"),
    &numbers,
);

Rust (functional / recursive)

pub fn fold_left_recursive<T, A, F>(f: &F, acc: A, items: &[T]) -> A
where
    F: Fn(A, &T) -> A,
{
    match items {
        [] => acc,
        [h, rest @ ..] => fold_left_recursive(f, f(acc, h), rest),
    }
}

Type Signatures

Concept	OCaml	Rust
`fold_left` signature	`val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a`	`fn fold_left<T, A, F: Fn(A, &T) -> A>(F, A, &[T]) -> A`
Combiner	`'a -> 'b -> 'a`	`F: Fn(A, &T) -> A`
Initial accumulator	`'a`	`A` (owned, passed and returned by value)
List	`'b list`	`&[T]`
Operator literal	`(+)`, `( * )`	closure: `\|acc, x\| acc + x`

Key Insights

**List.fold_left ↔ Iterator::fold** — identical semantics: threads an accumulator left-to-right and returns the final value. The stdlib implementation of Iterator::fold is already a tight while let loop.

Accumulator passed by value — both languages treat the accumulator as a value (A), not a reference. This is why fold composes cleanly with immutable data: each step returns the new accumulator rather than mutating one in place.

Operators-as-functions — OCaml can write (+) and pass it directly; Rust has no "operator as value" syntax, so you wrap it in |a, b| a + b. Named helpers like i32::saturating_add can be passed by path, but arithmetic operators cannot.

Direction matters — fold_left vs fold_right gives different results for non-associative operations. fold_left (-) 0 [1;2;3;4;5] is -15; switching to fold_right yields 3. Rust only exposes fold (left); right-fold requires .rev().fold(...) on a DoubleEndedIterator.

Borrowing elements — OCaml passes list elements by value (they are boxed/immutable); Rust's .iter() yields &T, so the closure takes (A, &T) -> A. When T: Copy, the closure can dereference; otherwise, work with the reference.

When to Use Each Style

Use idiomatic Rust when: you want constant stack use on long slices, or when composing with other iterator adapters (filter, map, take_while). Iterator::fold inlines aggressively and is the right default.

Use recursive Rust when: you're teaching the OCaml → Rust correspondence, or the input is a genuinely recursive structure (binary trees, cons-lists) where slice indexing doesn't apply. Beware: Rust does not guarantee TCO, so recursive folds can blow the stack on long lists.

Open Source Repos

functional-rust

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

Rust