886 Intermediate

886-scan-accumulate — Scan / Accumulate

Functional Programming

Tutorial

The Problem

Fold collapses a sequence to a single value. Scan is fold's sibling: it emits every intermediate accumulator value as an element of a new sequence. Running sums, cumulative maxima, and prefix products are all applications of scan. In financial applications, scan computes balance history from a list of transactions. In signal processing, it computes moving statistics. Haskell has scanl, OCaml has Seq.scan, and Python's itertools.accumulate serves the same role. Rust's Iterator::scan adapter is the idiomatic approach — stateful, lazy, and composable with the rest of the iterator ecosystem.

🎯 Learning Outcomes

• Use .scan(init, |state, item| ...) to compute running accumulations

• Build running sum, running product, running max, and running min in one pass

• Implement balance history from a sequence of transactions using scan

• Understand the difference between fold (single result) and scan (sequence of results)

• Compare with OCaml's Seq.scan and Python's itertools.accumulate

Code Example

pub fn running_sum(data: &[i32]) -> Vec<i32> {
    data.iter()
        .scan(0, |acc, &x| {
            *acc += x;
            Some(*acc)
        })
        .collect()
}

(* Manual scan: returns init + every intermediate state *)
let scan f init lst =
  let rec aux acc state = function
    | [] -> List.rev acc
    | x :: rest ->
      let new_state = f state x in
      aux (new_state :: acc) new_state rest
  in
  aux [init] init lst

let running_sum lst = scan ( + ) 0 lst

Key Differences

Mutability: Rust scan uses &mut state — the state is explicitly mutable inside the closure; OCaml uses functional state threading.

Early termination: Rust scan can return None to stop early (like a conditional scan-while); OCaml requires explicit Seq.take_while wrapping.

Initial value: Rust scan starts emitting from the first transformed value (not the initial state); OCaml's scan_left typically includes the initial state.

Laziness: Both are lazy when using Seq/iterator form; both require explicit collection for eager evaluation.

OCaml Approach

OCaml's Seq.scan f init xs produces a lazy sequence of intermediate values. List.fold_left is used for the eager version, collecting intermediate values with a ref accumulator. scan_left in the example uses a helper that returns init :: (fold values) — the list of all accumulator states including the initial. OCaml's Seq.scan is lazy like Rust's; List-based scan is eager.

Full Source

#![allow(clippy::all)]
// Example 092: Scan / Accumulate
// Like fold but emits every intermediate value — running sums, cumulative statistics, balance histories.

// === Approach 1: Basic scan using std iterator adapter ===

/// Running sum: each element is the cumulative sum up to that index.
pub fn running_sum(data: &[i32]) -> Vec<i32> {
    data.iter()
        .scan(0, |acc, &x| {
            *acc += x;
            Some(*acc)
        })
        .collect()
}

/// Running product: cumulative product at each step.
pub fn running_product(data: &[i32]) -> Vec<i32> {
    data.iter()
        .scan(1, |acc, &x| {
            *acc *= x;
            Some(*acc)
        })
        .collect()
}

// === Approach 2: Running max / min ===

/// Running max: the highest value seen so far at each position.
pub fn running_max(data: &[i32]) -> Vec<i32> {
    data.iter()
        .scan(i32::MIN, |max, &x| {
            *max = (*max).max(x);
            Some(*max)
        })
        .collect()
}

/// Running min: the lowest value seen so far at each position.
pub fn running_min(data: &[i32]) -> Vec<i32> {
    data.iter()
        .scan(i32::MAX, |min, &x| {
            *min = (*min).min(x);
            Some(*min)
        })
        .collect()
}

// === Approach 3: Practical application — balance history ===

/// Given a starting balance and a sequence of signed transactions,
/// return the balance after each transaction.
pub fn balance_history(initial: i32, transactions: &[i32]) -> Vec<i32> {
    transactions
        .iter()
        .scan(initial, |bal, &tx| {
            *bal += tx;
            Some(*bal)
        })
        .collect()
}

/// Running average (as f64) at each position.
pub fn running_average(data: &[f64]) -> Vec<f64> {
    data.iter()
        .scan((0.0_f64, 0_usize), |state, &x| {
            state.0 += x;
            state.1 += 1;
            Some(state.0 / state.1 as f64)
        })
        .collect()
}

// === Approach 4: Recursive / functional style mirroring OCaml ===

