939 Intermediate

939 Scan Left

Functional Programming

Tutorial

The Problem

Implement scan_left, which produces all intermediate accumulator values while folding over a sequence. Unlike fold (which returns only the final value), scan_left returns the initial value followed by every partial result, making it possible to observe the fold's evolution step by step. Build running sum and running max as concrete applications, then compare with Rust's built-in Iterator::scan adapter.

🎯 Learning Outcomes

• Understand the relationship between fold (reduces to one value) and scan (keeps every intermediate value)

• Implement scan_left<T, A, F>(init, items, f) -> Vec<A> using a generic accumulator

• Apply scan_left to compute running sum, running max, and other prefix aggregations

• Use Rust's Iterator::scan with mutable state (&mut state) and Some/None control

• Recognize why scan_left produces n + 1 values for an n-element input (includes the initial value)

Code Example

#![allow(clippy::all)]
/// # Scan Left — Running Accumulation
///
/// `scan` returns all intermediate results of a fold operation.
/// Like fold, but keeps the running state at each step.

/// Custom scan_left: returns vec of all intermediate accumulator values.
pub fn scan_left<T, A, F>(init: A, items: &[T], f: F) -> Vec<A>
where
    A: Clone,
    F: Fn(&A, &T) -> A,
{
    let mut result = vec![init.clone()];
    let mut acc = init;
    for item in items {
        acc = f(&acc, item);
        result.push(acc.clone());
    }
    result
}

/// Running sum
pub fn running_sum(nums: &[i64]) -> Vec<i64> {
    scan_left(0i64, nums, |acc, x| acc + x)
}

/// Running max
pub fn running_max(nums: &[i64]) -> Vec<i64> {
    scan_left(i64::MIN, nums, |acc, x| *acc.max(x))
}

/// Idiomatic Rust: use the built-in `scan` iterator adapter.
/// Note: `Iterator::scan` is slightly different — it takes FnMut with mutable state.
pub fn running_sum_idiomatic(nums: &[i64]) -> Vec<i64> {
    let mut result = vec![0i64];
    result.extend(nums.iter().scan(0i64, |state, &x| {
        *state += x;
        Some(*state)
    }));
    result
}

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

    #[test]
    fn test_running_sum() {
        assert_eq!(running_sum(&[1, 2, 3, 4, 5]), vec![0, 1, 3, 6, 10, 15]);
    }

    #[test]
    fn test_running_sum_empty() {
        assert_eq!(running_sum(&[]), vec![0]);
    }

    #[test]
    fn test_running_max() {
        let result = running_max(&[3, 1, 4, 1, 5, 9, 2, 6]);
        assert_eq!(result[1..], [3, 3, 4, 4, 5, 9, 9, 9]);
    }

    #[test]
    fn test_scan_left_generic() {
        let result = scan_left(String::new(), &["hello", " ", "world"], |acc, s| {
            format!("{}{}", acc, s)
        });
        assert_eq!(result, vec!["", "hello", "hello ", "hello world"]);
    }

    #[test]
    fn test_idiomatic() {
        assert_eq!(
            running_sum_idiomatic(&[1, 2, 3, 4, 5]),
            vec![0, 1, 3, 6, 10, 15]
        );
    }
}

(* Scan Left — Running Accumulation *)
(* Returns all intermediate fold results *)

let scan_left f init lst =
  let _, result = List.fold_left (fun (acc, res) x ->
    let acc' = f acc x in
    (acc', acc' :: res)
  ) (init, [init]) lst in
  List.rev result

let running_sum = scan_left (+) 0
let running_max = scan_left max min_int

let () =
  List.iter (Printf.printf "%d ") (running_sum [1;2;3;4;5]);
  print_newline ();
  List.iter (Printf.printf "%d ") (running_max [3;1;4;1;5;9;2;6]);
  print_newline ();
  assert (running_sum [1;2;3] = [0;1;3;6]);
  Printf.printf "All scan_left tests passed!\n"

Key Differences

