1002 Intermediate

1002 — List Fold Left

Functional Programming

Tutorial

The Problem

Implement fold_left — the left-to-right accumulator fold — both as a thin wrapper around Iterator::fold and as an explicit tail-recursive function. Compute sum, product, and maximum from a list using the same fold abstraction. Compare with OCaml's List.fold_left and a custom tail-recursive implementation.

🎯 Learning Outcomes

• Use items.iter().fold(init, f) as the idiomatic Rust fold

• Implement fold_left_recursive using slice pattern [head, tail @ ..] for educational comparison

• Understand that fold_left is left-associative: ((init ⊕ x₁) ⊕ x₂) ⊕ …

• Derive sum, product, and max as specialisations of fold_left

• Map Rust's Iterator::fold to OCaml's List.fold_left f init lst

• Recognise that Rust's iterative fold is always tail-recursive; OCaml's recursive version needs manual TCO

Code Example

fn main() {
    let numbers = vec![1, 2, 3, 4, 5];
    
    // Iterator-based fold_left (idiomatic)
    let sum = numbers.iter().fold(0, |acc, x| acc + x);
    let product = numbers.iter().fold(1, |acc, x| acc * x);
    let max_val = numbers.iter().fold(i32::MIN, |acc, x| if x > &acc { *x } else { acc });
    
    println!("Sum: {}, Product: {}, Max: {}", sum, product, max_val);
}

(* Data and basic operations *)
let numbers = [1; 2; 3; 4; 5]
let sum = List.fold_left ( + ) 0 numbers
let product = List.fold_left ( * ) 1 numbers
let max_val = List.fold_left max min_int numbers

(* Output *)
let () = Printf.printf "Sum: %d, Product: %d, Max: %d\n" sum product max_val

Key Differences

Aspect	Rust	OCaml
Idiomatic	`iter.fold(init, f)`	`List.fold_left f init lst`
Argument order	`f(accumulator, item)`	`f acc item`
Item type	`&T` (reference from `iter()`)	`T` (value from list)
Tail recursion	Always (iterative)	TCO by compiler
Partial application	Not idiomatic (closure)	`let sum = List.fold_left (+) 0`
Max with empty	Requires `Option<U>` or sentinel	Same pattern

fold_left is the universal list combinator: map, filter, sum, product, reverse, length — all are expressible as fold_left. Understanding it deeply is the foundation of functional list processing.

OCaml Approach

List.fold_left (+) 0 numbers is the standard library call. The custom fold_left_recursive f acc = function | [] -> acc | head :: tail -> fold_left_recursive f (f acc head) tail is tail-recursive and gets TCO by OCaml's compiler. Convenience functions sum and product are partial applications: let sum = List.fold_left (+) 0.

Full Source

#![allow(clippy::all)]
//! # List Fold Left
//!
//! Demonstrates reducing a list to a single value using left-to-right folding.
//! This example shows both iterator-based and recursive approaches in Rust.

/// Fold left using iterators (idiomatic Rust approach).
///
/// Applies a binary operation cumulatively from left to right,
/// starting with an initial accumulator value.
///
/// # Arguments
/// * `init` - Initial accumulator value
/// * `items` - Slice of items to fold
/// * `f` - Binary operation: (accumulator, item) -> accumulator
///
/// # Example
/// ```
/// use list_fold_left::fold_left_iter;
///
/// let numbers = vec![1, 2, 3, 4, 5];
/// let sum = fold_left_iter(0, &numbers, |acc, x| acc + x);
/// assert_eq!(sum, 15);
/// ```
pub fn fold_left_iter<T, U, F>(init: U, items: &[T], f: F) -> U
where
    F: Fn(U, &T) -> U,
{
    items.iter().fold(init, f)
}

