087 Intermediate

087 — Iterator Adapters

Functional Programming

Tutorial

The Problem

Implement custom iterator adapters — MyMap, MyFilter, and MyTake — by wrapping an inner iterator and implementing next. Bundle them into an extension trait MyIterExt for fluent chaining. Compare with OCaml's Seq-based my_map, my_filter, and my_take functions.

🎯 Learning Outcomes

• Model an iterator adapter as a struct holding an inner iterator and a function

• Use FnMut for adapter closures that may need mutable state (e.g. counting)

• Implement next for adapters by delegating to the inner iterator

• Create an extension trait to add adapter methods to all iterators

• Understand why adapter structs are generic over I: Iterator and F: FnMut

• Map Rust's adapter structs to OCaml's higher-order Seq-based functions

Code Example

//! Example 087: Iterator Adapters
//!
//! OCaml's `Seq.t` is a thunk that produces `Seq.Nil | Seq.Cons (x, rest)` on
//! demand. The reference example builds `my_map`, `my_filter`, `my_take`, and
//! `my_skip` by recursing over those thunks.
//!
//! Rust's [`Iterator`] trait already covers the same ground, so we mirror the
//! OCaml helpers as named adapter structs (`MyMap`, `MyFilter`, `MyTake`,
//! `MySkip`) and expose them through an extension trait [`MyIterExt`] for a
//! fluent `iter.my_filter(...).my_map(...).my_take(...)` style.

/// Adapter produced by [`MyIterExt::my_map`]; applies `f` to every yielded
/// item, mirroring OCaml's `my_map`.
pub struct MyMap<I, F> {
    iter: I,
    f: F,
}

impl<I, F, B> Iterator for MyMap<I, F>
where
    I: Iterator,
    F: FnMut(I::Item) -> B,
{
    type Item = B;

    fn next(&mut self) -> Option<B> {
        self.iter.next().map(&mut self.f)
    }
}

/// Adapter produced by [`MyIterExt::my_filter`]; yields only items where the
/// predicate returns `true`, mirroring OCaml's `my_filter`.
pub struct MyFilter<I, P> {
    iter: I,
    predicate: P,
}

impl<I, P> Iterator for MyFilter<I, P>
where
    I: Iterator,
    P: FnMut(&I::Item) -> bool,
{
    type Item = I::Item;

    fn next(&mut self) -> Option<I::Item> {
        self.iter.by_ref().find(|item| (self.predicate)(item))
    }
}

/// Adapter produced by [`MyIterExt::my_take`]; yields at most the first `n`
/// items, mirroring OCaml's `my_take`.
pub struct MyTake<I> {
    iter: I,
    remaining: usize,
}

impl<I: Iterator> Iterator for MyTake<I> {
    type Item = I::Item;

    fn next(&mut self) -> Option<I::Item> {
        if self.remaining == 0 {
            None
        } else {
            self.remaining -= 1;
            self.iter.next()
        }
    }
}

/// Adapter produced by [`MyIterExt::my_skip`]; discards the first `n` items
/// on the first `next` call, mirroring OCaml's `my_skip`.
pub struct MySkip<I> {
    iter: I,
    to_skip: usize,
}

impl<I: Iterator> Iterator for MySkip<I> {
    type Item = I::Item;

    fn next(&mut self) -> Option<I::Item> {
        while self.to_skip > 0 {
            self.iter.next()?;
            self.to_skip -= 1;
        }
        self.iter.next()
    }
}

/// Extension trait that adds the OCaml-named adapters to every [`Iterator`].
///
/// Bring it into scope with `use example_087_iterator_adapters::MyIterExt;` to
/// chain `my_map`, `my_filter`, `my_take`, and `my_skip` on any iterator.
pub trait MyIterExt: Iterator + Sized {
    /// Maps each item through `f`, like OCaml's `my_map`.
    fn my_map<F, B>(self, f: F) -> MyMap<Self, F>
    where
        F: FnMut(Self::Item) -> B,
    {
        MyMap { iter: self, f }
    }

    /// Keeps only items satisfying `predicate`, like OCaml's `my_filter`.
    fn my_filter<P>(self, predicate: P) -> MyFilter<Self, P>
    where
        P: FnMut(&Self::Item) -> bool,
    {
        MyFilter {
            iter: self,
            predicate,
        }
    }

