List.fold_left — Accumulate a Result
Functional Programming
Tutorial
The Problem
Use List.fold_left to reduce a list of integers into a single accumulated result: sum, product, and maximum. Implement a generic fold_left that mirrors OCaml's standard library function signature, and demonstrate how the same fold pattern expresses all three computations by varying only the combining function and the initial accumulator value.
🎯 Learning Outcomes
List.fold_left f acc xs maps directly to Rust's Iterator::fold(init, f) — same argument order, same semantics, different syntaxfold_left (+) 0 [1;2;3] computes ((0+1)+2)+3( + ), ( * ), max) pass built-in operators as first-class functions, and how Rust uses closures to achieve the same effectmax_val uses reduce (fold without an initial value) returning Option<i64> rather than fold with i64::MIN — the Option makes the empty-list case explicit and type-safefold_left<T, U, F> signature in Rust expresses the same higher-kinded abstraction as OCaml's polymorphic List.fold_leftCode Example
pub fn sum_idiomatic(numbers: &[i64]) -> i64 {
numbers.iter().copied().sum()
}
pub fn max_val(numbers: &[i64]) -> Option<i64> {
numbers.iter().copied().reduce(i64::max)
}Key Differences
( + ) to lift an infix operator into a first-class two-argument function; Rust uses explicit closures |acc, &x| acc + x — more verbose but unambiguous about argument types and bindingList.fold_left max min_int uses min_int as the identity (always returns a valid integer); Rust's reduce returns None for an empty slice, surfacing the absence case in the type rather than hiding it behind a sentinel valuefold_left f acc list; Rust: fold(init, |acc, x| ...) — the accumulator comes first in both, then the combining function in Rust's closure; the conceptual mapping is 1:1'a list); Rust uses contiguous slices (&[T]), which allows bounds-checked random access and is cache-friendly, but the fold abstraction looks identical from the caller's perspectiveOCaml Approach
OCaml's standard library exports List.fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a, a tail-recursive left fold. Operator sections like ( + ) and ( * ) are the addition and multiplication operators in prefix position, usable as any other two-argument function. List.fold_left max min_int numbers passes the built-in max function directly; min_int serves as the identity element for the maximum operation over integers. All three computations in example.ml are single expressions — the composability of fold_left with first-class operators is the key idiomatic feature.
Full Source
#![allow(dead_code)]
//! List.fold_left — Accumulate a Result
//! See example.ml for OCaml reference
//!
//! OCaml's `List.fold_left f acc xs` applies `f acc x` for each element left-to-right,
//! threading the accumulator through. Rust's `Iterator::fold` is the direct equivalent.
/// Generic left fold — mirrors OCaml's `List.fold_left f acc xs`.
/// Threads `init` through every element using `f`.
pub fn fold_left<T, U, F>(items: &[T], init: U, f: F) -> U
where
F: Fn(U, &T) -> U,
{
items.iter().fold(init, f)
}
/// Idiomatic Rust: sum using the specialized `.sum()` adapter.
/// More efficient than a manual fold; Rust knows how to optimize it.
pub fn sum_idiomatic(numbers: &[i64]) -> i64 {
numbers.iter().copied().sum()
}
/// Idiomatic Rust: product using the specialized `.product()` adapter.
pub fn product_idiomatic(numbers: &[i64]) -> i64 {
numbers.iter().copied().product()
}
/// Functional style: sum via an explicit fold, mirroring OCaml's `List.fold_left (+) 0 xs`.
pub fn sum_fold(numbers: &[i64]) -> i64 {
fold_left(numbers, 0, |acc, &x| acc + x)
}
/// Functional style: product via an explicit fold, mirroring OCaml's `List.fold_left (*) 1 xs`.
pub fn product_fold(numbers: &[i64]) -> i64 {
fold_left(numbers, 1, |acc, &x| acc * x)
}
/// Find the maximum value. Returns `None` for an empty slice.
/// Uses `Iterator::reduce` (fold without a seed) so the empty case is explicit in the type.
pub fn max_val(numbers: &[i64]) -> Option<i64> {
numbers.iter().copied().reduce(i64::max)
}
/// Recursive fold: mirrors OCaml's `let rec fold_left_rec f acc = function ...`
pub fn fold_left_recursive<T, U, F>(items: &[T], acc: U, f: &F) -> U
where
F: Fn(U, &T) -> U,
{
match items {
[] => acc,
[head, rest @ ..] => {
let new_acc = f(acc, head);
fold_left_recursive(rest, new_acc, f)
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_sum_empty() {
assert_eq!(sum_idiomatic(&[]), 0);
assert_eq!(sum_fold(&[]), 0);
}
#[test]
fn test_sum_single() {
assert_eq!(sum_idiomatic(&[42]), 42);
assert_eq!(sum_fold(&[42]), 42);
}
#[test]
fn test_sum_multiple() {
assert_eq!(sum_idiomatic(&[1, 2, 3, 4, 5]), 15);
assert_eq!(sum_fold(&[1, 2, 3, 4, 5]), 15);
}
#[test]
fn test_product_multiple() {
assert_eq!(product_idiomatic(&[1, 2, 3, 4, 5]), 120);
assert_eq!(product_fold(&[1, 2, 3, 4, 5]), 120);
}
#[test]
fn test_max_val() {
assert_eq!(max_val(&[3, 1, 4, 1, 5, 9, 2, 6]), Some(9));
assert_eq!(max_val(&[]), None);
}
#[test]
fn test_fold_left_string_build() {
let words = ["hello", " ", "world"];
let result = fold_left(&words, String::new(), |acc, s| acc + s);
assert_eq!(result, "hello world");
}
#[test]
fn test_fold_left_count_evens() {
let nums = [1, 2, 3, 4, 5, 6_i64];
let evens = fold_left(&nums, 0, |acc, &x| if x % 2 == 0 { acc + 1 } else { acc });
assert_eq!(evens, 3);
}
#[test]
fn test_fold_left_recursive_sum() {
let numbers = [1_i64, 2, 3, 4, 5];
let result = fold_left_recursive(&numbers, 0, &|acc, &x| acc + x);
assert_eq!(result, 15);
}
}
✓ Tests
Rust test suite
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_sum_empty() {
assert_eq!(sum_idiomatic(&[]), 0);
assert_eq!(sum_fold(&[]), 0);
}
#[test]
fn test_sum_single() {
assert_eq!(sum_idiomatic(&[42]), 42);
assert_eq!(sum_fold(&[42]), 42);
}
#[test]
fn test_sum_multiple() {
assert_eq!(sum_idiomatic(&[1, 2, 3, 4, 5]), 15);
assert_eq!(sum_fold(&[1, 2, 3, 4, 5]), 15);
}
#[test]
fn test_product_multiple() {
assert_eq!(product_idiomatic(&[1, 2, 3, 4, 5]), 120);
assert_eq!(product_fold(&[1, 2, 3, 4, 5]), 120);
}
#[test]
fn test_max_val() {
assert_eq!(max_val(&[3, 1, 4, 1, 5, 9, 2, 6]), Some(9));
assert_eq!(max_val(&[]), None);
}
#[test]
fn test_fold_left_string_build() {
let words = ["hello", " ", "world"];
let result = fold_left(&words, String::new(), |acc, s| acc + s);
assert_eq!(result, "hello world");
}
#[test]
fn test_fold_left_count_evens() {
let nums = [1, 2, 3, 4, 5, 6_i64];
let evens = fold_left(&nums, 0, |acc, &x| if x % 2 == 0 { acc + 1 } else { acc });
assert_eq!(evens, 3);
}
#[test]
fn test_fold_left_recursive_sum() {
let numbers = [1_i64, 2, 3, 4, 5];
let result = fold_left_recursive(&numbers, 0, &|acc, &x| acc + x);
assert_eq!(result, 15);
}
}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 max_val = List.fold_left max min_int numbers
let rec fold_left_rec f acc = function
| [] -> acc
| x :: rest -> fold_left_rec f (f acc x) rest
Rust (idiomatic — specialized adapters)
pub fn sum_idiomatic(numbers: &[i64]) -> i64 {
numbers.iter().copied().sum()
}
pub fn max_val(numbers: &[i64]) -> Option<i64> {
numbers.iter().copied().reduce(i64::max)
}
Rust (functional/recursive fold)
pub fn fold_left_recursive<T, U, F>(items: &[T], acc: U, f: &F) -> U
where
F: Fn(U, &T) -> U,
{
match items {
[] => acc,
[head, rest @ ..] => {
let new_acc = f(acc, head);
fold_left_recursive(rest, new_acc, f)
}
}
}
Type Signatures
| Concept | OCaml | Rust |
|---|---|---|
| fold_left | ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a | fn fold_left<T, U, F>(items: &[T], init: U, f: F) -> U |
| sum | List.fold_left ( + ) 0 xs | xs.iter().copied().sum() |
| product | List.fold_left ( * ) 1 xs | xs.iter().copied().product() |
| max | List.fold_left max min_int xs | xs.iter().copied().reduce(i64::max) |
| empty result | implicit (returns init) | None for reduce, 0 for sum |
Key Insights
( + ) is a curried function you pass directly to fold_left; Rust needs a closure |acc, &x| acc + x or uses the specialized .sum() adapter.Iterator provides .sum() and .product() as specializations that clippy prefers over manual folds; OCaml expresses both uniformly via fold_left.fold_left f init [] returns init; Rust's Iterator::reduce returns None for empty input (no initial value), while fold with an initial value behaves like OCaml.fold_left f init list; Rust iter.fold(init, f) — the method receiver is the iterator, not a standalone function.fold_left is tail-recursive in the standard library; Rust's fold is also iterative. The manual recursive Rust version risks stack overflow on very long inputs.When to Use Each Style
**Use .sum() / .product() when:** computing simple numeric aggregations — Rust's specialized adapters are clearer and potentially more efficient.
**Use .fold() when:** the accumulation logic is custom and doesn't fit a standard adapter — e.g., building a HashMap or filtering while accumulating.
Use recursive fold when: demonstrating the OCaml parallel or building educational examples that show the structural recursion explicitly.
Exercises
running_sum using fold_left that returns a Vec<i64> of prefix sums — after folding [1, 2, 3, 4] the result should be [1, 3, 6, 10]flatten using fold_left that turns a Vec<Vec<T>> into a flat Vec<T> by accumulating with extendcount_if using fold_left that counts elements satisfying a predicate fn(&T) -> bool, and verify it handles the empty-slice case correctlyfold_right (right fold) and compare its behavior on a non-associative operation like subtraction against fold_left — show that fold_right (-) [1;2;3] 0 gives a different result than fold_left (-) 0 [1;2;3]