/// Fold left using recursion (functional style, like OCaml).
///
/// Tail-recursive implementation that manually processes the list.
/// The compiler may optimize this into a loop.
///
/// # Arguments
/// * `init` - Initial accumulator value
/// * `items` - Slice of items to fold
/// * `f` - Binary operation: (accumulator, item) -> accumulator
///
/// # Example
/// ```
/// use list_fold_left::fold_left_recursive;
///
/// let numbers = vec![1, 2, 3, 4, 5];
/// let sum = fold_left_recursive(0, &numbers, |acc, x| acc + x);
/// assert_eq!(sum, 15);
/// ```
pub fn fold_left_recursive<T, U, F>(init: U, items: &[T], f: F) -> U
where
    F: Fn(U, &T) -> U,
{
    match items {
        [] => init,
        [head, tail @ ..] => fold_left_recursive(f(init, head), tail, f),
    }
}

/// Calculate the sum of a list.
///
/// # Example
/// ```
/// use list_fold_left::sum;
/// assert_eq!(sum(&[1, 2, 3, 4, 5]), 15);
/// ```
pub fn sum(items: &[i32]) -> i32 {
    fold_left_iter(0, items, |acc, x| acc + x)
}

/// Calculate the product of a list.
///
/// # Example
/// ```
/// use list_fold_left::product;
/// assert_eq!(product(&[1, 2, 3, 4, 5]), 120);
/// ```
pub fn product(items: &[i32]) -> i32 {
    fold_left_iter(1, items, |acc, x| acc * x)
}

/// Find the maximum value in a list.
///
/// Returns `i32::MIN` if the list is empty (matching OCaml's min_int).
///
/// # Example
/// ```
/// use list_fold_left::max_value;
/// assert_eq!(max_value(&[1, 5, 3, 2, 4]), 5);
/// ```
pub fn max_value(items: &[i32]) -> i32 {
    fold_left_iter(i32::MIN, items, |acc, x| if x > &acc { *x } else { acc })
}

/// Find the minimum value in a list.
///
/// Returns `i32::MAX` if the list is empty.
///
/// # Example
/// ```
/// use list_fold_left::min_value;
/// assert_eq!(min_value(&[1, 5, 3, 2, 4]), 1);
/// ```
pub fn min_value(items: &[i32]) -> i32 {
    fold_left_iter(i32::MAX, items, |acc, x| if x < &acc { *x } else { acc })
}

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

    #[test]
    fn test_fold_left_iter_sum() {
        let numbers = vec![1, 2, 3, 4, 5];
        assert_eq!(fold_left_iter(0, &numbers, |acc, x| acc + x), 15);
    }

    #[test]
    fn test_fold_left_iter_product() {
        let numbers = vec![1, 2, 3, 4, 5];
        assert_eq!(fold_left_iter(1, &numbers, |acc, x| acc * x), 120);
    }

    #[test]
    fn test_fold_left_iter_max() {
        let numbers = vec![1, 5, 3, 2, 4];
        assert_eq!(
            fold_left_iter(i32::MIN, &numbers, |acc, x| if x > &acc { *x } else { acc }),
            5
        );
    }

    #[test]
    fn test_fold_left_iter_empty() {
        let empty: Vec<i32> = vec![];
        assert_eq!(fold_left_iter(0, &empty, |acc, x| acc + x), 0);
        assert_eq!(fold_left_iter(1, &empty, |acc, x| acc * x), 1);
    }

    #[test]
    fn test_fold_left_iter_single() {
        let single = vec![42];
        assert_eq!(fold_left_iter(0, &single, |acc, x| acc + x), 42);
        assert_eq!(fold_left_iter(1, &single, |acc, x| acc * x), 42);
    }

    #[test]
    fn test_fold_left_recursive_sum() {
        let numbers = vec![1, 2, 3, 4, 5];
        assert_eq!(fold_left_recursive(0, &numbers, |acc, x| acc + x), 15);
    }

    #[test]
    fn test_fold_left_recursive_product() {
        let numbers = vec![1, 2, 3, 4, 5];
        assert_eq!(fold_left_recursive(1, &numbers, |acc, x| acc * x), 120);
    }

    #[test]
    fn test_fold_left_recursive_max() {
        let numbers = vec![1, 5, 3, 2, 4];
        assert_eq!(
            fold_left_recursive(i32::MIN, &numbers, |acc, x| if x > &acc { *x } else { acc }),
            5
        );
    }

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

    #[test]
    fn test_fold_left_recursive_single() {
        let single = vec![42];
        assert_eq!(fold_left_recursive(0, &single, |acc, x| acc + x), 42);
    }

    #[test]
    fn test_sum() {
        assert_eq!(sum(&[1, 2, 3, 4, 5]), 15);
        assert_eq!(sum(&[]), 0);
        assert_eq!(sum(&[42]), 42);
        assert_eq!(sum(&[-5, 10, -3]), 2);
    }

    #[test]
    fn test_product() {
        assert_eq!(product(&[1, 2, 3, 4, 5]), 120);
        assert_eq!(product(&[]), 1);
        assert_eq!(product(&[42]), 42);
        assert_eq!(product(&[2, 3, 4]), 24);
    }

    #[test]
    fn test_max_value() {
        assert_eq!(max_value(&[1, 5, 3, 2, 4]), 5);
        assert_eq!(max_value(&[]), i32::MIN);
        assert_eq!(max_value(&[42]), 42);
        assert_eq!(max_value(&[-5, -1, -10]), -1);
    }

    #[test]
    fn test_min_value() {
        assert_eq!(min_value(&[1, 5, 3, 2, 4]), 1);
        assert_eq!(min_value(&[]), i32::MAX);
        assert_eq!(min_value(&[42]), 42);
        assert_eq!(min_value(&[-5, -1, -10]), -10);
    }

    #[test]
    fn test_fold_left_iter_string_concat() {
        let words = vec!["Hello", " ", "World"];
        let result = fold_left_iter(String::new(), &words, |acc, word| acc + word);
        assert_eq!(result, "Hello World");
    }

    #[test]
    fn test_fold_left_recursive_string_concat() {
        let words = vec!["Hello", " ", "World"];
        let result = fold_left_recursive(String::new(), &words, |acc, word| acc + word);
        assert_eq!(result, "Hello World");
    }
}