Aspect	Rust	OCaml
Built-in scan	`Iterator::scan` (mutable state, `Option` control)	None in stdlib; `Seq`-based for laziness
Result size	`n + 1` values (includes seed)	Typically same
Early termination	Return `None` from closure	Pattern match on `Seq`
Laziness	Eager with `Vec`; lazy with `Iterator::scan` chained	`Seq` is lazy by default
State mutation	`&mut state` in closure	`ref`/`!` in imperative version; accumulator in pure version

Rust's Iterator::scan is the idiomatic choice for streaming prefix aggregation. The key insight is that scan is to fold what map is to for_each: it produces values along the way rather than consuming them silently.

OCaml Approach

OCaml's standard library lacks a built-in scan_left but it is trivially defined:

let scan_left f init xs =
  let acc = ref init in
  init :: List.map (fun x ->
    acc := f !acc x;
    !acc
  ) xs

(* purely functional version *)
let scan_left_pure f init xs =
  List.fold_left
    (fun (acc, sofar) x ->
      let acc' = f acc x in
      (acc', sofar @ [acc']))
    (init, [init]) xs
  |> snd

OCaml's Seq module supports lazy scan over infinite sequences without materializing a list:

let seq_scan f init s =
  let open Seq in
  let rec go acc s () = match s () with
    | Nil -> Nil
    | Cons (x, rest) ->
        let acc' = f acc x in
        Cons (acc', go acc' rest)
  in
  Cons (init, go init s)

Full Source

#![allow(clippy::all)]
/// # Scan Left — Running Accumulation
///
/// `scan` returns all intermediate results of a fold operation.
/// Like fold, but keeps the running state at each step.

/// Custom scan_left: returns vec of all intermediate accumulator values.
pub fn scan_left<T, A, F>(init: A, items: &[T], f: F) -> Vec<A>
where
    A: Clone,
    F: Fn(&A, &T) -> A,
{
    let mut result = vec![init.clone()];
    let mut acc = init;
    for item in items {
        acc = f(&acc, item);
        result.push(acc.clone());
    }
    result
}

/// Running sum
pub fn running_sum(nums: &[i64]) -> Vec<i64> {
    scan_left(0i64, nums, |acc, x| acc + x)
}

/// Running max
pub fn running_max(nums: &[i64]) -> Vec<i64> {
    scan_left(i64::MIN, nums, |acc, x| *acc.max(x))
}

/// Idiomatic Rust: use the built-in `scan` iterator adapter.
/// Note: `Iterator::scan` is slightly different — it takes FnMut with mutable state.
pub fn running_sum_idiomatic(nums: &[i64]) -> Vec<i64> {
    let mut result = vec![0i64];
    result.extend(nums.iter().scan(0i64, |state, &x| {
        *state += x;
        Some(*state)
    }));
    result
}

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

    #[test]
    fn test_running_sum() {
        assert_eq!(running_sum(&[1, 2, 3, 4, 5]), vec![0, 1, 3, 6, 10, 15]);
    }

    #[test]
    fn test_running_sum_empty() {
        assert_eq!(running_sum(&[]), vec![0]);
    }

    #[test]
    fn test_running_max() {
        let result = running_max(&[3, 1, 4, 1, 5, 9, 2, 6]);
        assert_eq!(result[1..], [3, 3, 4, 4, 5, 9, 9, 9]);
    }

    #[test]
    fn test_scan_left_generic() {
        let result = scan_left(String::new(), &["hello", " ", "world"], |acc, s| {
            format!("{}{}", acc, s)
        });
        assert_eq!(result, vec!["", "hello", "hello ", "hello world"]);
    }

    #[test]
    fn test_idiomatic() {
        assert_eq!(
            running_sum_idiomatic(&[1, 2, 3, 4, 5]),
            vec![0, 1, 3, 6, 10, 15]
        );
    }
}

(* Scan Left — Running Accumulation *)
(* Returns all intermediate fold results *)