    /// Yields at most the first `n` items, like OCaml's `my_take`.
    fn my_take(self, n: usize) -> MyTake<Self> {
        MyTake {
            iter: self,
            remaining: n,
        }
    }

    /// Discards the first `n` items, like OCaml's `my_skip`.
    fn my_skip(self, n: usize) -> MySkip<Self> {
        MySkip {
            iter: self,
            to_skip: n,
        }
    }
}

impl<I: Iterator> MyIterExt for I {}

/// Returns the OCaml example pipeline: the first five even squares of the
/// natural numbers, computed with the custom adapters.
pub fn even_squares() -> Vec<u64> {
    (0u64..)
        .my_filter(|x| x % 2 == 0)
        .my_map(|x| x * x)
        .my_take(5)
        .collect()
}

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

    #[test]
    fn my_map_doubles_each_item() {
        let v: Vec<i32> = (0..5).my_map(|x| x * 2).collect();
        assert_eq!(v, vec![0, 2, 4, 6, 8]);
    }

    #[test]
    fn my_filter_keeps_matching_items() {
        let v: Vec<i32> = (0..5).my_filter(|x| *x > 2).collect();
        assert_eq!(v, vec![3, 4]);
    }

    #[test]
    fn my_take_bounds_iteration() {
        let v: Vec<i32> = (0..5).my_take(3).collect();
        assert_eq!(v, vec![0, 1, 2]);
    }

    #[test]
    fn my_take_more_than_available_is_safe() {
        let v: Vec<i32> = (0..3).my_take(10).collect();
        assert_eq!(v, vec![0, 1, 2]);
    }

    #[test]
    fn my_skip_drops_prefix() {
        let v: Vec<i32> = (0..5).my_skip(3).collect();
        assert_eq!(v, vec![3, 4]);
    }

    #[test]
    fn my_skip_more_than_available_is_empty() {
        let v: Vec<i32> = (0..3).my_skip(10).collect();
        assert!(v.is_empty());
    }

    #[test]
    fn my_skip_zero_is_identity() {
        let v: Vec<i32> = (0..3).my_skip(0).collect();
        assert_eq!(v, vec![0, 1, 2]);
    }

    #[test]
    fn adapters_compose_on_infinite_iterator() {
        let v: Vec<u64> = (0u64..)
            .my_filter(|x| x % 2 == 0)
            .my_map(|x| x * x)
            .my_take(5)
            .collect();
        assert_eq!(v, vec![0, 4, 16, 36, 64]);
    }

    #[test]
    fn even_squares_matches_ocaml_example() {
        assert_eq!(even_squares(), vec![0, 4, 16, 36, 64]);
    }

    #[test]
    fn my_filter_then_my_skip_then_my_take() {
        let v: Vec<i32> = (0..20)
            .my_filter(|x| x % 3 == 0)
            .my_skip(2)
            .my_take(3)
            .collect();
        assert_eq!(v, vec![6, 9, 12]);
    }
}

(* 087: Iterator Adapters — custom map/filter/take *)

(* Custom Seq-based adapters *)
let rec my_map f s () =
  match s () with
  | Seq.Nil -> Seq.Nil
  | Seq.Cons (x, rest) -> Seq.Cons (f x, my_map f rest)

let rec my_filter p s () =
  match s () with
  | Seq.Nil -> Seq.Nil
  | Seq.Cons (x, rest) ->
    if p x then Seq.Cons (x, my_filter p rest)
    else my_filter p rest ()

let rec my_take n s () =
  if n <= 0 then Seq.Nil
  else match s () with
    | Seq.Nil -> Seq.Nil
    | Seq.Cons (x, rest) -> Seq.Cons (x, my_take (n - 1) rest)

let rec my_skip n s () =
  if n <= 0 then s ()
  else match s () with
    | Seq.Nil -> Seq.Nil
    | Seq.Cons (_, rest) -> my_skip (n - 1) rest ()

(* Compose adapters *)
let naturals =
  let rec aux n () = Seq.Cons (n, aux (n + 1)) in
  aux 0

let even_squares =
  naturals
  |> my_filter (fun x -> x mod 2 = 0)
  |> my_map (fun x -> x * x)
  |> my_take 5

(* Tests *)
let () =
  let to_list s = List.of_seq s in
  let range = Seq.init 5 (fun i -> i) in
  assert (to_list (my_map (fun x -> x * 2) range) = [0; 2; 4; 6; 8]);
  assert (to_list (my_filter (fun x -> x > 2) range) = [3; 4]);
  assert (to_list (my_take 3 range) = [0; 1; 2]);
  assert (to_list (my_skip 3 range) = [3; 4]);
  assert (to_list even_squares = [0; 4; 16; 36; 64]);
  Printf.printf "✓ All tests passed\n"