(* List fold_left in OCaml
 * Demonstrates the standard library's List.fold_left and a custom recursive implementation
 *)

(* Standard library approach using List.fold_left *)
let fold_left_stdlib numbers =
  let sum = List.fold_left ( + ) 0 numbers in
  let product = List.fold_left ( * ) 1 numbers in
  let max_val = List.fold_left max min_int numbers in
  (sum, product, max_val)

(* Custom recursive implementation (like fold_left does internally) *)
let rec fold_left_recursive f acc = function
  | [] -> acc
  | head :: tail -> fold_left_recursive f (f acc head) tail

let fold_left_custom numbers =
  let sum = fold_left_recursive ( + ) 0 numbers in
  let product = fold_left_recursive ( * ) 1 numbers in
  let max_val = fold_left_recursive max min_int numbers in
  (sum, product, max_val)

(* Convenience functions *)
let sum numbers = List.fold_left ( + ) 0 numbers
let product numbers = List.fold_left ( * ) 1 numbers
let max_value numbers = List.fold_left max min_int numbers
let min_value numbers = List.fold_left min max_int numbers

(* Test with assertions *)
let () =
  let numbers = [1; 2; 3; 4; 5] in

  (* Test standard library *)
  let (sum_std, prod_std, max_std) = fold_left_stdlib numbers in
  Printf.printf "=== Standard library fold_left ===\n";
  Printf.printf "Sum: %d, Product: %d, Max: %d\n" sum_std prod_std max_std;
  assert (sum_std = 15);
  assert (prod_std = 120);
  assert (max_std = 5);

  (* Test custom recursive *)
  let (sum_rec, prod_rec, max_rec) = fold_left_custom numbers in
  Printf.printf "\n=== Custom recursive fold_left ===\n";
  Printf.printf "Sum: %d, Product: %d, Max: %d\n" sum_rec prod_rec max_rec;
  assert (sum_rec = 15);
  assert (prod_rec = 120);
  assert (max_rec = 5);

  (* Test convenience functions *)
  Printf.printf "\n=== Convenience functions ===\n";
  Printf.printf "Sum: %d, Product: %d, Max: %d\n" (sum numbers) (product numbers) (max_value numbers);
  assert (sum numbers = 15);
  assert (product numbers = 120);
  assert (max_value numbers = 5);

  (* Test edge cases *)
  Printf.printf "\n=== Edge cases ===\n";
  let empty = [] in
  Printf.printf "Empty list - sum: %d, product: %d, max: %d\n" (sum empty) (product empty) (max_value empty);
  assert (sum empty = 0);
  assert (product empty = 1);
  assert (max_value empty = min_int);

  let single = [42] in
  Printf.printf "Single element [42] - sum: %d, product: %d, max: %d\n" (sum single) (product single) (max_value single);
  assert (sum single = 42);
  assert (product single = 42);
  assert (max_value single = 42);

  let negative = [-5; 10; -3] in
  Printf.printf "Negative values [-5; 10; -3] - sum: %d, product: %d, max: %d\n" (sum negative) (product negative) (max_value negative);
  assert (sum negative = 2);
  assert (product negative = 150);
  assert (max_value negative = 10);

  Printf.printf "\n✓ All assertions passed!\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_fold_left_iter_sum() {
        let numbers = vec![1, 2, 3, 4, 5];
        assert_eq!(fold_left_iter(0, &numbers, |acc, x| acc + x), 15);
    }

    #[test]
    fn test_fold_left_iter_product() {
        let numbers = vec![1, 2, 3, 4, 5];
        assert_eq!(fold_left_iter(1, &numbers, |acc, x| acc * x), 120);
    }

    #[test]
    fn test_fold_left_iter_max() {
        let numbers = vec![1, 5, 3, 2, 4];
        assert_eq!(
            fold_left_iter(i32::MIN, &numbers, |acc, x| if x > &acc { *x } else { acc }),
            5
        );
    }

    #[test]
    fn test_fold_left_iter_empty() {
        let empty: Vec<i32> = vec![];
        assert_eq!(fold_left_iter(0, &empty, |acc, x| acc + x), 0);
        assert_eq!(fold_left_iter(1, &empty, |acc, x| acc * x), 1);
    }

    #[test]
    fn test_fold_left_iter_single() {
        let single = vec![42];
        assert_eq!(fold_left_iter(0, &single, |acc, x| acc + x), 42);
        assert_eq!(fold_left_iter(1, &single, |acc, x| acc * x), 42);
    }

    #[test]
    fn test_fold_left_recursive_sum() {
        let numbers = vec![1, 2, 3, 4, 5];
        assert_eq!(fold_left_recursive(0, &numbers, |acc, x| acc + x), 15);
    }

    #[test]
    fn test_fold_left_recursive_product() {
        let numbers = vec![1, 2, 3, 4, 5];
        assert_eq!(fold_left_recursive(1, &numbers, |acc, x| acc * x), 120);
    }

    #[test]
    fn test_fold_left_recursive_max() {
        let numbers = vec![1, 5, 3, 2, 4];
        assert_eq!(
            fold_left_recursive(i32::MIN, &numbers, |acc, x| if x > &acc { *x } else { acc }),
            5
        );
    }

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

    #[test]
    fn test_fold_left_recursive_single() {
        let single = vec![42];
        assert_eq!(fold_left_recursive(0, &single, |acc, x| acc + x), 42);
    }

    #[test]
    fn test_sum() {
        assert_eq!(sum(&[1, 2, 3, 4, 5]), 15);
        assert_eq!(sum(&[]), 0);
        assert_eq!(sum(&[42]), 42);
        assert_eq!(sum(&[-5, 10, -3]), 2);
    }

    #[test]
    fn test_product() {
        assert_eq!(product(&[1, 2, 3, 4, 5]), 120);
        assert_eq!(product(&[]), 1);
        assert_eq!(product(&[42]), 42);
        assert_eq!(product(&[2, 3, 4]), 24);
    }

    #[test]
    fn test_max_value() {
        assert_eq!(max_value(&[1, 5, 3, 2, 4]), 5);
        assert_eq!(max_value(&[]), i32::MIN);
        assert_eq!(max_value(&[42]), 42);
        assert_eq!(max_value(&[-5, -1, -10]), -1);
    }

    #[test]
    fn test_min_value() {
        assert_eq!(min_value(&[1, 5, 3, 2, 4]), 1);
        assert_eq!(min_value(&[]), i32::MAX);
        assert_eq!(min_value(&[42]), 42);
        assert_eq!(min_value(&[-5, -1, -10]), -10);
    }

    #[test]
    fn test_fold_left_iter_string_concat() {
        let words = vec!["Hello", " ", "World"];
        let result = fold_left_iter(String::new(), &words, |acc, word| acc + word);
        assert_eq!(result, "Hello World");
    }

    #[test]
    fn test_fold_left_recursive_string_concat() {
        let words = vec!["Hello", " ", "World"];
        let result = fold_left_recursive(String::new(), &words, |acc, word| acc + word);
        assert_eq!(result, "Hello World");
    }
}

