095 Intermediate

095 — Double-Ended Iterator

Functional Programming

Tutorial

The Problem

Use Rust's DoubleEndedIterator trait to iterate from both ends simultaneously. Implement palindrome detection by comparing forward and reversed iterators, and demonstrate next() / next_back() on the same iterator instance. Compare with OCaml's manual array-based bidirectional iteration.

🎯 Learning Outcomes

• Use v.iter().rev() to create a reversed iterator from a DoubleEndedIterator

• Compare two iterators with .eq(other_iter) for element-wise equality

• Use .next_back() to advance from the back without consuming the front

• Understand that next() and next_back() share position state — they meet in the middle

• Map Rust's DoubleEndedIterator to OCaml's mutable front/back array cursors

• Recognise when double-ended iteration avoids a reversal allocation

Code Example

#![allow(clippy::all)]
// 095: Double-Ended Iterator

fn is_palindrome(v: &[i32]) -> bool {
    v.iter().eq(v.iter().rev())
}

fn take_from_both(v: &[i32]) -> (Vec<i32>, Vec<i32>) {
    let mut iter = v.iter();
    let front: Vec<i32> = (0..2).filter_map(|_| iter.next().copied()).collect();
    let back: Vec<i32> = (0..2).filter_map(|_| iter.next_back().copied()).collect();
    (front, back)
}

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

    #[test]
    fn test_palindrome() {
        assert!(is_palindrome(&[1, 2, 3, 2, 1]));
        assert!(!is_palindrome(&[1, 2, 3]));
    }

    #[test]
    fn test_take_both() {
        let (f, b) = take_from_both(&[1, 2, 3, 4, 5]);
        assert_eq!(f, vec![1, 2]);
        assert_eq!(b, vec![5, 4]);
    }

    #[test]
    fn test_next_back() {
        let v = vec![1, 2, 3];
        let mut iter = v.iter();
        assert_eq!(iter.next_back(), Some(&3));
        assert_eq!(iter.next(), Some(&1));
        assert_eq!(iter.next(), Some(&2));
        assert_eq!(iter.next(), None);
    }
}

(* 095: Double-Ended Iteration *)
(* OCaml lists are singly-linked — no efficient reverse iteration *)
(* We simulate with arrays *)

let iter_both arr =
  let n = Array.length arr in
  let front = ref 0 in
  let back = ref (n - 1) in
  let next_front () =
    if !front > !back then None
    else (let v = arr.(!front) in incr front; Some v)
  in
  let next_back () =
    if !back < !front then None
    else (let v = arr.(!back) in decr back; Some v)
  in
  (next_front, next_back)

let is_palindrome_arr arr =
  let n = Array.length arr in
  let rec check i = i >= n / 2 || (arr.(i) = arr.(n - 1 - i) && check (i + 1)) in
  check 0

(* Tests *)
let () =
  let arr = [|1; 2; 3; 4; 5|] in
  let (nf, nb) = iter_both arr in
  assert (nf () = Some 1);
  assert (nb () = Some 5);
  assert (nf () = Some 2);
  assert (nb () = Some 4);
  assert (is_palindrome_arr [|1; 2; 3; 2; 1|]);
  assert (not (is_palindrome_arr [|1; 2; 3|]));
  Printf.printf "✓ All tests passed\n"

Key Differences

Aspect	Rust	OCaml
Reverse iteration	`.rev()` on any `DoubleEndedIterator`	Arrays: `arr.(n-1-i)`, lists: reverse
Bidirectional	`next()` + `next_back()` on same iter	Manual front/back indices
Palindrome	`.iter().eq(.iter().rev())`	`arr.(i) = arr.(n-1-i)`
Allocation	Zero (`.rev()` is O(1))	Zero for arrays
Protocol	Trait method `next_back`	Manual cursor
Lists	Not `DoubleEndedIterator`	`List.rev` makes a copy

DoubleEndedIterator is implemented by slices, ranges, Vec, VecDeque, Rev, and many standard adapters. It enables efficient palindrome checks, bidirectional parsing, and simultaneous front/back consumption without allocating a reversed copy.

OCaml Approach

