887 Intermediate

887-windows-chunks — Windows and Chunks

Functional Programming

Tutorial

The Problem

Sliding window algorithms process overlapping sub-sequences for signal analysis, moving averages, and local extrema detection. Non-overlapping chunking processes data in fixed batches for pagination, block processing, and parallel work distribution. Both are fundamental in data processing pipelines. Rust provides .windows(n) (overlapping, zero-copy) and .chunks(n) / .chunks_exact(n) (non-overlapping) as built-in slice methods. These are unique in that they operate on slices (borrowing from the original data) rather than consuming iterators, enabling zero-allocation window and chunk processing.

🎯 Learning Outcomes

• Use .windows(n) for overlapping sliding windows over slices

• Use .chunks(n) for non-overlapping batch processing

• Use .chunks_exact(n) when uniform chunk sizes are required and remainders should be handled separately

• Compute moving averages, pairwise differences, and local maxima using windows

• Compare with OCaml's recursive list splitting for similar operations

Code Example

pub fn moving_average(data: &[f64], window_size: usize) -> Vec<f64> {
    data.windows(window_size)
        .map(|w| w.iter().sum::<f64>() / window_size as f64)
        .collect()
}

pub fn chunk_sums(data: &[i32], size: usize) -> Vec<i32> {
    data.chunks(size).map(|c| c.iter().sum()).collect()
}

pub fn chunk_exact_sums(data: &[i32], size: usize) -> (Vec<i32>, &[i32]) {
    let iter = data.chunks_exact(size);
    let remainder = iter.remainder();
    let sums = iter.map(|c| c.iter().sum()).collect();
    (sums, remainder)
}

let windows n lst =
  let arr = Array.of_list lst in
  let len = Array.length arr in
  if n > len then []
  else List.init (len - n + 1) (fun i ->
    Array.to_list (Array.sub arr i n))

let moving_average n lst =
  let ws = windows n (List.map float_of_int lst) in
  List.map (fun w ->
    List.fold_left (+.) 0.0 w /. float_of_int n) ws

let chunks n lst =
  let rec aux acc current count = function
    | [] -> List.rev (if current = [] then acc else List.rev current :: acc)
    | x :: rest ->
      if count = n then aux (List.rev current :: acc) [x] 1 rest
      else aux acc (x :: current) (count + 1) rest
  in aux [] [] 0 lst

Key Differences

Zero-copy: Rust .windows(n) returns references into the original slice — no allocation; OCaml typically allocates new lists or arrays per window.

Exact chunks: chunks_exact provides a separate remainder accessor — OCaml requires explicit length-check after manual chunking.

Built-in vs recursive: Rust has first-class slice methods; OCaml requires writing recursive functions for window and chunk operations.

Bounds safety: Rust windows/chunks are bounds-safe by construction; OCaml Array.sub can raise Invalid_argument on out-of-bounds.

OCaml Approach

OCaml lacks built-in window/chunk operations on lists. The idiomatic approach uses recursive functions: let rec windows n lst = match lst with | [] -> [] | _ -> if List.length lst < n then [] else (List.filteri (fun i _ -> i < n) lst) :: windows n (List.tl lst). For arrays, Array.sub arr i n extracts a chunk. OCaml's Array.init with modular arithmetic can implement circular windows. The absence of built-in windows/chunks is a significant usability difference.

Full Source

#![allow(clippy::all)]
// Example 093: Windows and Chunks
// Sliding window algorithms in Rust

// === Approach 1: Windows (overlapping) ===

// Idiomatic Rust: uses built-in .windows(n) for zero-copy overlapping slices
pub fn moving_average(data: &[f64], window_size: usize) -> Vec<f64> {
    if window_size == 0 {
        return vec![];
    }
    data.windows(window_size)
        .map(|w| w.iter().sum::<f64>() / window_size as f64)
        .collect()
}

pub fn pairwise_diff(data: &[i32]) -> Vec<i32> {
    data.windows(2).map(|w| w[1] - w[0]).collect()
}