Key Differences

Aspect	Rust	OCaml
Adapter type	Generic struct `MyMap<I, F>`	Higher-order function `'a Seq.t -> 'a Seq.t`
Closure mutability	`FnMut` allowed	Mutable via `ref` if needed
Extension	`trait MyIterExt`	`\|>` pipe operator
Filter inner loop	`while let`	Tail-recursive `my_filter p rest ()`
Composability	Fluent method chain	`\|>` composition
Laziness mechanism	Pull-based `next`	Thunk evaluation

Building custom adapters from scratch reveals the mechanics behind std::iter. In production, use the standard adapters — they are optimised and tested. But understanding the internals is essential for designing custom data sources and specialised iteration patterns.

OCaml Approach

OCaml's Seq adapters are plain functions: my_map f s returns a thunk fun () -> match s () with Seq.Nil -> … | Seq.Cons(x, rest) -> Seq.Cons(f x, my_map f rest). my_filter recurses to skip non-matching elements. my_take decrements a counter. There is no extension trait; composition is achieved with the |> pipe operator. Both approaches achieve the same lazy pipeline; Rust's adapter structs make the type of each step explicit.

Full Source

//! Example 087: Iterator Adapters
//!
//! OCaml's `Seq.t` is a thunk that produces `Seq.Nil | Seq.Cons (x, rest)` on
//! demand. The reference example builds `my_map`, `my_filter`, `my_take`, and
//! `my_skip` by recursing over those thunks.
//!
//! Rust's [`Iterator`] trait already covers the same ground, so we mirror the
//! OCaml helpers as named adapter structs (`MyMap`, `MyFilter`, `MyTake`,
//! `MySkip`) and expose them through an extension trait [`MyIterExt`] for a
//! fluent `iter.my_filter(...).my_map(...).my_take(...)` style.

/// Adapter produced by [`MyIterExt::my_map`]; applies `f` to every yielded
/// item, mirroring OCaml's `my_map`.
pub struct MyMap<I, F> {
    iter: I,
    f: F,
}

impl<I, F, B> Iterator for MyMap<I, F>
where
    I: Iterator,
    F: FnMut(I::Item) -> B,
{
    type Item = B;

    fn next(&mut self) -> Option<B> {
        self.iter.next().map(&mut self.f)
    }
}

/// Adapter produced by [`MyIterExt::my_filter`]; yields only items where the
/// predicate returns `true`, mirroring OCaml's `my_filter`.
pub struct MyFilter<I, P> {
    iter: I,
    predicate: P,
}

impl<I, P> Iterator for MyFilter<I, P>
where
    I: Iterator,
    P: FnMut(&I::Item) -> bool,
{
    type Item = I::Item;

    fn next(&mut self) -> Option<I::Item> {
        self.iter.by_ref().find(|item| (self.predicate)(item))
    }
}

/// Adapter produced by [`MyIterExt::my_take`]; yields at most the first `n`
/// items, mirroring OCaml's `my_take`.
pub struct MyTake<I> {
    iter: I,
    remaining: usize,
}

impl<I: Iterator> Iterator for MyTake<I> {
    type Item = I::Item;

    fn next(&mut self) -> Option<I::Item> {
        if self.remaining == 0 {
            None
        } else {
            self.remaining -= 1;
            self.iter.next()
        }
    }
}

/// Adapter produced by [`MyIterExt::my_skip`]; discards the first `n` items
/// on the first `next` call, mirroring OCaml's `my_skip`.
pub struct MySkip<I> {
    iter: I,
    to_skip: usize,
}

impl<I: Iterator> Iterator for MySkip<I> {
    type Item = I::Item;

    fn next(&mut self) -> Option<I::Item> {
        while self.to_skip > 0 {
            self.iter.next()?;
            self.to_skip -= 1;
        }
        self.iter.next()
    }
}

/// Extension trait that adds the OCaml-named adapters to every [`Iterator`].
///
/// Bring it into scope with `use example_087_iterator_adapters::MyIterExt;` to
/// chain `my_map`, `my_filter`, `my_take`, and `my_skip` on any iterator.
pub trait MyIterExt: Iterator + Sized {
    /// Maps each item through `f`, like OCaml's `my_map`.
    fn my_map<F, B>(self, f: F) -> MyMap<Self, F>
    where
        F: FnMut(Self::Item) -> B,
    {
        MyMap { iter: self, f }
    }

