905 Intermediate

905-iterator-peekable — Iterator Peekable

Functional Programming

Tutorial

The Problem

Lexers and parsers routinely need to inspect the next token before deciding which production rule to apply, without consuming that token. Without peek, the only options are consuming and pushing back (requiring a separate buffer) or reading one token ahead manually. Rust's .peekable() adapter adds peek() — a reference to the next element without advancing the iterator. This is the minimal lookahead needed for LL(1) parsing, run-length encoding, and merge algorithms. OCaml's Stream module and the Angstrom parser combinator library serve similar roles.

🎯 Learning Outcomes

• Use .peekable() to add one-element lookahead to any iterator

• Implement group-consecutive using peek() to detect group boundaries

• Build a simple tokenizer using peekable char iteration with digit accumulation

• Understand how peek() returns Option<&Item> without advancing

• Compare with OCaml's Stream.peek and recursive lookahead patterns

Code Example

pub fn group_consecutive<T: PartialEq + Copy>(data: &[T]) -> Vec<Vec<T>> {
    let mut iter = data.iter().peekable();
    let mut groups = Vec::new();

    while let Some(&val) = iter.peek() {
        let mut group = Vec::new();
        while iter.peek() == Some(&val) {
            group.push(*iter.next().unwrap());
        }
        groups.push(group);
    }
    groups
}

(* OCaml has no built-in peekable iterator; carry a mutable lookahead ref *)
type 'a peekable = {
  mutable peeked: 'a option;
  mutable rest: 'a list;
}

let make_peekable lst = { peeked = None; rest = lst }

let peek p =
  match p.peeked with
  | Some _ as v -> v
  | None ->
    match p.rest with
    | [] -> None
    | x :: _ -> p.peeked <- Some x; Some x

let next p =
  match p.peeked with
  | Some v ->
    p.peeked <- None;
    (match p.rest with _ :: xs -> p.rest <- xs | [] -> ());
    Some v
  | None ->
    match p.rest with
    | [] -> None
    | x :: xs -> p.rest <- xs; Some x

Key Differences

One-element buffer: Rust Peekable buffers exactly one element; OCaml Stream can buffer more; both handle LL(1) grammars.

Peek returns reference: Rust peek() returns Option<&Item> — a reference into the buffer; consuming requires a separate next() call; OCaml returns a copy.

Composability: Rust Peekable<I> is itself an iterator, composable with other adapters; OCaml Stream is a distinct type.

Type safety: Rust's typed Peekable<Chars> vs Peekable<Tokens> is explicit at the type level; OCaml streams are polymorphic.

OCaml Approach

OCaml uses Stream (deprecated in 4.14) or manual lookahead. A common pattern: let current = ref (Stream.next s) with explicit rebinding after consuming. Parser combinators like Angstrom provide peek_char, satisfy, and take_while as building blocks. Manual tokenizers in OCaml typically use a position index with explicit bounds checking: if !pos < len && s.[!pos] = c then .... OCaml's Scanf module handles many parsing cases without explicit peek.

Full Source

#![allow(clippy::all)]
//! 261. Lookahead with Peekable
//!
//! `Peekable` wraps any iterator and adds `peek()` — inspect the next element
//! without consuming it. Essential for parsers, run-length encoding, and
//! merge algorithms.

/// Group consecutive equal elements using `Peekable`.
pub fn group_consecutive<T: PartialEq + Copy>(data: &[T]) -> Vec<Vec<T>> {
    let mut iter = data.iter().peekable();
    let mut groups: Vec<Vec<T>> = Vec::new();

    while let Some(&val) = iter.peek() {
        let mut group = Vec::new();
        while iter.peek() == Some(&val) {
            // Safe: we just peeked a Some
            group.push(*iter.next().unwrap());
        }
        groups.push(group);
    }

    groups
}

/// Simple token type for a minimal tokenizer demo.
#[derive(Debug, PartialEq)]
pub enum Token {
    Number(i64),
    Plus,
    Minus,
    Unknown(char),
}

/// Tokenize a string of digits, `+`, and `-` using `Peekable` for lookahead.
pub fn tokenize(input: &str) -> Vec<Token> {
    let mut chars = input.chars().peekable();
    let mut tokens = Vec::new();

    while let Some(&ch) = chars.peek() {
        match ch {
            '0'..='9' => {
                let mut num_str = String::new();
                while chars.peek().is_some_and(|c| c.is_ascii_digit()) {
                    num_str.push(chars.next().unwrap());
                }
                tokens.push(Token::Number(num_str.parse().unwrap_or(0)));
            }
            '+' => {
                chars.next();
                tokens.push(Token::Plus);
            }
            '-' => {
                chars.next();
                tokens.push(Token::Minus);
            }
            ' ' => {
                chars.next();
            }
            other => {
                chars.next();
                tokens.push(Token::Unknown(other));
            }
        }
    }

    tokens
}

