096 Intermediate

096 — Exact Size Iterator

Functional Programming

Tutorial

The Problem

Demonstrate Rust's ExactSizeIterator trait — iterators that know their length in O(1). Show that Vec::iter(), ranges, and enumerate all implement ExactSizeIterator, enabling .len() without traversal. Demonstrate chunks_exact for obtaining only full-sized chunks plus a remainder. Compare with OCaml's O(1) Array.length versus O(n) List.length.

🎯 Learning Outcomes

• Call .len() on any ExactSizeIterator in O(1)

• Understand that .len() on iterators is distinct from .count() (which consumes)

• Use chunks_exact(n) to iterate only complete chunks and access the remainder

• Distinguish ExactSizeIterator (knows length) from Iterator (does not)

• Map Rust's array/Vec O(1) length to OCaml's Array.length O(1)

• Recognise when knowing size ahead of time enables Vec::with_capacity

Code Example

#![allow(clippy::all)]
// 096: Exact Size Iterator

#[cfg(test)]
mod tests {
    #[test]
    fn test_exact_size() {
        let v = vec![1, 2, 3, 4, 5];
        assert_eq!(v.iter().len(), 5);
        assert_eq!((0..10).len(), 10);
    }

    #[test]
    fn test_enumerate_len() {
        let v = vec!["a", "b", "c"];
        let e: Vec<_> = v.iter().enumerate().collect();
        assert_eq!(e, vec![(0, &"a"), (1, &"b"), (2, &"c")]);
    }

    #[test]
    fn test_chunks_exact() {
        let v = vec![1, 2, 3, 4, 5];
        let c: Vec<&[i32]> = v.chunks_exact(2).collect();
        assert_eq!(c, vec![&[1, 2][..], &[3, 4][..]]);
        assert_eq!(v.chunks_exact(2).remainder(), &[5]);
    }
}

(* 096: Exact Size *)
(* OCaml: List.length is O(n), Array.length is O(1) *)

let array_len arr = Array.length arr  (* O(1) *)
let list_len lst = List.length lst    (* O(n) *)

(* Sized iteration *)
let enumerate lst =
  List.mapi (fun i x -> (i, x)) lst

let chunks_exact n lst =
  let len = List.length lst in
  let full = len / n in
  let rec aux acc i = function
    | _ when i >= full -> List.rev acc
    | lst ->
      let chunk = List.filteri (fun j _ -> j < n) lst in
      let rest = List.filteri (fun j _ -> j >= n) lst in
      aux (chunk :: acc) (i + 1) rest
  in
  aux [] 0 lst

(* Tests *)
let () =
  assert (array_len [|1;2;3|] = 3);
  assert (enumerate ["a";"b";"c"] = [(0,"a"); (1,"b"); (2,"c")]);
  assert (chunks_exact 2 [1;2;3;4;5] = [[1;2]; [3;4]]);
  Printf.printf "✓ All tests passed\n"

Key Differences

Aspect	Rust	OCaml
O(1) length	`ExactSizeIterator::len()`	`Array.length`
O(n) length	`Iterator::count()` (consumes!)	`List.length`
Chunks with remainder	`chunks_exact(n).remainder()`	Manual split
Enumerate	`.enumerate()` (preserves ExactSize)	`List.mapi`
Protocol	Trait `ExactSizeIterator`	No equivalent
Consuming length	`.count()` drains iterator	`Seq.length` or `List.length`

ExactSizeIterator::len() is non-consuming — unlike .count(), it does not advance the iterator. This is critical when you want to pre-allocate (Vec::with_capacity(iter.len())) without losing the ability to iterate.

OCaml Approach

OCaml arrays have O(1) Array.length; lists require O(n) List.length. There is no ExactSizeIterator protocol — arrays inherently carry their length, and sequential iteration with for i = 0 to Array.length a - 1 do naturally provides sized bounds. List.mapi provides enumerate-style indexed iteration.

Full Source

#![allow(clippy::all)]
// 096: Exact Size Iterator

#[cfg(test)]
mod tests {
    #[test]
    fn test_exact_size() {
        let v = vec![1, 2, 3, 4, 5];
        assert_eq!(v.iter().len(), 5);
        assert_eq!((0..10).len(), 10);
    }

    #[test]
    fn test_enumerate_len() {
        let v = vec!["a", "b", "c"];
        let e: Vec<_> = v.iter().enumerate().collect();
        assert_eq!(e, vec![(0, &"a"), (1, &"b"), (2, &"c")]);
    }

    #[test]
    fn test_chunks_exact() {
        let v = vec![1, 2, 3, 4, 5];
        let c: Vec<&[i32]> = v.chunks_exact(2).collect();
        assert_eq!(c, vec![&[1, 2][..], &[3, 4][..]]);
        assert_eq!(v.chunks_exact(2).remainder(), &[5]);
    }
}

(* 096: Exact Size *)
(* OCaml: List.length is O(n), Array.length is O(1) *)

let array_len arr = Array.length arr  (* O(1) *)
let list_len lst = List.length lst    (* O(n) *)

(* Sized iteration *)
let enumerate lst =
  List.mapi (fun i x -> (i, x)) lst

let chunks_exact n lst =
  let len = List.length lst in
  let full = len / n in
  let rec aux acc i = function
    | _ when i >= full -> List.rev acc
    | lst ->
      let chunk = List.filteri (fun j _ -> j < n) lst in
      let rest = List.filteri (fun j _ -> j >= n) lst in
      aux (chunk :: acc) (i + 1) rest
  in
  aux [] 0 lst

(* Tests *)
let () =
  assert (array_len [|1;2;3|] = 3);
  assert (enumerate ["a";"b";"c"] = [(0,"a"); (1,"b"); (2,"c")]);
  assert (chunks_exact 2 [1;2;3;4;5] = [[1;2]; [3;4]]);
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    #[test]
    fn test_exact_size() {
        let v = vec![1, 2, 3, 4, 5];
        assert_eq!(v.iter().len(), 5);
        assert_eq!((0..10).len(), 10);
    }

    #[test]
    fn test_enumerate_len() {
        let v = vec!["a", "b", "c"];
        let e: Vec<_> = v.iter().enumerate().collect();
        assert_eq!(e, vec![(0, &"a"), (1, &"b"), (2, &"c")]);
    }

    #[test]
    fn test_chunks_exact() {
        let v = vec![1, 2, 3, 4, 5];
        let c: Vec<&[i32]> = v.chunks_exact(2).collect();
        assert_eq!(c, vec![&[1, 2][..], &[3, 4][..]]);
        assert_eq!(v.chunks_exact(2).remainder(), &[5]);
    }
}

Deep Comparison

Core Insight

ExactSizeIterator knows its length upfront — enables optimized allocation and bounds checking

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

Write collect_with_capacity<I: ExactSizeIterator<Item=T>>(iter: I) -> Vec<T> that pre-allocates exactly the right capacity.

Implement ExactSizeIterator for a custom Counter struct that counts from start to end.

Show that .map(f) on an ExactSizeIterator preserves ExactSizeIterator by checking that the mapped iterator also has .len().

Use chunks_exact(3).remainder() to process a byte buffer in 3-byte UTF-8 sequences, handling the partial final chunk separately.

In OCaml, implement a sized_seq type that pairs a Seq.t with a known int length and implement map that preserves the size.

Open Source Repos

functional-rust

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

Rust