// Returns the center value of every window where it is strictly greater than both neighbors
pub fn local_maxima(data: &[i32]) -> Vec<i32> {
    data.windows(3)
        .filter(|w| w[1] > w[0] && w[1] > w[2])
        .map(|w| w[1])
        .collect()
}

// === Approach 2: Chunks (non-overlapping) ===

// Idiomatic Rust: .chunks(n) slices into non-overlapping blocks; last may be shorter
pub fn chunk_sums(data: &[i32], size: usize) -> Vec<i32> {
    data.chunks(size).map(|c| c.iter().sum()).collect()
}

pub fn chunk_maxes(data: &[i32], size: usize) -> Vec<i32> {
    data.chunks(size)
        .map(|c| *c.iter().max().unwrap())
        .collect()
}

// chunks_exact skips the remainder; access leftover via .remainder()
pub fn chunk_exact_sums(data: &[i32], size: usize) -> (Vec<i32>, &[i32]) {
    let iter = data.chunks_exact(size);
    let remainder = iter.remainder();
    let sums = iter.map(|c| c.iter().sum()).collect();
    (sums, remainder)
}

// === Approach 3: Manual recursive (OCaml-style) ===

// Recursive windows — mirrors the OCaml implementation
pub fn windows_recursive<T: Clone>(slice: &[T], n: usize) -> Vec<Vec<T>> {
    if n == 0 || slice.len() < n {
        return vec![];
    }
    let mut result = vec![slice[..n].to_vec()];
    result.extend(windows_recursive(&slice[1..], n));
    result
}

// Recursive chunks — mirrors OCaml List-based chunking
pub fn chunks_recursive<T: Clone>(slice: &[T], n: usize) -> Vec<Vec<T>> {
    if n == 0 || slice.is_empty() {
        return vec![];
    }
    let end = n.min(slice.len());
    let mut result = vec![slice[..end].to_vec()];
    result.extend(chunks_recursive(&slice[end..], n));
    result
}

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

    // --- moving_average ---

    #[test]
    fn test_moving_average_basic() {
        let data = [1.0, 2.0, 3.0, 4.0, 5.0];
        let result = moving_average(&data, 3);
        assert_eq!(result, vec![2.0, 3.0, 4.0]);
    }

    #[test]
    fn test_moving_average_window_equals_len() {
        let data = [1.0, 2.0, 3.0];
        let result = moving_average(&data, 3);
        assert_eq!(result, vec![2.0]);
    }

    #[test]
    fn test_moving_average_window_larger_than_data() {
        let data = [1.0, 2.0];
        let result = moving_average(&data, 5);
        assert!(result.is_empty());
    }

    #[test]
    fn test_moving_average_zero_window() {
        let data = [1.0, 2.0, 3.0];
        let result = moving_average(&data, 0);
        assert!(result.is_empty());
    }

    // --- pairwise_diff ---

    #[test]
    fn test_pairwise_diff_basic() {
        assert_eq!(pairwise_diff(&[1, 3, 6, 10]), vec![2, 3, 4]);
    }

    #[test]
    fn test_pairwise_diff_single() {
        assert!(pairwise_diff(&[42]).is_empty());
    }

    #[test]
    fn test_pairwise_diff_empty() {
        assert!(pairwise_diff(&[]).is_empty());
    }

    // --- local_maxima ---

    #[test]
    fn test_local_maxima_basic() {
        assert_eq!(local_maxima(&[1, 3, 2, 5, 4]), vec![3, 5]);
    }

    #[test]
    fn test_local_maxima_none() {
        assert!(local_maxima(&[1, 2, 3, 4]).is_empty());
    }

    // --- chunk_sums ---

    #[test]
    fn test_chunk_sums_even_split() {
        assert_eq!(chunk_sums(&[1, 2, 3, 4, 5, 6], 2), vec![3, 7, 11]);
    }

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

    #[test]
    fn test_chunk_sums_empty() {
        assert!(chunk_sums(&[], 3).is_empty());
    }

    // --- chunk_exact_sums ---

    #[test]
    fn test_chunk_exact_sums_remainder() {
        let data = [1, 2, 3, 4, 5];
        let (sums, remainder) = chunk_exact_sums(&data, 2);
        assert_eq!(sums, vec![3, 7]);
        assert_eq!(remainder, &[5]);
    }

    #[test]
    fn test_chunk_exact_sums_no_remainder() {
        let data = [1, 2, 3, 4];
        let (sums, remainder) = chunk_exact_sums(&data, 2);
        assert_eq!(sums, vec![3, 7]);
        assert!(remainder.is_empty());
    }

    // --- recursive variants ---

    #[test]
    fn test_windows_recursive() {
        let result = windows_recursive(&[1, 2, 3, 4, 5], 3);
        assert_eq!(result, vec![vec![1, 2, 3], vec![2, 3, 4], vec![3, 4, 5]]);
    }

    #[test]
    fn test_windows_recursive_too_large() {
        let result = windows_recursive(&[1, 2], 5);
        assert!(result.is_empty());
    }

    #[test]
    fn test_chunks_recursive() {
        let result = chunks_recursive(&[1, 2, 3, 4, 5], 3);
        assert_eq!(result, vec![vec![1, 2, 3], vec![4, 5]]);
    }

    #[test]
    fn test_chunks_recursive_even() {
        let result = chunks_recursive(&[1, 2, 3, 4], 2);
        assert_eq!(result, vec![vec![1, 2], vec![3, 4]]);
    }
}

