904-iterator-scan — Iterator Scan
Functional Programming
Tutorial
The Problem
Fold produces one final value. Scan produces the whole sequence of intermediate values — one per input element. Running sums, cumulative maxima, and prefix products are all scan applications. The scan operation also supports early termination: returning None from the closure stops the iterator, enabling a "scan until condition" behavior that fold cannot express lazily. Haskell has scanl; OCaml has Seq.scan (since 4.14); Python has itertools.accumulate. Rust's Iterator::scan takes a mutable state reference, giving fine-grained control over both the emitted value and the accumulator.
🎯 Learning Outcomes
.scan(init, |state, item| ...) to produce running accumulationsNone return from the scan closure to stop early&mut state (what's tracked) and Some(value) (what's emitted)Seq.scan and Python's itertools.accumulateCode Example
pub fn running_sum(nums: &[i64]) -> Vec<i64> {
nums.iter()
.scan(0i64, |state, &x| {
*state += x;
Some(*state)
})
.collect()
}Key Differences
scanl and OCaml scan_left include the initial accumulator as the first output element; Rust scan does not — it starts emitting from the first transformed value.None; OCaml Seq.scan requires Seq.take_while for early stopping.&mut S, emitted is Some(V)); OCaml scan emits the updated state directly.&mut state explicitly; OCaml threads state as an immutable function argument.OCaml Approach
OCaml Seq.scan f init xs is available since 4.14. For eager scan: let scan_left f init xs = let r = ref [init] in let _ = List.fold_left (fun acc x -> let next = f acc x in r := next :: !r; next) init xs in List.rev !r. The custom scan_left in the example preserves the initial value in the output (like Haskell's scanl), while Rust's scan does not include the initial state in the output — a subtle but important difference.
Full Source
#![allow(clippy::all)]
//! 260. Stateful accumulation with scan()
//!
//! `scan()` is like `fold` but emits each intermediate state as an iterator element.
//! The closure receives `&mut state` and the current item, returns `Some(value)` to
//! continue or `None` to stop early.
/// Running sum using scan — idiomatic Rust iterator approach.
pub fn running_sum(nums: &[i64]) -> Vec<i64> {
nums.iter()
.scan(0i64, |state, &x| {
*state += x;
Some(*state)
})
.collect()
}
/// Running product using scan.
pub fn running_product(nums: &[i64]) -> Vec<i64> {
nums.iter()
.scan(1i64, |state, &x| {
*state *= x;
Some(*state)
})
.collect()
}
/// Prefix sums up to (and not including) the first value that exceeds `limit`.
/// Returns `None` from the closure to stop the iterator early.
pub fn running_sum_until(nums: &[i64], limit: i64) -> Vec<i64> {
nums.iter()
.scan(0i64, |state, &x| {
*state += x;
if *state > limit {
None
} else {
Some(*state)
}
})
.collect()
}
/// Running maximum — tracks the largest value seen so far.
pub fn running_max(nums: &[i64]) -> Vec<i64> {
nums.iter()
.scan(i64::MIN, |state, &x| {
*state = (*state).max(x);
Some(*state)
})
.collect()
}
/// Generic scan: mirrors the OCaml `scan init f lst` function.
/// Threads `init` as mutable state, applies `f(state, item)` at each step,
/// and collects all intermediate states.
pub fn scan<T, F>(init: T, mut f: F, items: &[T]) -> Vec<T>
where
T: Copy,
F: FnMut(T, T) -> T,
{
items
.iter()
.scan(init, |state, &x| {
*state = f(*state, x);
Some(*state)
})
.collect()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_running_sum_empty() {
assert_eq!(running_sum(&[]), Vec::<i64>::new());
}
#[test]
fn test_running_sum_single() {
assert_eq!(running_sum(&[42]), vec![42]);
}
#[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_with_negatives() {
let transactions = [100, -30, 50, -80, 200];
assert_eq!(running_sum(&transactions), vec![100, 70, 120, 40, 240]);
}
#[test]
fn test_running_product_multiple() {
assert_eq!(running_product(&[1, 2, 3, 4, 5]), vec![1, 2, 6, 24, 120]);
}
#[test]
fn test_running_product_single() {
assert_eq!(running_product(&[7]), vec![7]);
}
#[test]
fn test_running_sum_until_terminates_early() {
// 1, 3, 6 are <= 6; next would be 10 > 6, so stops
assert_eq!(running_sum_until(&[1, 2, 3, 4, 5], 6), vec![1, 3, 6]);
}
#[test]
fn test_running_sum_until_no_early_stop() {
assert_eq!(running_sum_until(&[1, 2, 3], 100), vec![1, 3, 6]);
}
#[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_generic_scan_sum() {
let result = scan(0i64, |a, b| a + b, &[1, 2, 3, 4, 5]);
assert_eq!(result, vec![1, 3, 6, 10, 15]);
}
#[test]
fn test_generic_scan_product() {
let result = scan(1i64, |a, b| a * b, &[1, 2, 3, 4, 5]);
assert_eq!(result, vec![1, 2, 6, 24, 120]);
}
}
✓ Tests
Rust test suite
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_running_sum_empty() {
assert_eq!(running_sum(&[]), Vec::<i64>::new());
}
#[test]
fn test_running_sum_single() {
assert_eq!(running_sum(&[42]), vec![42]);
}
#[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_with_negatives() {
let transactions = [100, -30, 50, -80, 200];
assert_eq!(running_sum(&transactions), vec![100, 70, 120, 40, 240]);
}
#[test]
fn test_running_product_multiple() {
assert_eq!(running_product(&[1, 2, 3, 4, 5]), vec![1, 2, 6, 24, 120]);
}
#[test]
fn test_running_product_single() {
assert_eq!(running_product(&[7]), vec![7]);
}
#[test]
fn test_running_sum_until_terminates_early() {
// 1, 3, 6 are <= 6; next would be 10 > 6, so stops
assert_eq!(running_sum_until(&[1, 2, 3, 4, 5], 6), vec![1, 3, 6]);
}
#[test]
fn test_running_sum_until_no_early_stop() {
assert_eq!(running_sum_until(&[1, 2, 3], 100), vec![1, 3, 6]);
}
#[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_generic_scan_sum() {
let result = scan(0i64, |a, b| a + b, &[1, 2, 3, 4, 5]);
assert_eq!(result, vec![1, 3, 6, 10, 15]);
}
#[test]
fn test_generic_scan_product() {
let result = scan(1i64, |a, b| a * b, &[1, 2, 3, 4, 5]);
assert_eq!(result, vec![1, 2, 6, 24, 120]);
}
}Deep Comparison
OCaml vs Rust: Stateful Accumulation with scan()
Side-by-Side Code
OCaml
let scan init f lst =
let (_, result) = List.fold_left (fun (acc, acc_list) x ->
let new_acc = f acc x in
(new_acc, acc_list @ [new_acc])
) (init, []) lst in
result
let () =
let nums = [1; 2; 3; 4; 5] in
let running_sum = scan 0 (+) nums in
Printf.printf "Running sum: %s\n"
(String.concat ", " (List.map string_of_int running_sum));
let transactions = [100; -30; 50; -80; 200] in
let balances = scan 0 (+) transactions in
Printf.printf "Balances: %s\n"
(String.concat ", " (List.map string_of_int balances))
Rust (idiomatic)
pub fn running_sum(nums: &[i64]) -> Vec<i64> {
nums.iter()
.scan(0i64, |state, &x| {
*state += x;
Some(*state)
})
.collect()
}
Rust (functional/generic — mirrors OCaml's scan init f lst)
pub fn scan<T, F>(init: T, mut f: F, items: &[T]) -> Vec<T>
where
T: Copy,
F: FnMut(T, T) -> T,
{
items
.iter()
.scan(init, |state, &x| {
*state = f(*state, x);
Some(*state)
})
.collect()
}
Rust (early termination — no OCaml equivalent without manual recursion)
pub fn running_sum_until(nums: &[i64], limit: i64) -> Vec<i64> {
nums.iter()
.scan(0i64, |state, &x| {
*state += x;
if *state > limit { None } else { Some(*state) }
})
.collect()
}
Type Signatures
| Concept | OCaml | Rust |
|---|---|---|
| scan signature | val scan : 'a -> ('a -> 'b -> 'a) -> 'b list -> 'a list | fn scan<T, F>(init: T, f: F, items: &[T]) -> Vec<T> |
| Iterator scan | N/A (must build with fold) | Iterator::scan(init, \|state, item\| -> Option<B>) |
| State threading | tuple in fold accumulator | &mut state in closure |
| Early termination | manual recursion required | None from closure stops iterator |
| Input type | 'b list | &[T] (borrowed slice) |
| Output type | 'a list | Vec<T> (owned) |
Key Insights
scan; it must be implemented using List.fold_left with a tuple accumulator (state, result_list). Rust provides Iterator::scan as a first-class lazy iterator adapter.scan is a lazy iterator — it produces values on demand and composes with other adapters without allocating intermediate collections. OCaml's fold_left-based scan builds the entire result list eagerly, and the acc_list @ [new_acc] pattern is O(n²) due to list append.&mut state — the closure mutates it in place, which is explicit and zero-cost. OCaml uses immutable tuple (acc, acc_list) replaced at each step, relying on the GC to reclaim old values.None from Rust's scan closure halts the iterator immediately — no values are computed beyond that point. Replicating this in OCaml requires switching to explicit recursion with a base case, since fold_left cannot short-circuit.scan adapter works over any Iterator, not just lists — it can scan over file lines, network packets, channels, or infinite ranges without buffering the entire input. This makes it suitable for streaming and real-time accumulation tasks that OCaml's list-based approach cannot express directly.When to Use Each Style
**Use idiomatic Rust (Iterator::scan) when:** you need a lazy, composable running accumulation — prefix sums, running totals, state machine output — especially over large or infinite sequences where you don't want to materialise the whole input first.
**Use the generic scan<T, F> wrapper when:** you want an API that directly mirrors the OCaml scan init f lst calling convention, passing the combining function as a value rather than inlining it in the closure.
**Use early-terminating scan (None return) when:** you want to take a prefix of the accumulation up to some condition — e.g., "give me balances until the account goes negative" — which fold cannot express without post-processing.
Exercises
running_average using scan with state (sum, count) and emitting sum / count as f64.scan_while_positive(nums: &[i64]) -> Vec<i64> that computes a running product but stops when it first becomes negative.