070: Scan Left

Difficulty: Intermediate Category: Functional Patterns Concept: Running accumulation: like fold but keeps intermediate results Key Insight: Scan produces all intermediate fold values. Rust's `.scan()` is stateful; OCaml builds the list manually.

// 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
}

fn main() {
    println!("running_sum([1,2,3,4]) = {:?}", running_sum(&[1, 2, 3, 4]));
    println!("running_product([1,2,3,4]) = {:?}", running_product(&[1, 2, 3, 4]));
    println!("running_max([3,1,4,1,5,9]) = {:?}", running_max(&[3, 1, 4, 1, 5, 9]));
}

#[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"

📊 Detailed 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