let scan_left f init lst =
  let _, result = List.fold_left (fun (acc, res) x ->
    let acc' = f acc x in
    (acc', acc' :: res)
  ) (init, [init]) lst in
  List.rev result

let running_sum = scan_left (+) 0
let running_max = scan_left max min_int

let () =
  List.iter (Printf.printf "%d ") (running_sum [1;2;3;4;5]);
  print_newline ();
  List.iter (Printf.printf "%d ") (running_max [3;1;4;1;5;9;2;6]);
  print_newline ();
  assert (running_sum [1;2;3] = [0;1;3;6]);
  Printf.printf "All scan_left tests passed!\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_running_sum() {
        assert_eq!(running_sum(&[1, 2, 3, 4, 5]), vec![0, 1, 3, 6, 10, 15]);
    }

    #[test]
    fn test_running_sum_empty() {
        assert_eq!(running_sum(&[]), vec![0]);
    }

    #[test]
    fn test_running_max() {
        let result = running_max(&[3, 1, 4, 1, 5, 9, 2, 6]);
        assert_eq!(result[1..], [3, 3, 4, 4, 5, 9, 9, 9]);
    }

    #[test]
    fn test_scan_left_generic() {
        let result = scan_left(String::new(), &["hello", " ", "world"], |acc, s| {
            format!("{}{}", acc, s)
        });
        assert_eq!(result, vec!["", "hello", "hello ", "hello world"]);
    }

    #[test]
    fn test_idiomatic() {
        assert_eq!(
            running_sum_idiomatic(&[1, 2, 3, 4, 5]),
            vec![0, 1, 3, 6, 10, 15]
        );
    }
}

Deep Comparison

Scan Left — OCaml vs Rust Comparison

Core Insight

Scan is fold's cousin that keeps all intermediate states. OCaml builds it on top of fold_left with accumulator tuple (state, results). Rust has Iterator::scan() built-in but with a different API: it uses mutable state (FnMut) for performance rather than returning new state.

OCaml Approach

Implements scan_left using List.fold_left with a pair accumulator (acc, results_list). Each step produces a new pair — pure functional, no mutation. The result list is built in reverse and reversed at the end. Partial application makes running_sum = scan_left (+) 0 beautifully concise.

Rust Approach

Custom scan_left function uses &[T] slice input and Vec<A> output. The built-in Iterator::scan() takes a mutable state reference — closures modify state in place via *state += x. This is more memory-efficient but less purely functional. Both approaches are available.

Comparison Table

Aspect	OCaml	Rust
Memory	Reverse + rev (2x list)	Single Vec with push
Null safety	N/A	N/A
Errors	N/A	N/A
Iteration	`fold_left` with pair acc	`for` loop or `Iterator::scan()`
Mutation	None (purely functional)	`scan()` uses `FnMut` (mutable state)

Things Rust Learners Should Notice

**Iterator::scan()** is built-in but uses mutable state — different philosophy from OCaml

**A: Clone bound** — needed to store intermediate values; OCaml's GC handles this implicitly

**Slices &[T]** — Rust's way of borrowing a view into a collection without owning it

**vec![init.clone()]** — initial value must be cloned since we also keep it as running state

Exercises

Implement running_product using scan_left and verify it matches Iterator::scan.

Build a running_balance that tracks a bank account balance through a list of transactions (positive = deposit, negative = withdrawal).

Use Iterator::scan with None to implement scan_until_negative: stop scanning as soon as the running sum goes below zero.

Implement max_prefix_sum: use scan_left to find the maximum running sum over the entire array — useful in the Kadane's algorithm family.

Write a lazy scan_seq that works over Rust iterators without collecting into a Vec, using a custom struct that implements Iterator.

Open Source Repos

functional-rust

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

Rust

Tutorial

The Problem

🎯 Learning Outcomes

Code Example

Key Differences

OCaml Approach

Full Source

Deep Comparison

Scan Left — OCaml vs Rust Comparison

Core Insight

OCaml Approach

Rust Approach

Comparison Table

Things Rust Learners Should Notice

Further Reading

Exercises

Open Source Repos