Deep Comparison

Comparison: OCaml vs Rust - Fold Left

Side-by-Side Code Comparison

The Original OCaml Example

(* Data and basic operations *)
let numbers = [1; 2; 3; 4; 5]
let sum = List.fold_left ( + ) 0 numbers
let product = List.fold_left ( * ) 1 numbers
let max_val = List.fold_left max min_int numbers

(* Output *)
let () = Printf.printf "Sum: %d, Product: %d, Max: %d\n" sum product max_val

The Rust Iterator Equivalent

fn main() {
    let numbers = vec![1, 2, 3, 4, 5];
    
    // Iterator-based fold_left (idiomatic)
    let sum = numbers.iter().fold(0, |acc, x| acc + x);
    let product = numbers.iter().fold(1, |acc, x| acc * x);
    let max_val = numbers.iter().fold(i32::MIN, |acc, x| if x > &acc { *x } else { acc });
    
    println!("Sum: {}, Product: {}, Max: {}", sum, product, max_val);
}

The Rust Recursive Equivalent

fn fold_left_recursive<T, U, F>(init: U, items: &[T], f: F) -> U
where
    F: Fn(U, &T) -> U,
{
    match items {
        [] => init,
        [head, tail @ ..] => fold_left_recursive(f(init, head), tail, f),
    }
}

