261 Intermediate

261: Lookahead with Peekable

Functional Programming

Tutorial

The Problem

Many parsing and grouping algorithms need to examine the next element before deciding whether to consume it. A lexer must decide if the current < starts <, <=, or << by looking ahead. A run-length encoder must check if the next element continues the current run. Without lookahead, you must buffer elements manually or restructure the algorithm. Peekable wraps any iterator to add a one-element lookahead without consuming the peeked element.

🎯 Learning Outcomes

• Understand how peek() inspects the next element without advancing the iterator

• Use Peekable to implement run-length grouping and lexer-style tokenization

• Recognize that peek() returns Option<&Item> — a reference to the next element

• Combine peek() with while let to consume elements conditionally

Code Example

#![allow(clippy::all)]
//! 261. Lookahead with Peekable
//!
//! `Peekable` adds `peek()` to inspect the next element without consuming it.

#[cfg(test)]
mod tests {
    #[test]
    fn test_peek_no_consume() {
        let mut iter = [1i32, 2, 3].iter().peekable();
        let p = iter.peek().copied().copied();
        let n = iter.next().copied();
        assert_eq!(p, Some(1));
        assert_eq!(n, Some(1));
        assert_eq!(iter.next().copied(), Some(2));
    }

    #[test]
    fn test_peek_groups() {
        let data = [1i32, 1, 2, 3, 3];
        let mut iter = data.iter().peekable();
        let mut groups: Vec<Vec<i32>> = Vec::new();
        while let Some(&val) = iter.peek() {
            let mut g = Vec::new();
            while iter.peek() == Some(&val) {
                g.push(*iter.next().unwrap());
            }
            groups.push(g);
        }
        assert_eq!(groups, vec![vec![1, 1], vec![2], vec![3, 3]]);
    }

    #[test]
    fn test_peek_empty() {
        let data: Vec<i32> = vec![];
        let mut p = data.iter().peekable();
        assert_eq!(p.peek(), None);
    }
}

(* 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 ()

Key Differences

Built-in support: Rust provides Peekable<I> as a standard adapter; OCaml requires manual buffering.

Reference semantics: peek() returns Option<&Item> — a reference — so the item remains available for next(); no copying occurs.

One-element buffer: Peekable buffers exactly one element; for deeper lookahead you need a different approach.

Parser combinators: Libraries like nom and pest build on this pattern for full recursive-descent parsing.

OCaml Approach

OCaml's standard library does not provide a built-in peekable abstraction. The idiomatic approach is to use a ref holding an optional buffered element, or to restructure the algorithm to pass the "next" element as an argument to recursive calls:

(* Manual lookahead with a buffer ref *)
let peekable seq =
  let buf = ref None in
  let peek () = match !buf with
    | Some v -> Some v
    | None -> let v = Seq.uncons seq in buf := Option.map fst v; Option.map fst v
  in ...

Full Source

#![allow(clippy::all)]
//! 261. Lookahead with Peekable
//!
//! `Peekable` adds `peek()` to inspect the next element without consuming it.

#[cfg(test)]
mod tests {
    #[test]
    fn test_peek_no_consume() {
        let mut iter = [1i32, 2, 3].iter().peekable();
        let p = iter.peek().copied().copied();
        let n = iter.next().copied();
        assert_eq!(p, Some(1));
        assert_eq!(n, Some(1));
        assert_eq!(iter.next().copied(), Some(2));
    }

    #[test]
    fn test_peek_groups() {
        let data = [1i32, 1, 2, 3, 3];
        let mut iter = data.iter().peekable();
        let mut groups: Vec<Vec<i32>> = Vec::new();
        while let Some(&val) = iter.peek() {
            let mut g = Vec::new();
            while iter.peek() == Some(&val) {
                g.push(*iter.next().unwrap());
            }
            groups.push(g);
        }
        assert_eq!(groups, vec![vec![1, 1], vec![2], vec![3, 3]]);
    }

    #[test]
    fn test_peek_empty() {
        let data: Vec<i32> = vec![];
        let mut p = data.iter().peekable();
        assert_eq!(p.peek(), None);
    }
}

(* 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 {
    #[test]
    fn test_peek_no_consume() {
        let mut iter = [1i32, 2, 3].iter().peekable();
        let p = iter.peek().copied().copied();
        let n = iter.next().copied();
        assert_eq!(p, Some(1));
        assert_eq!(n, Some(1));
        assert_eq!(iter.next().copied(), Some(2));
    }

    #[test]
    fn test_peek_groups() {
        let data = [1i32, 1, 2, 3, 3];
        let mut iter = data.iter().peekable();
        let mut groups: Vec<Vec<i32>> = Vec::new();
        while let Some(&val) = iter.peek() {
            let mut g = Vec::new();
            while iter.peek() == Some(&val) {
                g.push(*iter.next().unwrap());
            }
            groups.push(g);
        }
        assert_eq!(groups, vec![vec![1, 1], vec![2], vec![3, 3]]);
    }

    #[test]
    fn test_peek_empty() {
        let data: Vec<i32> = vec![];
        let mut p = data.iter().peekable();
        assert_eq!(p.peek(), None);
    }
}

Exercises

Use Peekable to implement a simple tokenizer that merges consecutive digit characters into a single number token.

Build a group_consecutive function that groups adjacent equal elements without allocating a combined collection first.

Use peek() to implement a merge_sorted function that merges two sorted iterators into one sorted output without a temporary buffer.

Open Source Repos

functional-rust

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

Rust