/// Merge two sorted slices using `Peekable` for head comparison.
pub fn merge_sorted(a: &[i32], b: &[i32]) -> Vec<i32> {
    let mut ia = a.iter().peekable();
    let mut ib = b.iter().peekable();
    let mut result = Vec::with_capacity(a.len() + b.len());

    loop {
        match (ia.peek(), ib.peek()) {
            (Some(&&x), Some(&&y)) => {
                if x <= y {
                    result.push(x);
                    ia.next();
                } else {
                    result.push(y);
                    ib.next();
                }
            }
            (Some(&&x), None) => {
                result.push(x);
                ia.next();
            }
            (None, Some(&&y)) => {
                result.push(y);
                ib.next();
            }
            (None, None) => break,
        }
    }

    result
}

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

    #[test]
    fn test_group_consecutive_basic() {
        let data = [1i32, 1, 2, 2, 2, 3, 1, 1];
        assert_eq!(
            group_consecutive(&data),
            vec![vec![1, 1], vec![2, 2, 2], vec![3], vec![1, 1]]
        );
    }

    #[test]
    fn test_group_consecutive_all_same() {
        assert_eq!(group_consecutive(&[5i32, 5, 5]), vec![vec![5, 5, 5]]);
    }

    #[test]
    fn test_group_consecutive_all_unique() {
        assert_eq!(
            group_consecutive(&[1i32, 2, 3]),
            vec![vec![1], vec![2], vec![3]]
        );
    }

    #[test]
    fn test_group_consecutive_empty() {
        assert_eq!(group_consecutive::<i32>(&[]), Vec::<Vec<i32>>::new());
    }

    #[test]
    fn test_tokenize_multi_digit_numbers() {
        assert_eq!(
            tokenize("123 + 45 - 6"),
            vec![
                Token::Number(123),
                Token::Plus,
                Token::Number(45),
                Token::Minus,
                Token::Number(6),
            ]
        );
    }

    #[test]
    fn test_tokenize_empty() {
        assert_eq!(tokenize(""), vec![]);
    }

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

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

    #[test]
    fn test_peek_does_not_consume() {
        let mut iter = [10i32, 20, 30].iter().peekable();
        let first_peek = iter.peek().copied();
        let second_peek = iter.peek().copied();
        let consumed = iter.next().copied();
        assert_eq!(first_peek, Some(&10i32));
        assert_eq!(second_peek, Some(&10i32));
        assert_eq!(consumed, Some(10i32));
        assert_eq!(iter.next().copied(), Some(20i32));
    }
}

(* 261. Lookahead with Peekable - OCaml *)

type 'a peekable = {
  mutable peeked: 'a option;
  mutable rest: 'a list;
}

let make_peekable lst = { peeked = None; rest = lst }

let peek p =
  match p.peeked with
  | Some _ as v -> v
  | None ->
    (match p.rest with
     | [] -> None
     | x :: _ -> p.peeked <- Some x; Some x)

let next p =
  match p.peeked with
  | Some v -> p.peeked <- None; (match p.rest with _ :: xs -> p.rest <- xs | [] -> ()); Some v
  | None ->
    match p.rest with
    | [] -> None
    | x :: xs -> p.rest <- xs; Some x

let () =
  let p = make_peekable [1; 2; 3; 4; 5] in
  Printf.printf "Peek: %s\n" (match peek p with Some n -> string_of_int n | None -> "None");
  Printf.printf "Next: %s\n" (match next p with Some n -> string_of_int n | None -> "None");
  Printf.printf "Next: %s\n" (match next p with Some n -> string_of_int n | None -> "None");
  let p2 = make_peekable [1; 1; 2; 2; 3] in
  let rec group_eq () =
    match next p2 with
    | None -> []
    | Some x ->
      let rec collect acc =
        match peek p2 with
        | Some y when y = x -> ignore (next p2); collect (x :: acc)
        | _ -> List.rev (x :: acc)
      in
      collect [] :: group_eq ()
  in
  let groups = group_eq () in
  List.iter (fun g ->
    Printf.printf "[%s] " (String.concat ";" (List.map string_of_int g))
  ) groups;
  print_newline ()

✓ Tests Rust test suite

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

    #[test]
    fn test_group_consecutive_basic() {
        let data = [1i32, 1, 2, 2, 2, 3, 1, 1];
        assert_eq!(
            group_consecutive(&data),
            vec![vec![1, 1], vec![2, 2, 2], vec![3], vec![1, 1]]
        );
    }

    #[test]
    fn test_group_consecutive_all_same() {
        assert_eq!(group_consecutive(&[5i32, 5, 5]), vec![vec![5, 5, 5]]);
    }

    #[test]
    fn test_group_consecutive_all_unique() {
        assert_eq!(
            group_consecutive(&[1i32, 2, 3]),
            vec![vec![1], vec![2], vec![3]]
        );
    }

    #[test]
    fn test_group_consecutive_empty() {
        assert_eq!(group_consecutive::<i32>(&[]), Vec::<Vec<i32>>::new());
    }

    #[test]
    fn test_tokenize_multi_digit_numbers() {
        assert_eq!(
            tokenize("123 + 45 - 6"),
            vec![
                Token::Number(123),
                Token::Plus,
                Token::Number(45),
                Token::Minus,
                Token::Number(6),
            ]
        );
    }

    #[test]
    fn test_tokenize_empty() {
        assert_eq!(tokenize(""), vec![]);
    }

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

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

    #[test]
    fn test_peek_does_not_consume() {
        let mut iter = [10i32, 20, 30].iter().peekable();
        let first_peek = iter.peek().copied();
        let second_peek = iter.peek().copied();
        let consumed = iter.next().copied();
        assert_eq!(first_peek, Some(&10i32));
        assert_eq!(second_peek, Some(&10i32));
        assert_eq!(consumed, Some(10i32));
        assert_eq!(iter.next().copied(), Some(20i32));
    }
}