fn main() {
    let numbers = vec![1, 2, 3, 4, 5];
    
    // Recursive fold_left (functional style)
    let sum = fold_left_recursive(0, &numbers, |acc, x| acc + x);
    let product = fold_left_recursive(1, &numbers, |acc, x| acc * x);
    let max_val = fold_left_recursive(i32::MIN, &numbers, |acc, x| if x > &acc { *x } else { acc });
    
    println!("Sum: {}, Product: {}, Max: {}", sum, product, max_val);
}

Type Signatures Table

Operation	OCaml	Rust (Iterator)	Rust (Recursive)
Sum	`int list -> int`	`fn(Vec<i32>) -> i32`	`fn(U, &[T], Fn(U, &T)->U) -> U`
Generic Fold	`('a -> 'b -> 'a) -> 'a -> 'b list -> 'a`	`fn<T,U,F>(U, &[T], F)->U where F:Fn(U,&T)->U`	Same as iterator
Max	`(int -> int -> int) -> int -> int list -> int`	`fn(i32::MIN, &[i32], \\|acc, x\\| ...) -> i32`	Same as iterator

Key Insights

1. Currying vs Direct Application

OCaml embraces currying:

List.fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

Each arrow represents a curried parameter. You can partially apply:

let fold_add = List.fold_left ( + )
let sum = fold_add 0 numbers

Rust uses direct function application:

fn fold_left_iter<T, U, F>(init: U, items: &[T], f: F) -> U

All parameters at once. Closures capture context naturally:

let init = 0;
let result = fold_left_iter(init, &numbers, |acc, x| acc + x);

Winner: OCaml is more elegant for composition, but Rust's approach is more explicit and easier to read for newcomers.

