070 Intermediate

070 — Scan Left (Running Accumulation)

Functional Programming

Tutorial

The Problem

scan_left (Haskell: scanl, OCaml: List.fold_left with output collection) produces all intermediate values of a fold, not just the final result. Where fold([1,2,3,4], +, 0) gives 10, scan_left([1,2,3,4], +, 0) gives [0, 1, 3, 6, 10] — every prefix sum including the initial accumulator. This is the "running total" operation.

Running totals appear throughout practical computing. Financial ledgers track a running balance alongside each transaction, enabling audit trails. Prefix sum arrays — the canonical scan_left application — allow O(1) range sum queries: sum(i..j) = prefix[j] - prefix[i], making them a standard data structure in competitive programming and database query engines. Exponential moving averages in signal processing and real-time analytics compute as a scan over time-series data. Compilers accumulate struct field offset tables by scanning over field sizes. Any computation that needs to observe the fold at every step, not just at the end, uses scan.

🎯 Learning Outcomes

• Use Rust's .scan(init, |acc, &x| { *acc = ...; Some(*acc) }) for running accumulation with mutable state

• Implement a generic scan_left<T: Clone, F>(init: T, v: &[T], f: F) -> Vec<T> that mirrors OCaml's pattern

• Distinguish scan (keeps all intermediates) from fold (keeps only the final result)

• Build prefix sum arrays for O(1) range sum queries

• Implement running max, running min, and running product with the same generic combinator

• Recognize that scan is fold with intermediate-result observation at every step

Code Example

#![allow(clippy::all)]
// 070: Scan Left — running accumulation

// Approach 1: Using .scan() iterator
fn running_sum(v: &[i32]) -> Vec<i32> {
    let mut result = vec![0];
    result.extend(v.iter().scan(0, |state, &x| {
        *state += x;
        Some(*state)
    }));
    result
}

// Approach 2: Manual scan function
fn scan_left<T: Clone, F>(init: T, v: &[T], f: F) -> Vec<T>
where
    F: Fn(&T, &T) -> T,
{
    let mut result = vec![init.clone()];
    let mut acc = init;
    for x in v {
        acc = f(&acc, x);
        result.push(acc.clone());
    }
    result
}

fn running_product(v: &[i32]) -> Vec<i32> {
    scan_left(1, v, |a, b| a * b)
}

// Approach 3: Running max
fn running_max(v: &[i32]) -> Vec<i32> {
    if v.is_empty() {
        return vec![];
    }
    let mut result = vec![v[0]];
    let mut current_max = v[0];
    for &x in &v[1..] {
        current_max = current_max.max(x);
        result.push(current_max);
    }
    result
}

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

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

    #[test]
    fn test_running_product() {
        assert_eq!(running_product(&[1, 2, 3, 4]), vec![1, 1, 2, 6, 24]);
    }

    #[test]
    fn test_scan_left() {
        assert_eq!(scan_left(0, &vec![1, 2, 3], |a, b| a + b), vec![0, 1, 3, 6]);
    }

    #[test]
    fn test_running_max() {
        assert_eq!(running_max(&[3, 1, 4, 1, 5, 9]), vec![3, 3, 4, 4, 5, 9]);
        assert_eq!(running_max(&[]), Vec::<i32>::new());
    }
}

(* 070: Scan Left — running accumulation *)

(* Approach 1: Recursive scan_left *)
let scan_left f init lst =
  let rec aux acc current = function
    | [] -> List.rev (current :: acc)
    | x :: xs -> aux (current :: acc) (f current x) xs
  in
  aux [] init lst

(* Running sum *)
let running_sum lst = scan_left ( + ) 0 lst

(* Running product *)
let running_product lst = scan_left ( * ) 1 lst

(* Approach 2: Using fold_left to build scan *)
let scan_left_fold f init lst =
  let result, _ =
    List.fold_left
      (fun (acc_list, current) x ->
        let next = f current x in
        (next :: acc_list, next))
      ([init], init)
      lst
  in
  List.rev result

(* Approach 3: Running max *)
let running_max lst =
  match lst with
  | [] -> []
  | x :: xs ->
    scan_left (fun a b -> max a b) x xs

(* Tests *)
let () =
  assert (running_sum [1; 2; 3; 4] = [0; 1; 3; 6; 10]);
  assert (running_sum [] = [0]);
  assert (running_product [1; 2; 3; 4] = [1; 1; 2; 6; 24]);
  assert (scan_left_fold ( + ) 0 [1; 2; 3] = [0; 1; 3; 6]);
  assert (running_max [3; 1; 4; 1; 5; 9] = [3; 3; 4; 4; 5; 9]);
  Printf.printf "✓ All tests passed\n"

Key Differences

**.scan() in stdlib**: Rust's Iterator::scan is built in — providing (0..n).scan(0, |acc, x| { *acc += x; Some(*acc) }). OCaml has no stdlib scan; it must be manually implemented.

State mutation: Rust's scan closure receives &mut state and can modify it. OCaml's functional approach passes the new accumulator as a recursive argument.

Including initial value: The standard scan_left(f, init, list) includes init as the first element. Rust's .scan() does NOT include the initial value — it starts with the result of applying f to the first element. Account for this difference.

Prefix sum array: (0..=n).scan(0i32, |s, x| { *s += x; Some(*s) }).collect::<Vec<_>>() builds a prefix sum array for O(1) range queries: sum(i..j) = prefix[j] - prefix[i].

OCaml Approach

OCaml's standard library List.fold_left computes only the final result. For scan, you define it manually:

let scan_left f init lst =
  let rec aux acc lst result =
    match lst with
    | [] -> List.rev result
    | x :: t ->
      let acc' = f acc x in
      aux acc' t (acc' :: result)
  in
  init :: aux init lst []

This is tail-recursive via the accumulator result list, reversed at the end. OCaml 4.11 added List.fold_left_map which produces a transformed list alongside the accumulator, partially overlapping with scan for element-wise transforms but not providing running intermediates directly.

Full Source

#![allow(clippy::all)]
// 070: Scan Left — running accumulation

// Approach 1: Using .scan() iterator
fn running_sum(v: &[i32]) -> Vec<i32> {
    let mut result = vec![0];
    result.extend(v.iter().scan(0, |state, &x| {
        *state += x;
        Some(*state)
    }));
    result
}

// Approach 2: Manual scan function
fn scan_left<T: Clone, F>(init: T, v: &[T], f: F) -> Vec<T>
where
    F: Fn(&T, &T) -> T,
{
    let mut result = vec![init.clone()];
    let mut acc = init;
    for x in v {
        acc = f(&acc, x);
        result.push(acc.clone());
    }
    result
}

fn running_product(v: &[i32]) -> Vec<i32> {
    scan_left(1, v, |a, b| a * b)
}

// Approach 3: Running max
fn running_max(v: &[i32]) -> Vec<i32> {
    if v.is_empty() {
        return vec![];
    }
    let mut result = vec![v[0]];
    let mut current_max = v[0];
    for &x in &v[1..] {
        current_max = current_max.max(x);
        result.push(current_max);
    }
    result
}

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

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

    #[test]
    fn test_running_product() {
        assert_eq!(running_product(&[1, 2, 3, 4]), vec![1, 1, 2, 6, 24]);
    }

    #[test]
    fn test_scan_left() {
        assert_eq!(scan_left(0, &vec![1, 2, 3], |a, b| a + b), vec![0, 1, 3, 6]);
    }

    #[test]
    fn test_running_max() {
        assert_eq!(running_max(&[3, 1, 4, 1, 5, 9]), vec![3, 3, 4, 4, 5, 9]);
        assert_eq!(running_max(&[]), Vec::<i32>::new());
    }
}

(* 070: Scan Left — running accumulation *)

(* Approach 1: Recursive scan_left *)
let scan_left f init lst =
  let rec aux acc current = function
    | [] -> List.rev (current :: acc)
    | x :: xs -> aux (current :: acc) (f current x) xs
  in
  aux [] init lst

(* Running sum *)
let running_sum lst = scan_left ( + ) 0 lst

(* Running product *)
let running_product lst = scan_left ( * ) 1 lst

(* Approach 2: Using fold_left to build scan *)
let scan_left_fold f init lst =
  let result, _ =
    List.fold_left
      (fun (acc_list, current) x ->
        let next = f current x in
        (next :: acc_list, next))
      ([init], init)
      lst
  in
  List.rev result

(* Approach 3: Running max *)
let running_max lst =
  match lst with
  | [] -> []
  | x :: xs ->
    scan_left (fun a b -> max a b) x xs

(* Tests *)
let () =
  assert (running_sum [1; 2; 3; 4] = [0; 1; 3; 6; 10]);
  assert (running_sum [] = [0]);
  assert (running_product [1; 2; 3; 4] = [1; 1; 2; 6; 24]);
  assert (scan_left_fold ( + ) 0 [1; 2; 3] = [0; 1; 3; 6]);
  assert (running_max [3; 1; 4; 1; 5; 9] = [3; 3; 4; 4; 5; 9]);
  Printf.printf "✓ All 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]), vec![0, 1, 3, 6, 10]);
        assert_eq!(running_sum(&[]), vec![0]);
    }

    #[test]
    fn test_running_product() {
        assert_eq!(running_product(&[1, 2, 3, 4]), vec![1, 1, 2, 6, 24]);
    }

    #[test]
    fn test_scan_left() {
        assert_eq!(scan_left(0, &vec![1, 2, 3], |a, b| a + b), vec![0, 1, 3, 6]);
    }

    #[test]
    fn test_running_max() {
        assert_eq!(running_max(&[3, 1, 4, 1, 5, 9]), vec![3, 3, 4, 4, 5, 9]);
        assert_eq!(running_max(&[]), Vec::<i32>::new());
    }
}

Deep Comparison

Core Insight

Scan is fold that emits every intermediate accumulator value. scan_left [1;2;3] (+) 0 gives [0;1;3;6] — the running sum. It's the functional equivalent of a cumulative sum.

OCaml Approach

• No built-in scan_left — implement with fold or recursion

• Returns list of all accumulator states

• List.fold_left adapted to collect intermediates

Rust Approach

• .scan(state, |st, x| ...) — stateful iterator adapter

• Returns Option to allow early termination

• Also achievable with fold collecting into Vec

Comparison Table

Feature	OCaml	Rust
Built-in	No	`.scan()` iterator adapter
Result	List of accumulators	Iterator of values
State	Accumulator in recursion	Mutable state in closure

Exercises

Range sum query: Build a prefix sum array from [3, 1, 4, 1, 5, 9, 2, 6]. Write range_sum(prefix: &[i32], i: usize, j: usize) -> i32 that computes the sum of elements from index i to j in O(1).

Running statistics: Write running_mean(v: &[f64]) -> Vec<f64> where result[i] is the mean of v[0..=i]. Use scan with a (sum, count) state tuple.

Sliding window max: Using a running max, implement a sliding window maximum of size k: for each position i, find the maximum in v[i-k+1..=i]. This requires a deque, not just scan — research the monotone deque approach.

Open Source Repos

functional-rust

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

Rust