/// Generic scan: applies `f` to running state and each element,
/// collecting each intermediate state (including `init`).
pub fn scan<S, T, F>(init: S, data: &[T], f: F) -> Vec<S>
where
    S: Clone,
    F: Fn(S, &T) -> S,
{
    let mut result = Vec::with_capacity(data.len() + 1);
    result.push(init.clone());
    let mut state = init;
    for item in data {
        state = f(state, item);
        result.push(state.clone());
    }
    result
}

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

    #[test]
    fn test_running_sum_empty() {
        assert_eq!(running_sum(&[]), Vec::<i32>::new());
    }

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

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

    #[test]
    fn test_running_sum_negative() {
        assert_eq!(running_sum(&[10, -3, 2, -1]), vec![10, 7, 9, 8]);
    }

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

    #[test]
    fn test_running_max_empty() {
        assert_eq!(running_max(&[]), Vec::<i32>::new());
    }

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

    #[test]
    fn test_running_min() {
        assert_eq!(running_min(&[5, 3, 8, 1, 7]), vec![5, 3, 3, 1, 1]);
    }

    #[test]
    fn test_balance_history() {
        // start at 100, transactions: +50, -30, +20, -10
        assert_eq!(
            balance_history(100, &[50, -30, 20, -10]),
            vec![150, 120, 140, 130]
        );
    }

    #[test]
    fn test_balance_history_empty() {
        assert_eq!(balance_history(500, &[]), Vec::<i32>::new());
    }

    #[test]
    fn test_running_average() {
        let result = running_average(&[1.0, 2.0, 3.0, 4.0]);
        let expected = vec![1.0, 1.5, 2.0, 2.5];
        for (a, b) in result.iter().zip(expected.iter()) {
            assert!((a - b).abs() < 1e-10);
        }
    }

    #[test]
    fn test_generic_scan_includes_init() {
        // scan with addition: should include initial value 0
        let result = scan(0, &[1, 2, 3], |acc, &x| acc + x);
        assert_eq!(result, vec![0, 1, 3, 6]);
    }

    #[test]
    fn test_generic_scan_empty() {
        let result = scan(42, &[] as &[i32], |acc, &x| acc + x);
        assert_eq!(result, vec![42]);
    }

    #[test]
    fn test_generic_scan_string_concat() {
        let words = ["hello", "world", "rust"];
        let result = scan(String::new(), &words, |mut acc, w| {
            if !acc.is_empty() {
                acc.push(' ');
            }
            acc.push_str(w);
            acc
        });
        assert_eq!(result, vec!["", "hello", "hello world", "hello world rust"]);
    }
}

(* Example 092: Scan / Accumulate *)
(* Running fold: OCaml custom → Rust scan *)

(* Approach 1: Manual scan implementation *)
let scan f init lst =
  let rec aux acc state = function
    | [] -> List.rev acc
    | x :: rest ->
      let new_state = f state x in
      aux (new_state :: acc) new_state rest
  in
  aux [init] init lst

let running_sum lst = scan ( + ) 0 lst
let running_max lst =
  match lst with
  | [] -> []
  | x :: rest -> scan max x rest

(* Approach 2: Scan without initial value *)
let scan1 f = function
  | [] -> []
  | x :: rest ->
    let rec aux acc state = function
      | [] -> List.rev acc
      | y :: rest ->
        let new_state = f state y in
        aux (new_state :: acc) new_state rest
    in
    aux [x] x rest

(* Approach 3: Practical applications *)
let running_average lst =
  let _, result = List.fold_left (fun (i, acc) x ->
    let n = i + 1 in
    let avg = (float_of_int (List.fold_left (+) 0 (List.filteri (fun j _ -> j < n) lst))) /. float_of_int n in
    (n, acc @ [avg])
  ) (0, []) lst in
  result

let balance_history transactions =
  scan ( + ) 0 transactions

let is_monotonic lst =
  let diffs = List.map2 (fun a b -> b - a) (List.filteri (fun i _ -> i < List.length lst - 1) lst)
    (List.tl lst) in
  List.for_all (fun d -> d >= 0) diffs || List.for_all (fun d -> d <= 0) diffs

