092 Intermediate

092 — Scan Accumulate

Functional Programming

Tutorial

The Problem

Implement running_sum and running_max — prefix accumulations that produce a new sequence where each element is the accumulated result up to that position. Use Rust's Iterator::scan for running_sum and an explicit loop for running_max. Compare with OCaml's scan_left built on List.fold_left.

🎯 Learning Outcomes

• Use Iterator::scan(init, |state, x| { … ; Some(result) }) for stateful prefix computations

• Understand that scan is like fold but emits intermediate accumulator values

• Distinguish scan (emits each step) from fold (emits only the final result)

• Implement running_max with an explicit loop when scan becomes cumbersome

• Map Rust's scan to OCaml's scan_left built from List.fold_left

• Recognise prefix scan as a fundamental data-parallel primitive

Code Example

#![allow(clippy::all)]
// 092: Scan with Accumulator

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

fn running_max(v: &[i32]) -> Vec<i32> {
    if v.is_empty() {
        return vec![];
    }
    let mut max_val = v[0];
    let mut result = vec![max_val];
    for &x in &v[1..] {
        max_val = max_val.max(x);
        result.push(max_val);
    }
    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]);
    }

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

(* 092: Scan with Accumulator *)

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

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

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

Key Differences

Aspect	Rust	OCaml
Scan primitive	`Iterator::scan(init, f)`	Custom `scan_left` via `fold_left`
State mutation	`*state += x` (mutable ref)	Immutable `next = f acc x`
Accumulator	Modified in place	New value each step
Running max	Explicit loop	`scan_left max x xs`
Order	No reversal needed	`List.rev result` needed
Standard library	`scan` built in	`scan_left` not in stdlib

The scan operation is the prefix-sum primitive of functional programming. It generalises fold by keeping intermediate results — essential for computing things like running averages, cumulative distributions, and prefix XORs in competitive programming.

OCaml Approach

OCaml's scan_left f init lst is implemented with fold_left: at each step, compute next = f acc x, accumulate next :: res, and reverse at the end. running_sum = scan_left (+) 0 and running_max = scan_left max x xs with the first element as the initial value. The pattern is elegant but requires the List.rev at the end to restore order.

Full Source

#![allow(clippy::all)]
// 092: Scan with Accumulator

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

fn running_max(v: &[i32]) -> Vec<i32> {
    if v.is_empty() {
        return vec![];
    }
    let mut max_val = v[0];
    let mut result = vec![max_val];
    for &x in &v[1..] {
        max_val = max_val.max(x);
        result.push(max_val);
    }
    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]);
    }

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

(* 092: Scan with Accumulator *)

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

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

(* Tests *)
let () =
  assert (running_sum [1; 2; 3; 4] = [0; 1; 3; 6; 10]);
  assert (running_max [3; 1; 4; 1; 5] = [3; 3; 4; 4; 5]);
  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]);
    }

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

Deep Comparison

Core Insight

Scan is fold that emits every intermediate state — useful for running sums, products, or state machines

OCaml Approach

• See example.ml for implementation

Rust Approach

• See example.rs for implementation

Comparison Table

Feature	OCaml	Rust
See	example.ml	example.rs

Exercises

Implement running_product(v: &[i64]) -> Vec<i64> using scan with initial value 1.

Write running_avg(v: &[f64]) -> Vec<f64> that computes the running arithmetic mean.

Implement scan_right (right-to-left scan) by reversing the input, scanning, then reversing the output.

Use scan to implement enumerate: produce (0, v[0]), (1, v[1]), … without calling .enumerate().

In OCaml, implement scan_left using Seq to make it lazy — deferring computation until elements are demanded.

Open Source Repos

functional-rust

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

Rust