085 Intermediate

085 — Accumulate (Custom Map)

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "085 — Accumulate (Custom Map)" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Implement a custom `accumulate` function equivalent to `map` — applying a function to every element of a list and collecting the results. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Implement a custom accumulate function equivalent to map — applying a function to every element of a list and collecting the results. Provide three versions: naive recursive, tail-recursive with an accumulator, and idiomatic iterator-based. Compare with OCaml's List.map and tail-recursive alternative.

🎯 Learning Outcomes

• Use slice pattern matching [head, tail @ ..] for destructuring in Rust

• Understand why naive recursion risks stack overflow on large inputs

• Implement tail-recursive accumulation with Vec::push + pre-allocation

• Recognise that lst.into_iter().map(f).collect() is the idiomatic Rust equivalent

• Map the OCaml tail-recursive accumulator pattern (go (f h :: acc) t) to Rust

• Compare eager list operations in OCaml with iterator laziness in Rust

Code Example

#![allow(clippy::all)]
/// Accumulate — Custom Map Implementation
///
/// Ownership: The function takes ownership of input vec and returns new vec.
/// The closure borrows or moves each element depending on the function.

/// Recursive version (not tail-recursive — will stack overflow on large inputs)
pub fn accumulate<T, U, F>(lst: &[T], f: F) -> Vec<U>
where
    F: Fn(&T) -> U,
{
    fn inner<T, U>(lst: &[T], f: &dyn Fn(&T) -> U) -> Vec<U> {
        match lst {
            [] => vec![],
            [head, tail @ ..] => {
                let mut result = vec![f(head)];
                result.extend(inner(tail, f));
                result
            }
        }
    }
    inner(lst, &f)
}

/// Tail-recursive version using accumulator
pub fn accumulate_tr<T, U, F>(lst: &[T], f: F) -> Vec<U>
where
    F: Fn(&T) -> U,
{
    let mut acc = Vec::with_capacity(lst.len());
    for item in lst {
        acc.push(f(item));
    }
    acc
}

/// Iterator-based version (most idiomatic Rust)
pub fn accumulate_iter<T, U>(lst: impl IntoIterator<Item = T>, f: impl Fn(T) -> U) -> Vec<U> {
    lst.into_iter().map(f).collect()
}

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

    #[test]
    fn test_squares() {
        assert_eq!(
            accumulate(&[1, 2, 3, 4, 5], |x| x * x),
            vec![1, 4, 9, 16, 25]
        );
    }

    #[test]
    fn test_empty() {
        assert_eq!(accumulate::<i32, i32, _>(&[], |x| x * x), Vec::<i32>::new());
    }

    #[test]
    fn test_strings() {
        let words = vec!["hello".to_string(), "world".to_string()];
        assert_eq!(
            accumulate(&words, |s| s.to_uppercase()),
            vec!["HELLO", "WORLD"]
        );
    }

    #[test]
    fn test_tail_recursive() {
        assert_eq!(accumulate_tr(&[1, 2, 3], |x| x + 10), vec![11, 12, 13]);
    }

    #[test]
    fn test_iterator_version() {
        assert_eq!(accumulate_iter(vec![1, 2, 3], |x| x * 2), vec![2, 4, 6]);
    }

    #[test]
    fn test_type_change() {
        assert_eq!(
            accumulate(&[1, 2, 3], |x| x.to_string()),
            vec!["1", "2", "3"]
        );
    }
}

(* Accumulate — Custom Map *)

(* Version 1: Simple recursive *)
let rec accumulate f = function
  | [] -> []
  | h :: t -> f h :: accumulate f t

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

let () =
  assert (accumulate (fun x -> x * x) [1;2;3;4;5] = [1;4;9;16;25]);
  assert (accumulate_tr String.uppercase_ascii ["hello";"world"] = ["HELLO";"WORLD"])

Key Differences

Aspect	Rust	OCaml
List destructuring	`[head, tail @ ..]` slice pattern	`h :: t`
Tail recursion	Iterative `push` in a loop	`go (f h :: acc) t` + `List.rev`
Idiomatic version	`.iter().map(f).collect()`	`List.map f lst`
Stack safety	Recursive version unsafe on large input	Same — `List.map` may stack overflow
Pre-allocation	`Vec::with_capacity(lst.len())`	Not possible with `list`
Ownership	`&T` in closure for borrow / `T` for move	Value semantics throughout

The recursive version illustrates how OCaml idioms translate to Rust, but the take-away is that Rust's iterator protocol handles this cleanly without recursion. Use the iterator version in production; use the recursive version only for educational comparison.

OCaml Approach

OCaml's List.map is defined recursively as f h :: accumulate f t. The tail-recursive version builds f h :: acc in reverse and calls List.rev at the end. OCaml's native List.map uses continuation-based tail calls in newer versions. The OCaml code is shorter because list cons :: is syntactic and pattern matching on lists is built into the language.

Full Source

#![allow(clippy::all)]
/// Accumulate — Custom Map Implementation
///
/// Ownership: The function takes ownership of input vec and returns new vec.
/// The closure borrows or moves each element depending on the function.

/// Recursive version (not tail-recursive — will stack overflow on large inputs)
pub fn accumulate<T, U, F>(lst: &[T], f: F) -> Vec<U>
where
    F: Fn(&T) -> U,
{
    fn inner<T, U>(lst: &[T], f: &dyn Fn(&T) -> U) -> Vec<U> {
        match lst {
            [] => vec![],
            [head, tail @ ..] => {
                let mut result = vec![f(head)];
                result.extend(inner(tail, f));
                result
            }
        }
    }
    inner(lst, &f)
}