Deep Comparison

OCaml vs Rust: Lookahead with Peekable

Side-by-Side Code

OCaml

(* OCaml has no built-in peekable iterator; carry a mutable lookahead ref *)
type 'a peekable = {
  mutable peeked: 'a option;
  mutable rest: 'a list;
}

let make_peekable lst = { peeked = None; rest = lst }

let peek p =
  match p.peeked with
  | Some _ as v -> v
  | None ->
    match p.rest with
    | [] -> None
    | x :: _ -> p.peeked <- Some x; Some x

let next p =
  match p.peeked with
  | Some v ->
    p.peeked <- None;
    (match p.rest with _ :: xs -> p.rest <- xs | [] -> ());
    Some v
  | None ->
    match p.rest with
    | [] -> None
    | x :: xs -> p.rest <- xs; Some x

Rust (idiomatic — stdlib Peekable)

pub fn group_consecutive<T: PartialEq + Copy>(data: &[T]) -> Vec<Vec<T>> {
    let mut iter = data.iter().peekable();
    let mut groups = Vec::new();

    while let Some(&val) = iter.peek() {
        let mut group = Vec::new();
        while iter.peek() == Some(&val) {
            group.push(*iter.next().unwrap());
        }
        groups.push(group);
    }
    groups
}

Rust (tokenizer using Peekable)

pub fn tokenize(input: &str) -> Vec<Token> {
    let mut chars = input.chars().peekable();
    let mut tokens = Vec::new();

    while let Some(&ch) = chars.peek() {
        match ch {
            '0'..='9' => {
                let mut num_str = String::new();
                while chars.peek().map_or(false, |c| c.is_ascii_digit()) {
                    num_str.push(chars.next().unwrap());
                }
                tokens.push(Token::Number(num_str.parse().unwrap_or(0)));
            }
            '+' => { chars.next(); tokens.push(Token::Plus); }
            '-' => { chars.next(); tokens.push(Token::Minus); }
            ' ' => { chars.next(); }
            other => { chars.next(); tokens.push(Token::Unknown(other)); }
        }
    }
    tokens
}

Type Signatures

Concept	OCaml	Rust
Peekable wrapper	`'a peekable` (custom mutable record)	`Peekable<I: Iterator>` (stdlib adapter)
Peek operation	`peek : 'a peekable -> 'a option`	`fn peek(&mut self) -> Option<&<I as Iterator>::Item>`
Advance	`next : 'a peekable -> 'a option`	`fn next(&mut self) -> Option<I::Item>`
Construction	`make_peekable : 'a list -> 'a peekable`	`.peekable()` on any iterator

Key Insights

Standard vs. manual: Rust's stdlib ships Peekable<I> as a zero-cost iterator adapter; OCaml's standard library has no equivalent, requiring a hand-rolled mutable record with a peeked slot.

Ownership through the peek reference: peek() returns Option<&Item> — a reference into the adapter's internal buffer. You can inspect the value without moving it; calling next() later yields the owned value.

No "put-back" needed: Both languages solve the same problem — you can't un-consume an iterator element — but Rust encapsulates the buffer inside Peekable, whereas OCaml requires the caller to manage the peeked field manually.

Lifetime-free lookahead: Even though peek() returns a reference, the borrow checker ensures it does not escape past the next next() call — no unsafe code, no lifetimes visible at the call site.

Composability: Because Peekable<I> itself implements Iterator, it can be chained with .map(), .filter(), .zip() and any other adapter — OCaml's mutable record cannot.

When to Use Each Style

**Use idiomatic Rust (Peekable)** when you need to inspect the next element in any iterator pipeline — parsers, tokenizers, run-length encoders, merge steps.

Use the recursive/functional style when the algorithm is inherently recursive and the lookahead is captured naturally by pattern matching on the tail of a list — e.g., match list with [a; b; ..rest].

Exercises

Use peekable to implement deduplicate<T: PartialEq + Clone>(iter: impl Iterator<Item=T>) -> Vec<T> that removes consecutive duplicates.

Build a simple expression tokenizer that handles multi-character operators (<=, >=, ==) using two-character lookahead.

Implement merge_sorted<T: Ord + Clone>(a: impl Iterator<Item=T>, b: impl Iterator<Item=T>) -> Vec<T> using peekable on both iterators.

Open Source Repos

functional-rust

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

Rust