(* Example 093: Windows and Chunks *)
(* Sliding window algorithms *)

(* Approach 1: Windows (sliding window) *)
let windows n lst =
  let arr = Array.of_list lst in
  let len = Array.length arr in
  if n > len then []
  else List.init (len - n + 1) (fun i ->
    Array.to_list (Array.sub arr i n))

let moving_average n lst =
  let ws = windows n (List.map float_of_int lst) in
  List.map (fun w ->
    List.fold_left (+.) 0.0 w /. float_of_int n
  ) ws

let pairwise_diff lst =
  let ws = windows 2 lst in
  List.map (function [a; b] -> b - a | _ -> 0) ws

(* Approach 2: Chunks (non-overlapping) *)
let chunks n lst =
  let rec aux acc current count = function
    | [] -> List.rev (if current = [] then acc else List.rev current :: acc)
    | x :: rest ->
      if count = n then
        aux (List.rev current :: acc) [x] 1 rest
      else
        aux acc (x :: current) (count + 1) rest
  in
  aux [] [] 0 lst

let chunks_exact n lst =
  let all = chunks n lst in
  List.filter (fun chunk -> List.length chunk = n) all

(* Approach 3: Practical algorithms *)
let local_maxima lst =
  windows 3 lst
  |> List.filter (function [a; b; c] -> b > a && b > c | _ -> false)
  |> List.map (function [_; b; _] -> b | _ -> 0)

let contains_pattern pattern lst =
  let n = List.length pattern in
  windows n lst |> List.exists (fun w -> w = pattern)

