ExamplesBy LevelBy TopicLearning Paths
104 Intermediate
← 1041040 →

104-scan-left — Scan Left (Running Accumulation)

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "104-scan-left — Scan Left (Running Accumulation)" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. `fold` reduces a sequence to one value. Key difference from OCaml: 1. **Laziness**: Rust's `Iterator::scan` is lazy — values are computed only when consumed; OCaml's `List`

Tutorial

The Problem

fold reduces a sequence to one value. scan (also called scanl in Haskell or scan_left in OCaml) returns all intermediate accumulator values — a prefix sum, running maximum, or cumulative product. This is the essential operation for financial running totals, cumulative distribution functions, and online statistics algorithms.

Rust's Iterator::scan implements this lazily, making it composable with the full iterator adapter chain.

🎯 Learning Outcomes

  • • Use Iterator::scan to produce running totals and running extremes
  • • Implement a custom scan_left mirroring OCaml's List.scan_left
  • • Understand that scan is fold that emits intermediate results
  • • Apply scan to prefix sums, running maximum, and cumulative products
  • • Chain scan with other iterator adapters for complex streaming computations

    • Code Example

    xs.iter().scan(init, |state, &x| {
    *state = f(*state, x);
    Some(*state)
})

    Key Differences

  • Laziness: Rust's Iterator::scan is lazy — values are computed only when consumed; OCaml's List-based scan is strict.
  • State mutation: Rust's scan closure receives &mut state for mutation; OCaml's fold passes state by value (immutable by default).
  • Initial value inclusion: Rust's scan excludes the initial value by default; the running_sum function uses once(0).chain(...) to include it — matching OCaml's scan_left which includes the initial accumulator.
  • **scan_left name**: OCaml uses List.scan_left (or fold_left with accumulation); Rust uses Iterator::scan.

    • OCaml Approach

    let scan_left f init xs =
  List.fold_left (fun (acc, result) x ->
    let new_acc = f acc x in
    (new_acc, result @ [new_acc])
  ) (init, [init]) xs
  |> snd

    Base.List.folding_map provides a cleaner one-pass implementation. OCaml's lazy Seq.scan would be the equivalent of Rust's lazy Iterator::scan.

    Full Source

    #![allow(clippy::all)]
//! # Scan Left — Running Accumulation
//!
//! `scan` returns all intermediate results of a fold.
//! Rust's `Iterator::scan` method does this lazily.

// ---------------------------------------------------------------------------
// Approach A: Iterator::scan (idiomatic Rust)
// ---------------------------------------------------------------------------

pub fn running_sum(xs: &[i32]) -> Vec<i32> {
    let mut acc = 0;
    std::iter::once(0)
        .chain(xs.iter().map(move |&x| {
            acc += x;
            acc
        }))
        .collect()
}

pub fn running_max(xs: &[i32]) -> Vec<i32> {
    xs.iter()
        .scan(i32::MIN, |state, &x| {
            *state = (*state).max(x);
            Some(*state)
        })
        .collect()
}

// ---------------------------------------------------------------------------
// Approach B: Manual scan_left (mirrors OCaml)
// ---------------------------------------------------------------------------

pub fn scan_left<T: Clone, U: Clone>(f: impl Fn(&T, &U) -> T, init: T, xs: &[U]) -> Vec<T> {
    let mut result = Vec::with_capacity(xs.len() + 1);
    result.push(init.clone());
    let mut acc = init;
    for x in xs {
        acc = f(&acc, x);
        result.push(acc.clone());
    }
    result
}

// ---------------------------------------------------------------------------
// Approach C: Fold-based scan
// ---------------------------------------------------------------------------

pub fn scan_fold<T: Clone>(f: impl Fn(T, T) -> T, init: T, xs: &[T]) -> Vec<T> {
    xs.iter().fold(vec![init.clone()], |mut res, x| {
        let last = res.last().unwrap().clone();
        res.push(f(last, x.clone()));
        res
    })
}

#[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_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_scan_left() {
        let result = scan_left(|a: &i32, b: &i32| a + b, 0, &[1, 2, 3, 4, 5]);
        assert_eq!(result, vec![0, 1, 3, 6, 10, 15]);
    }

    #[test]
    fn test_scan_empty() {
        assert_eq!(scan_left(|a: &i32, b: &i32| a + b, 0, &[]), vec![0]);
    }

    #[test]
    fn test_scan_fold() {
        assert_eq!(scan_fold(|a, b| a + b, 0, &[1, 2, 3]), vec![0, 1, 3, 6]);
    }
}
    ✓ Tests Rust test suite 
    #[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_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_scan_left() {
        let result = scan_left(|a: &i32, b: &i32| a + b, 0, &[1, 2, 3, 4, 5]);
        assert_eq!(result, vec![0, 1, 3, 6, 10, 15]);
    }

    #[test]
    fn test_scan_empty() {
        assert_eq!(scan_left(|a: &i32, b: &i32| a + b, 0, &[]), vec![0]);
    }

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

    Deep Comparison

    Comparison: Scan Left — OCaml vs Rust

    Core Insight

    Scan is fold's verbose cousin — it keeps all intermediate results. OCaml lacks a built-in scan_left, so you build it by accumulating into a reversed list during fold_left. Rust provides Iterator::scan in the standard library, with a mutable state parameter — more flexible but slightly different semantics (it doesn't automatically include the initial value).

    OCaml

    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

    Rust — Iterator::scan

    xs.iter().scan(init, |state, &x| {
    *state = f(*state, x);
    Some(*state)
})

    Rust — Manual

    pub fn scan_left<T: Clone>(f: impl Fn(&T, &T) -> T, init: T, xs: &[T]) -> Vec<T> {
    let mut result = vec![init.clone()];
    let mut acc = init;
    for x in xs { acc = f(&acc, x); result.push(acc.clone()); }
    result
}

    Comparison Table

    AspectOCamlRust
    Built-inNoIterator::scan
    Returns initMust include manuallyNot included by default
    LazinessEager (list)Lazy (iterator)
    StateTuple (acc, result_list)&mut state parameter
    Reverse neededYes (List.rev)No (push appends)
    Result type'a listimpl Iterator<Item = T>

    Learner Notes

  • • **Iterator::scan quirk**: Rust's scan doesn't include the initial value — you need once(init).chain(scan(...)) if you want it
  • • Mutable state: Rust's scan gives &mut State — you mutate it and return Some(output), which can differ from state
  • • **List.rev cost**: OCaml's cons-based building produces reversed results; the final List.rev is O(n)
  • • Practical use: Running totals, prefix sums, moving averages — scan is underused but powerful
  • • Relationship: xs.fold(init, f) == xs.scan(init, f).last() — fold is scan without history

    • Exercises

  • Implement running_product(xs: &[i64]) -> Vec<i64> using scan, stopping accumulation at the first zero.
  • Write a cumulative_average(xs: &[f64]) -> Vec<f64> using scan that tracks both the running sum and count.
  • Use prefix sums to implement range_sum(prefix: &[i64], i: usize, j: usize) -> i64 with O(1) query time after O(n) preprocessing.

    • Open Source Repos

    functional-rust

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

    Rust