(* Tests *)
let () =
  assert (running_sum [1;2;3;4;5] = [0;1;3;6;10;15]);

  assert (scan1 ( + ) [1;2;3;4;5] = [1;3;6;10;15]);

  assert (balance_history [100; -30; 50; -20] = [0; 100; 70; 120; 100]);

  assert (is_monotonic [1;2;3;4;5]);
  assert (is_monotonic [5;4;3;2;1]);
  assert (not (is_monotonic [1;3;2;4]));

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_running_sum_empty() {
        assert_eq!(running_sum(&[]), Vec::<i32>::new());
    }

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

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

    #[test]
    fn test_running_sum_negative() {
        assert_eq!(running_sum(&[10, -3, 2, -1]), vec![10, 7, 9, 8]);
    }

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

    #[test]
    fn test_running_max_empty() {
        assert_eq!(running_max(&[]), Vec::<i32>::new());
    }

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

    #[test]
    fn test_running_min() {
        assert_eq!(running_min(&[5, 3, 8, 1, 7]), vec![5, 3, 3, 1, 1]);
    }

    #[test]
    fn test_balance_history() {
        // start at 100, transactions: +50, -30, +20, -10
        assert_eq!(
            balance_history(100, &[50, -30, 20, -10]),
            vec![150, 120, 140, 130]
        );
    }

    #[test]
    fn test_balance_history_empty() {
        assert_eq!(balance_history(500, &[]), Vec::<i32>::new());
    }

    #[test]
    fn test_running_average() {
        let result = running_average(&[1.0, 2.0, 3.0, 4.0]);
        let expected = vec![1.0, 1.5, 2.0, 2.5];
        for (a, b) in result.iter().zip(expected.iter()) {
            assert!((a - b).abs() < 1e-10);
        }
    }

    #[test]
    fn test_generic_scan_includes_init() {
        // scan with addition: should include initial value 0
        let result = scan(0, &[1, 2, 3], |acc, &x| acc + x);
        assert_eq!(result, vec![0, 1, 3, 6]);
    }

    #[test]
    fn test_generic_scan_empty() {
        let result = scan(42, &[] as &[i32], |acc, &x| acc + x);
        assert_eq!(result, vec![42]);
    }

    #[test]
    fn test_generic_scan_string_concat() {
        let words = ["hello", "world", "rust"];
        let result = scan(String::new(), &words, |mut acc, w| {
            if !acc.is_empty() {
                acc.push(' ');
            }
            acc.push_str(w);
            acc
        });
        assert_eq!(result, vec!["", "hello", "hello world", "hello world rust"]);
    }
}

Deep Comparison

OCaml vs Rust: Scan / Accumulate

Side-by-Side Code

OCaml

(* Manual scan: returns init + every intermediate state *)
let scan f init lst =
  let rec aux acc state = function
    | [] -> List.rev acc
    | x :: rest ->
      let new_state = f state x in
      aux (new_state :: acc) new_state rest
  in
  aux [init] init lst

let running_sum lst = scan ( + ) 0 lst

Rust (idiomatic — using built-in `scan` iterator adapter)

pub fn running_sum(data: &[i32]) -> Vec<i32> {
    data.iter()
        .scan(0, |acc, &x| {
            *acc += x;
            Some(*acc)
        })
        .collect()
}

Rust (functional/generic — mirrors OCaml structure)

pub fn scan<S, T, F>(init: S, data: &[T], f: F) -> Vec<S>
where
    S: Clone,
    F: Fn(S, &T) -> S,
{
    let mut result = Vec::with_capacity(data.len() + 1);
    result.push(init.clone());
    let mut state = init;
    for item in data {
        state = f(state, item);
        result.push(state.clone());
    }
    result
}

Type Signatures

Concept	OCaml	Rust
Generic scan	`val scan : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a list`	`fn scan<S, T, F>(init: S, data: &[T], f: F) -> Vec<S>`
Running sum	`val running_sum : int list -> int list`	`fn running_sum(data: &[i32]) -> Vec<i32>`
Iterator state	implicit via closure capture	`\|acc, &x\|` — `acc` is `&mut S`, mutated in place
Early termination	not built-in	return `None` from the closure to stop the iterator

Key Insights

Built-in adapter: Rust's Iterator::scan is a first-class iterator adapter that carries mutable state between elements, eliminating the need for the manual recursive helper OCaml requires.

Mutable state in closures: Rust's scan closure receives acc as &mut S — you mutate it in place and return Some(value) to continue, or None to stop early. OCaml's recursive approach threads state explicitly through parameters.

Ownership of state: The generic scan function requires S: Clone because each intermediate value must be stored independently in the output Vec. Rust makes this cost explicit; OCaml's GC handles sharing silently.

Lazy vs eager: Rust's .scan(...).collect() is lazy until collect drives it, enabling fusion with other adapters (.filter, .take) before materialising results. OCaml's list-based scan is strict and allocates immediately.

Practical pattern: Balance histories, running statistics, and state-machine trajectories are the canonical use cases. In both languages the pattern is the same: carry one piece of mutable state and emit its value after each update.

When to Use Each Style

**Use idiomatic Rust (.scan adapter) when:** you want composable, lazy iteration — chain .scan with .take_while, .filter, or .map before collecting, or when you only need part of the trajectory.

**Use the generic scan function when:** you want a reusable utility with an explicit initial value included in the output (matching OCaml's scan f init lst semantics), or when the state type requires non-Copy cloning that you want to make visible.

Exercises

Implement running_variance using scan to track count, sum, and sum-of-squares in a single pass.

Write scan_until_zero that computes running products but stops (returns None) when a zero is encountered.

Implement cumulative_max_index that tracks both the running maximum and the index where it was last updated.

Open Source Repos

functional-rust

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

Rust