(* Tests *)
let () =
  assert (windows 3 [1;2;3;4;5] = [[1;2;3]; [2;3;4]; [3;4;5]]);
  assert (windows 2 [1;2;3] = [[1;2]; [2;3]]);
  assert (windows 5 [1;2;3] = []);

  let avg = moving_average 3 [1;2;3;4;5] in
  assert (abs_float (List.hd avg -. 2.0) < 0.001);

  assert (pairwise_diff [1;3;6;10] = [2; 3; 4]);

  assert (chunks 2 [1;2;3;4;5] = [[1;2]; [3;4]; [5]]);
  assert (chunks_exact 2 [1;2;3;4;5] = [[1;2]; [3;4]]);

  assert (local_maxima [1;3;2;5;4;6;1] = [3; 5; 6]);
  assert (contains_pattern [3;4;5] [1;2;3;4;5;6]);
  assert (not (contains_pattern [3;5] [1;2;3;4;5;6]));

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    // --- moving_average ---

    #[test]
    fn test_moving_average_basic() {
        let data = [1.0, 2.0, 3.0, 4.0, 5.0];
        let result = moving_average(&data, 3);
        assert_eq!(result, vec![2.0, 3.0, 4.0]);
    }

    #[test]
    fn test_moving_average_window_equals_len() {
        let data = [1.0, 2.0, 3.0];
        let result = moving_average(&data, 3);
        assert_eq!(result, vec![2.0]);
    }

    #[test]
    fn test_moving_average_window_larger_than_data() {
        let data = [1.0, 2.0];
        let result = moving_average(&data, 5);
        assert!(result.is_empty());
    }

    #[test]
    fn test_moving_average_zero_window() {
        let data = [1.0, 2.0, 3.0];
        let result = moving_average(&data, 0);
        assert!(result.is_empty());
    }

    // --- pairwise_diff ---

    #[test]
    fn test_pairwise_diff_basic() {
        assert_eq!(pairwise_diff(&[1, 3, 6, 10]), vec![2, 3, 4]);
    }

    #[test]
    fn test_pairwise_diff_single() {
        assert!(pairwise_diff(&[42]).is_empty());
    }

    #[test]
    fn test_pairwise_diff_empty() {
        assert!(pairwise_diff(&[]).is_empty());
    }

    // --- local_maxima ---

    #[test]
    fn test_local_maxima_basic() {
        assert_eq!(local_maxima(&[1, 3, 2, 5, 4]), vec![3, 5]);
    }

    #[test]
    fn test_local_maxima_none() {
        assert!(local_maxima(&[1, 2, 3, 4]).is_empty());
    }

    // --- chunk_sums ---

    #[test]
    fn test_chunk_sums_even_split() {
        assert_eq!(chunk_sums(&[1, 2, 3, 4, 5, 6], 2), vec![3, 7, 11]);
    }

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

    #[test]
    fn test_chunk_sums_empty() {
        assert!(chunk_sums(&[], 3).is_empty());
    }

    // --- chunk_exact_sums ---

    #[test]
    fn test_chunk_exact_sums_remainder() {
        let data = [1, 2, 3, 4, 5];
        let (sums, remainder) = chunk_exact_sums(&data, 2);
        assert_eq!(sums, vec![3, 7]);
        assert_eq!(remainder, &[5]);
    }

    #[test]
    fn test_chunk_exact_sums_no_remainder() {
        let data = [1, 2, 3, 4];
        let (sums, remainder) = chunk_exact_sums(&data, 2);
        assert_eq!(sums, vec![3, 7]);
        assert!(remainder.is_empty());
    }

    // --- recursive variants ---

    #[test]
    fn test_windows_recursive() {
        let result = windows_recursive(&[1, 2, 3, 4, 5], 3);
        assert_eq!(result, vec![vec![1, 2, 3], vec![2, 3, 4], vec![3, 4, 5]]);
    }

    #[test]
    fn test_windows_recursive_too_large() {
        let result = windows_recursive(&[1, 2], 5);
        assert!(result.is_empty());
    }

    #[test]
    fn test_chunks_recursive() {
        let result = chunks_recursive(&[1, 2, 3, 4, 5], 3);
        assert_eq!(result, vec![vec![1, 2, 3], vec![4, 5]]);
    }

    #[test]
    fn test_chunks_recursive_even() {
        let result = chunks_recursive(&[1, 2, 3, 4], 2);
        assert_eq!(result, vec![vec![1, 2], vec![3, 4]]);
    }
}

Deep Comparison

OCaml vs Rust: Windows and Chunks

Side-by-Side Code

OCaml

let windows n lst =
  let arr = Array.of_list lst in
  let len = Array.length arr in
  if n > len then []
  else List.init (len - n + 1) (fun i ->
    Array.to_list (Array.sub arr i n))

let moving_average n lst =
  let ws = windows n (List.map float_of_int lst) in
  List.map (fun w ->
    List.fold_left (+.) 0.0 w /. float_of_int n) ws

let chunks n lst =
  let rec aux acc current count = function
    | [] -> List.rev (if current = [] then acc else List.rev current :: acc)
    | x :: rest ->
      if count = n then aux (List.rev current :: acc) [x] 1 rest
      else aux acc (x :: current) (count + 1) rest
  in aux [] [] 0 lst