OCaml lists are singly linked — no efficient reverse iteration. The iter_both function simulates double-ended iteration on arrays using mutable front and back index references. is_palindrome_arr checks symmetry with array indexing arr.(i) = arr.(n - 1 - i). Rust's built-in protocol is cleaner; OCaml requires manual bookkeeping.

Full Source

#![allow(clippy::all)]
// 095: Double-Ended Iterator

fn is_palindrome(v: &[i32]) -> bool {
    v.iter().eq(v.iter().rev())
}

fn take_from_both(v: &[i32]) -> (Vec<i32>, Vec<i32>) {
    let mut iter = v.iter();
    let front: Vec<i32> = (0..2).filter_map(|_| iter.next().copied()).collect();
    let back: Vec<i32> = (0..2).filter_map(|_| iter.next_back().copied()).collect();
    (front, back)
}

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

    #[test]
    fn test_palindrome() {
        assert!(is_palindrome(&[1, 2, 3, 2, 1]));
        assert!(!is_palindrome(&[1, 2, 3]));
    }

    #[test]
    fn test_take_both() {
        let (f, b) = take_from_both(&[1, 2, 3, 4, 5]);
        assert_eq!(f, vec![1, 2]);
        assert_eq!(b, vec![5, 4]);
    }

    #[test]
    fn test_next_back() {
        let v = vec![1, 2, 3];
        let mut iter = v.iter();
        assert_eq!(iter.next_back(), Some(&3));
        assert_eq!(iter.next(), Some(&1));
        assert_eq!(iter.next(), Some(&2));
        assert_eq!(iter.next(), None);
    }
}

(* 095: Double-Ended Iteration *)
(* OCaml lists are singly-linked — no efficient reverse iteration *)
(* We simulate with arrays *)

let iter_both arr =
  let n = Array.length arr in
  let front = ref 0 in
  let back = ref (n - 1) in
  let next_front () =
    if !front > !back then None
    else (let v = arr.(!front) in incr front; Some v)
  in
  let next_back () =
    if !back < !front then None
    else (let v = arr.(!back) in decr back; Some v)
  in
  (next_front, next_back)

let is_palindrome_arr arr =
  let n = Array.length arr in
  let rec check i = i >= n / 2 || (arr.(i) = arr.(n - 1 - i) && check (i + 1)) in
  check 0

(* Tests *)
let () =
  let arr = [|1; 2; 3; 4; 5|] in
  let (nf, nb) = iter_both arr in
  assert (nf () = Some 1);
  assert (nb () = Some 5);
  assert (nf () = Some 2);
  assert (nb () = Some 4);
  assert (is_palindrome_arr [|1; 2; 3; 2; 1|]);
  assert (not (is_palindrome_arr [|1; 2; 3|]));
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_palindrome() {
        assert!(is_palindrome(&[1, 2, 3, 2, 1]));
        assert!(!is_palindrome(&[1, 2, 3]));
    }

    #[test]
    fn test_take_both() {
        let (f, b) = take_from_both(&[1, 2, 3, 4, 5]);
        assert_eq!(f, vec![1, 2]);
        assert_eq!(b, vec![5, 4]);
    }

    #[test]
    fn test_next_back() {
        let v = vec![1, 2, 3];
        let mut iter = v.iter();
        assert_eq!(iter.next_back(), Some(&3));
        assert_eq!(iter.next(), Some(&1));
        assert_eq!(iter.next(), Some(&2));
        assert_eq!(iter.next(), None);
    }
}

Deep Comparison

Core Insight

DoubleEndedIterator iterates from both ends — enables rev() without collecting first

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

Implement is_palindrome_str(s: &str) -> bool using s.chars().eq(s.chars().rev()).

Write zip_ends<T: Clone>(v: &[T]) -> Vec<(T, T)> that pairs the first element with the last, second with second-to-last, etc.

Implement a bidirectional deque processor that alternately takes from front and back.

Use DoubleEndedIterator to implement a rotate_left that moves the first n elements to the back.

In OCaml, implement bidirectional iteration over a doubly linked list, defining both next and prev operations.

Open Source Repos

functional-rust

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

Rust