/// Tail-recursive version using accumulator
pub fn accumulate_tr<T, U, F>(lst: &[T], f: F) -> Vec<U>
where
    F: Fn(&T) -> U,
{
    let mut acc = Vec::with_capacity(lst.len());
    for item in lst {
        acc.push(f(item));
    }
    acc
}

/// Iterator-based version (most idiomatic Rust)
pub fn accumulate_iter<T, U>(lst: impl IntoIterator<Item = T>, f: impl Fn(T) -> U) -> Vec<U> {
    lst.into_iter().map(f).collect()
}

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

    #[test]
    fn test_squares() {
        assert_eq!(
            accumulate(&[1, 2, 3, 4, 5], |x| x * x),
            vec![1, 4, 9, 16, 25]
        );
    }

    #[test]
    fn test_empty() {
        assert_eq!(accumulate::<i32, i32, _>(&[], |x| x * x), Vec::<i32>::new());
    }

    #[test]
    fn test_strings() {
        let words = vec!["hello".to_string(), "world".to_string()];
        assert_eq!(
            accumulate(&words, |s| s.to_uppercase()),
            vec!["HELLO", "WORLD"]
        );
    }

    #[test]
    fn test_tail_recursive() {
        assert_eq!(accumulate_tr(&[1, 2, 3], |x| x + 10), vec![11, 12, 13]);
    }

    #[test]
    fn test_iterator_version() {
        assert_eq!(accumulate_iter(vec![1, 2, 3], |x| x * 2), vec![2, 4, 6]);
    }

    #[test]
    fn test_type_change() {
        assert_eq!(
            accumulate(&[1, 2, 3], |x| x.to_string()),
            vec!["1", "2", "3"]
        );
    }
}

(* Accumulate — Custom Map *)

(* Version 1: Simple recursive *)
let rec accumulate f = function
  | [] -> []
  | h :: t -> f h :: accumulate f t

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

let () =
  assert (accumulate (fun x -> x * x) [1;2;3;4;5] = [1;4;9;16;25]);
  assert (accumulate_tr String.uppercase_ascii ["hello";"world"] = ["HELLO";"WORLD"])

✓ Tests Rust test suite

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

    #[test]
    fn test_squares() {
        assert_eq!(
            accumulate(&[1, 2, 3, 4, 5], |x| x * x),
            vec![1, 4, 9, 16, 25]
        );
    }

    #[test]
    fn test_empty() {
        assert_eq!(accumulate::<i32, i32, _>(&[], |x| x * x), Vec::<i32>::new());
    }

    #[test]
    fn test_strings() {
        let words = vec!["hello".to_string(), "world".to_string()];
        assert_eq!(
            accumulate(&words, |s| s.to_uppercase()),
            vec!["HELLO", "WORLD"]
        );
    }

    #[test]
    fn test_tail_recursive() {
        assert_eq!(accumulate_tr(&[1, 2, 3], |x| x + 10), vec![11, 12, 13]);
    }

    #[test]
    fn test_iterator_version() {
        assert_eq!(accumulate_iter(vec![1, 2, 3], |x| x * 2), vec![2, 4, 6]);
    }

    #[test]
    fn test_type_change() {
        assert_eq!(
            accumulate(&[1, 2, 3], |x| x.to_string()),
            vec!["1", "2", "3"]
        );
    }
}

Deep Comparison

Accumulate — Comparison

Core Insight

Implementing map from scratch reveals how both languages handle recursion, list construction, and higher-order functions. The recursive pattern is identical, but idiomatic Rust favors iterators over manual recursion.

OCaml Approach

• let rec accumulate f = function | [] -> [] | h :: t -> f h :: accumulate f t

• Pattern matching on list constructors ([] and h :: t)

• Tail-recursive version reverses accumulator at the end

• List.rev acc is the standard tail-recursive pattern

Rust Approach

• Slice patterns [head, tail @ ..] mirror OCaml list patterns

• Vec::with_capacity pre-allocates for known size

• Iterator version: .into_iter().map(f).collect() — one line

• Closure takes &T (borrow) or T (ownership) depending on variant

Comparison Table

Aspect	OCaml	Rust
Pattern	`h :: t`	`[head, tail @ ..]`
Build result	`::` cons	`vec![]` + extend
Tail-recursive	`List.rev acc`	`Vec::push` (already efficient)
Idiomatic	`List.map`	`.iter().map().collect()`
Closure	`fun x -> ...`	`\|x\| ...` or `\\|x\\| ...`

Learner Notes

• Rust slice patterns are nightly-stable since 1.42 — use them!

• Vec::push is amortized O(1), no need for reverse trick

• The iterator version is what you'd actually write in production Rust

• OCaml's :: cons is O(1); Rust's vec! + extend is O(n) total

Exercises

Implement accumulate_filter_map<T, U>(lst: &[T], f: impl Fn(&T) -> Option<U>) -> Vec<U> that maps and filters in a single pass.

Write accumulate_indexed<T, U>(lst: &[T], f: impl Fn(usize, &T) -> U) -> Vec<U> that passes the index to the function.

Benchmark the three versions for a 1,000,000-element slice of i32. Document the results.

Implement accumulate using fold_right (right-associative fold) and explain why it is not tail-recursive.

In OCaml, implement accumulate_lazy using the Seq module so transformation is deferred until materialized.

Open Source Repos

functional-rust

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

Rust