Rust (idiomatic)

pub fn moving_average(data: &[f64], window_size: usize) -> Vec<f64> {
    data.windows(window_size)
        .map(|w| w.iter().sum::<f64>() / window_size as f64)
        .collect()
}

pub fn chunk_sums(data: &[i32], size: usize) -> Vec<i32> {
    data.chunks(size).map(|c| c.iter().sum()).collect()
}

pub fn chunk_exact_sums(data: &[i32], size: usize) -> (Vec<i32>, &[i32]) {
    let iter = data.chunks_exact(size);
    let remainder = iter.remainder();
    let sums = iter.map(|c| c.iter().sum()).collect();
    (sums, remainder)
}

Rust (functional/recursive)

pub fn windows_recursive<T: Clone>(slice: &[T], n: usize) -> Vec<Vec<T>> {
    if n == 0 || slice.len() < n {
        return vec![];
    }
    let mut result = vec![slice[..n].to_vec()];
    result.extend(windows_recursive(&slice[1..], n));
    result
}

pub fn chunks_recursive<T: Clone>(slice: &[T], n: usize) -> Vec<Vec<T>> {
    if n == 0 || slice.is_empty() {
        return vec![];
    }
    let end = n.min(slice.len());
    let mut result = vec![slice[..end].to_vec()];
    result.extend(chunks_recursive(&slice[end..], n));
    result
}

Type Signatures

Concept	OCaml	Rust
Windows	`val windows : int -> 'a list -> 'a list list`	`fn windows_recursive<T: Clone>(&[T], usize) -> Vec<Vec<T>>`
Built-in windows	`Array.sub` (copies)	`slice.windows(n)` → `Iterator<Item=&[T]>` (zero-copy)
Chunks	manual recursive + `Array.sub`	`slice.chunks(n)` → `Iterator<Item=&[T]>` (zero-copy)
Exact chunks	manual boundary check	`slice.chunks_exact(n)` + `.remainder()`
Moving average	`List.fold_left` over sub-lists	`.map(\|w\| w.iter().sum::<f64>() / n as f64)`

Key Insights

Zero-copy vs O(n²) allocation: OCaml's Array.sub allocates a new array for every window or chunk — O(n·k) total allocations. Rust's .windows(n) and .chunks(n) hand out &[T] slice references into the original data with no copying whatsoever.

Built-in vs hand-rolled: OCaml has no standard windows or chunks on lists; you must write them from scratch using Array.sub or recursive list manipulation. Rust bakes both directly into the slice type as iterator-producing methods.

**chunks_exact for strict batching:** Rust provides chunks_exact(n) which silently skips the final partial chunk and exposes it through .remainder(). This makes it easy to separate "full batches" from "leftover" without manual length arithmetic.

Iterator composability: Because .windows and .chunks produce iterators, they compose directly with .map, .filter, and .collect — no intermediate List.map steps needed. The OCaml versions must go through an intermediate list of lists.

Recursive style as explicit OCaml mirror: The recursive Rust implementations (windows_recursive, chunks_recursive) use slice-slicing &slice[1..] and &slice[end..] instead of list destructuring, but the structural recursion is identical to the OCaml versions — demonstrating how Rust can mimic functional decomposition while still being safe and zero-cost.

When to Use Each Style

**Use idiomatic Rust (.windows / .chunks) when:** processing slices in production code — it is zero-copy, bounds-checked, and composes cleanly with iterators. Use recursive Rust when: teaching the OCaml parallel explicitly, or when building a generic abstraction over a custom data structure that doesn't expose slices.

Exercises

Use .windows(5) to find the position of the subarray with the maximum sum in a slice of integers.

Implement chunk_by_weight<T: Clone, F: Fn(&T) -> usize> that splits a slice into chunks where each chunk's total weight stays below a limit.

Write overlapping_pairs_sum using .windows(2) that returns the sum of every adjacent pair.

Open Source Repos

functional-rust

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

Rust