    /// Keeps only items satisfying `predicate`, like OCaml's `my_filter`.
    fn my_filter<P>(self, predicate: P) -> MyFilter<Self, P>
    where
        P: FnMut(&Self::Item) -> bool,
    {
        MyFilter {
            iter: self,
            predicate,
        }
    }

    /// Yields at most the first `n` items, like OCaml's `my_take`.
    fn my_take(self, n: usize) -> MyTake<Self> {
        MyTake {
            iter: self,
            remaining: n,
        }
    }

    /// Discards the first `n` items, like OCaml's `my_skip`.
    fn my_skip(self, n: usize) -> MySkip<Self> {
        MySkip {
            iter: self,
            to_skip: n,
        }
    }
}

impl<I: Iterator> MyIterExt for I {}

/// Returns the OCaml example pipeline: the first five even squares of the
/// natural numbers, computed with the custom adapters.
pub fn even_squares() -> Vec<u64> {
    (0u64..)
        .my_filter(|x| x % 2 == 0)
        .my_map(|x| x * x)
        .my_take(5)
        .collect()
}

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

    #[test]
    fn my_map_doubles_each_item() {
        let v: Vec<i32> = (0..5).my_map(|x| x * 2).collect();
        assert_eq!(v, vec![0, 2, 4, 6, 8]);
    }

    #[test]
    fn my_filter_keeps_matching_items() {
        let v: Vec<i32> = (0..5).my_filter(|x| *x > 2).collect();
        assert_eq!(v, vec![3, 4]);
    }

    #[test]
    fn my_take_bounds_iteration() {
        let v: Vec<i32> = (0..5).my_take(3).collect();
        assert_eq!(v, vec![0, 1, 2]);
    }

    #[test]
    fn my_take_more_than_available_is_safe() {
        let v: Vec<i32> = (0..3).my_take(10).collect();
        assert_eq!(v, vec![0, 1, 2]);
    }

    #[test]
    fn my_skip_drops_prefix() {
        let v: Vec<i32> = (0..5).my_skip(3).collect();
        assert_eq!(v, vec![3, 4]);
    }

    #[test]
    fn my_skip_more_than_available_is_empty() {
        let v: Vec<i32> = (0..3).my_skip(10).collect();
        assert!(v.is_empty());
    }

    #[test]
    fn my_skip_zero_is_identity() {
        let v: Vec<i32> = (0..3).my_skip(0).collect();
        assert_eq!(v, vec![0, 1, 2]);
    }

    #[test]
    fn adapters_compose_on_infinite_iterator() {
        let v: Vec<u64> = (0u64..)
            .my_filter(|x| x % 2 == 0)
            .my_map(|x| x * x)
            .my_take(5)
            .collect();
        assert_eq!(v, vec![0, 4, 16, 36, 64]);
    }

    #[test]
    fn even_squares_matches_ocaml_example() {
        assert_eq!(even_squares(), vec![0, 4, 16, 36, 64]);
    }

    #[test]
    fn my_filter_then_my_skip_then_my_take() {
        let v: Vec<i32> = (0..20)
            .my_filter(|x| x % 3 == 0)
            .my_skip(2)
            .my_take(3)
            .collect();
        assert_eq!(v, vec![6, 9, 12]);
    }
}

(* 087: Iterator Adapters — custom map/filter/take *)

(* Custom Seq-based adapters *)
let rec my_map f s () =
  match s () with
  | Seq.Nil -> Seq.Nil
  | Seq.Cons (x, rest) -> Seq.Cons (f x, my_map f rest)

let rec my_filter p s () =
  match s () with
  | Seq.Nil -> Seq.Nil
  | Seq.Cons (x, rest) ->
    if p x then Seq.Cons (x, my_filter p rest)
    else my_filter p rest ()

let rec my_take n s () =
  if n <= 0 then Seq.Nil
  else match s () with
    | Seq.Nil -> Seq.Nil
    | Seq.Cons (x, rest) -> Seq.Cons (x, my_take (n - 1) rest)

let rec my_skip n s () =
  if n <= 0 then s ()
  else match s () with
    | Seq.Nil -> Seq.Nil
    | Seq.Cons (_, rest) -> my_skip (n - 1) rest ()

