070: Scan Left

Difficulty: ⭐ Level: Foundations Like `fold`, but keep every intermediate value — running totals, prefix sums, and accumulated state made simple.

The Problem This Solves

You have a list of daily sales figures and you want the running total after each day, not just the grand total. Or you want the running maximum as you scan through sensor readings. Or you want to watch how an accumulator evolves step by step. `fold` collapses a list to a single value. `scan` does the same accumulation, but captures every intermediate state. The result is a list as long as the input (plus one for the initial value). In Python, `itertools.accumulate` does this. In JavaScript you'd build the array manually. In Rust, `Iterator::scan` is built-in — though its API is slightly different from the functional ideal, so it's instructive to write your own `scan_left` first.

The Intuition

Run a fold step-by-step. After each step, save the current accumulator value. At the end you have all the intermediate results, not just the final one. Input `[1, 2, 3, 4, 5]` with addition starting from `0`:

Start: `[0]`
After 1: `[0, 1]`
After 2: `[0, 1, 3]`
After 3: `[0, 1, 3, 6]`
After 4: `[0, 1, 3, 6, 10]`
After 5: `[0, 1, 3, 6, 10, 15]`

That's your prefix sum. The same pattern works for running max, running product, string accumulation, anything.

How It Works in Rust

Custom `scan_left` — the clearest version:

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()];  // include the initial value
 let mut acc = init;
 for item in items {
     acc = f(&acc, item);
     result.push(acc.clone());
 }
 result
}

// Running sum: scan_left with addition
pub fn running_sum(nums: &[i64]) -> Vec<i64> {
 scan_left(0i64, nums, |acc, x| acc + x)
}
// running_sum(&[1,2,3,4,5]) → [0, 1, 3, 6, 10, 15]

Using the built-in `Iterator::scan` adapter:

// scan takes FnMut with a mutable state reference
let running = nums.iter().scan(0i64, |state, &x| {
 *state += x;
 Some(*state)
});
// Yields: 1, 3, 6, 10, 15  (no initial value included)

Note: the built-in `scan` doesn't include the initial value; add it manually if needed.

What This Unlocks

Running totals — balance after each transaction, score after each round
Prefix sums — precompute cumulative sums for O(1) range sum queries
State traces — log every state of a simulation or state machine for debugging or visualization

Key Differences

Concept	OCaml	Rust
Implementation	`fold_left` accumulating both value and result list	Custom `scan_left` or built-in `Iterator::scan`
Includes initial	`[init] @ accumulated_list`	`vec![init]` then extend
Built-in	No `scan_left` in stdlib	`Iterator::scan` (FnMut, no initial in output)
Functional purity	Pure — no mutation	Custom version is pure; built-in uses `FnMut`

/// # 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]
        );
    }
}

fn main() {
    println!("{:?}", running_sum(&[1, 2, 3, 4, 5]), vec![0, 1, 3, 6, 10, 15]);
    println!("{:?}", running_sum(&[]), vec![0]);
    println!("{:?}", result[1..], [3, 3, 4, 4, 5, 9, 9, 9]);
}

(* 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"

📊 Detailed 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

1. `Iterator::scan()` is built-in but uses mutable state — different philosophy from OCaml 2. `A: Clone` bound — needed to store intermediate values; OCaml's GC handles this implicitly 3. Slices `&[T]` — Rust's way of borrowing a view into a collection without owning it 4. `vec![init.clone()]` — initial value must be cloned since we also keep it as running state