2. Memory Model Impact

OCaml:

• Lists are immutable linked lists

• Each recursive call traverses one cons cell

• Garbage collection handles cleanup

• No lifetime annotations needed

Rust:

fn fold_left_recursive<T, U, F>(init: U, items: &[T], f: F) -> U {
    match items {
        [] => init,
        [head, tail @ ..] => fold_left_recursive(f(init, head), tail, f),
    }
}

• Slices provide zero-copy views into arrays

• Stack grows with recursion depth (no TCO guarantee!)

• Lifetimes ensure F and T don't outlive data

• No garbage collection needed

Winner: Rust is more efficient for large arrays thanks to slices. OCaml is safer from stack overflow due to list structure.

3. Operator Overloading vs Explicit Syntax

OCaml:

List.fold_left ( + ) 0 numbers   (* Treat + as a function *)
List.fold_left max min_int numbers  (* Use max builtin directly *)

Rust:

fold_left_iter(0, &numbers, |acc, x| acc + x)  (* Must write closure *)
fold_left_iter(i32::MIN, &numbers, |acc, x| if x > &acc { *x } else { acc })

Winner: OCaml is concise. Rust is explicit (which some find clearer, especially beginners).

4. Generic Type Constraints

OCaml:

let fold_left f init xs = List.fold_left f init xs
(* Type checker infers: 'a -> 'b -> 'a *)
(* Works with ANY types *)

Rust:

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

• T = element type

• U = accumulator type (can differ from T)

• F = closure type with trait bound Fn(U, &T) -> U

• All constraints explicit in the signature

Winner: Rust wins on clarity—you see exactly what types are involved and what the function expects.

5. Tail Call Optimization (TCO)

OCaml:

let rec fold_left f acc = function
  | [] -> acc
  | head :: tail -> fold_left f (f acc head) tail

This is guaranteed tail-recursive. The recursive call is in tail position, so OCaml (and most Lisp/Scheme implementations) optimize it to a loop.

Rust:

match items {
    [] => init,
    [head, tail @ ..] => fold_left_recursive(f(init, head), tail, f),
}

This is tail-recursive in structure but Rust makes NO GUARANTEE of TCO. The compiler may optimize it, but:

• For large lists, this could overflow the stack

• items.iter().fold() is always loop-compiled and safe

Winner: OCaml wins on predictability. Rust wins on practical safety (use iterators!).

Performance Implications

Iterator-Based (Rust)

• Pros: Zero-copy, compiled to loop, cache-friendly, no stack overflow risk

• Cons: Slightly more verbose syntax

• Best for: Large lists, performance-critical code

Recursive (Both Languages)

• OCaml Pros: Guaranteed TCO, elegant pattern matching

• OCaml Cons: Linked list traversal is cache-unfriendly

• Rust Pros: Shows functional style, clear semantics

• Rust Cons: Stack risk, no TCO guarantee

• Best for: Learning, small lists, composition patterns

Summary: When to Use Each

Scenario	Language	Approach	Reason
Large arrays (>10K)	Rust	Iterator	Stack-safe, cache-friendly
Beautiful code	OCaml	fold_left	Concise, elegant
Learning recursion	Rust	Recursive	Explicit pattern matching
Production system	Rust	Iterator	Predictable performance
Functional composition	OCaml	Standard lib	Currying + pipelines
Type-safe pipelines	Rust	Closures + chains	Iterator adapters

Both languages excel at expressing fold operations. OCaml is more concise; Rust is more explicit and safer for large-scale data processing.

Exercises

Implement map using fold_left_iter by collecting transformed elements into a Vec.

Implement filter using fold_left_iter by conditionally appending to the accumulator.

Implement reverse using fold_left_iter with a Vec accumulator using insert(0, ...).

Write fold_right (right-associative fold) and show that fold_right cons [] lst reconstructs the list.

In OCaml, implement List.fold_left from scratch without using the standard library version, then verify it matches List.fold_left on 10 example inputs.

Open Source Repos

functional-rust

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

Rust