(* Compose adapters *)
let naturals =
  let rec aux n () = Seq.Cons (n, aux (n + 1)) in
  aux 0

let even_squares =
  naturals
  |> my_filter (fun x -> x mod 2 = 0)
  |> my_map (fun x -> x * x)
  |> my_take 5

(* Tests *)
let () =
  let to_list s = List.of_seq s in
  let range = Seq.init 5 (fun i -> i) in
  assert (to_list (my_map (fun x -> x * 2) range) = [0; 2; 4; 6; 8]);
  assert (to_list (my_filter (fun x -> x > 2) range) = [3; 4]);
  assert (to_list (my_take 3 range) = [0; 1; 2]);
  assert (to_list (my_skip 3 range) = [3; 4]);
  assert (to_list even_squares = [0; 4; 16; 36; 64]);
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn my_map_doubles_each_item() {
        let v: Vec<i32> = (0..5).my_map(|x| x * 2).collect();
        assert_eq!(v, vec![0, 2, 4, 6, 8]);
    }

    #[test]
    fn my_filter_keeps_matching_items() {
        let v: Vec<i32> = (0..5).my_filter(|x| *x > 2).collect();
        assert_eq!(v, vec![3, 4]);
    }

    #[test]
    fn my_take_bounds_iteration() {
        let v: Vec<i32> = (0..5).my_take(3).collect();
        assert_eq!(v, vec![0, 1, 2]);
    }

    #[test]
    fn my_take_more_than_available_is_safe() {
        let v: Vec<i32> = (0..3).my_take(10).collect();
        assert_eq!(v, vec![0, 1, 2]);
    }

    #[test]
    fn my_skip_drops_prefix() {
        let v: Vec<i32> = (0..5).my_skip(3).collect();
        assert_eq!(v, vec![3, 4]);
    }

    #[test]
    fn my_skip_more_than_available_is_empty() {
        let v: Vec<i32> = (0..3).my_skip(10).collect();
        assert!(v.is_empty());
    }

    #[test]
    fn my_skip_zero_is_identity() {
        let v: Vec<i32> = (0..3).my_skip(0).collect();
        assert_eq!(v, vec![0, 1, 2]);
    }

    #[test]
    fn adapters_compose_on_infinite_iterator() {
        let v: Vec<u64> = (0u64..)
            .my_filter(|x| x % 2 == 0)
            .my_map(|x| x * x)
            .my_take(5)
            .collect();
        assert_eq!(v, vec![0, 4, 16, 36, 64]);
    }

    #[test]
    fn even_squares_matches_ocaml_example() {
        assert_eq!(even_squares(), vec![0, 4, 16, 36, 64]);
    }

    #[test]
    fn my_filter_then_my_skip_then_my_take() {
        let v: Vec<i32> = (0..20)
            .my_filter(|x| x % 3 == 0)
            .my_skip(2)
            .my_take(3)
            .collect();
        assert_eq!(v, vec![6, 9, 12]);
    }
}

Deep Comparison

Core Insight

An adapter takes an iterator and returns a new iterator that transforms each element. They compose lazily — no intermediate collections.

OCaml Approach

• Seq.map, Seq.filter — return new Seq

• Can build custom: let my_map f s () = match s () with ...

Rust Approach

• Built-in: .map(), .filter(), .take(), .skip()

• Custom: struct wrapping I: Iterator + impl Iterator

Comparison Table

Adapter	OCaml	Rust
Map	`Seq.map f s`	`.map(f)`
Filter	`Seq.filter p s`	`.filter(p)`
Take	manual	`.take(n)`
Skip	manual	`.skip(n)`
Custom	Closure-based	Struct wrapping iterator

Exercises

Implement a MyZip<A: Iterator, B: Iterator> adapter that yields pairs (A::Item, B::Item) and stops when either iterator is exhausted.

Write a MyFlatMap<I, F, J> adapter where F: FnMut(I::Item) -> J and J: Iterator.

Add a my_enumerate method to MyIterExt that wraps items as (usize, Item).

Implement MyChain<A: Iterator<Item=T>, B: Iterator<Item=T>> that yields all of A then all of B.

In OCaml, write a seq_flat_map : ('a -> 'b Seq.t) -> 'a Seq.t -> 'b Seq.t and test it on a sequence of string words split into characters.

Open Source Repos

functional-rust

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

Rust