282 Intermediate

282: DoubleEndedIterator and rev()

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "282: DoubleEndedIterator and rev()" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Some traversal algorithms need to process elements from both ends of a sequence — reversing a sequence, checking palindromes, implementing a two-pointer algorithm, or finding the last matching element efficiently. Key difference from OCaml: 1. **Zero

Tutorial

The Problem

Some traversal algorithms need to process elements from both ends of a sequence — reversing a sequence, checking palindromes, implementing a two-pointer algorithm, or finding the last matching element efficiently. DoubleEndedIterator extends the Iterator trait with a next_back() method, enabling traversal from the back end without reversing the sequence in memory. The rev() adapter wraps a DoubleEndedIterator to produce a forward iterator that yields elements from back to front.

🎯 Learning Outcomes

• Understand DoubleEndedIterator as adding next_back() to enable consumption from both ends

• Use rev() to iterate a bidirectional collection in reverse without allocating a reversed copy

• Implement DoubleEndedIterator on a custom struct with independent front and back pointers

• Recognize which standard iterators implement DoubleEndedIterator: slice iterators, Range, Vec, but not Chain by default

Code Example

let reversed: Vec<i32> = (1..=5).rev().collect();
// No allocation until collect() - rev() just swaps direction

let nums = [1; 2; 3; 4; 5] in
let reversed = List.rev nums  (* allocates new list *)

Key Differences

Zero-copy reverse: Rust's rev() on a DoubleEndedIterator is zero-allocation; OCaml's sequence reversal requires materializing into an array.

Two-pointer idiom: Rust's DoubleEndedIterator enables the classic two-pointer algorithm without materializing the full sequence.

Adapter compatibility: rev() composes with map, filter, and other adapters; OCaml requires restructuring the algorithm.

Standard collections: Vec, slices, BTreeMap, LinkedList implement DoubleEndedIterator in Rust; hash maps and forward-only structures do not.

OCaml Approach

OCaml's Seq module is inherently forward-only. Bidirectional iteration typically requires converting to an array (Array.of_seq) and using index-based access from both ends, or using a doubly-linked data structure:

let reverse_seq seq =
  let arr = Array.of_seq seq in
  Array.to_seq (Array.init (Array.length arr)
    (fun i -> arr.(Array.length arr - 1 - i)))
(* Allocates: no zero-copy reverse *)

Full Source

#![allow(clippy::all)]
//! # DoubleEndedIterator and rev()
//!
//! `DoubleEndedIterator` enables traversal from both ends; `rev()` swaps the direction.

/// A counter that can be consumed from either end
pub struct Counter {
    front: i32,
    back: i32,
}

impl Counter {
    pub fn new(n: i32) -> Self {
        Counter { front: 1, back: n }
    }

    pub fn range(start: i32, end: i32) -> Self {
        Counter {
            front: start,
            back: end,
        }
    }
}

impl Iterator for Counter {
    type Item = i32;

    fn next(&mut self) -> Option<i32> {
        if self.front > self.back {
            return None;
        }
        let v = self.front;
        self.front += 1;
        Some(v)
    }
}

impl DoubleEndedIterator for Counter {
    fn next_back(&mut self) -> Option<i32> {
        if self.front > self.back {
            return None;
        }
        let v = self.back;
        self.back -= 1;
        Some(v)
    }
}

/// Reverse a string using DoubleEndedIterator
pub fn reverse_string(s: &str) -> String {
    s.chars().rev().collect()
}

/// Check if a sequence is a palindrome using DoubleEndedIterator
pub fn is_palindrome<I>(iter: I) -> bool
where
    I: DoubleEndedIterator + Clone,
    I::Item: PartialEq,
{
    let mut forward = iter.clone();
    let mut backward = iter.rev();

    loop {
        match (forward.next(), backward.next()) {
            (Some(a), Some(b)) if a == b => continue,
            (None, None) => return true,
            _ => return false,
        }
    }
}

/// Consume from both ends simultaneously
pub fn from_both_ends<I>(mut iter: I) -> Vec<(Option<I::Item>, Option<I::Item>)>
where
    I: DoubleEndedIterator,
{
    let mut result = Vec::new();
    loop {
        let front = iter.next();
        let back = iter.next_back();
        if front.is_none() && back.is_none() {
            break;
        }
        result.push((front, back));
    }
    result
}

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

    #[test]
    fn test_rev_range() {
        let result: Vec<i32> = (1..=5).rev().collect();
        assert_eq!(result, vec![5, 4, 3, 2, 1]);
    }

    #[test]
    fn test_custom_dei_rev() {
        let result: Vec<i32> = Counter::new(5).rev().collect();
        assert_eq!(result, vec![5, 4, 3, 2, 1]);
    }

    #[test]
    fn test_next_back() {
        let mut c = Counter::new(5);
        assert_eq!(c.next_back(), Some(5));
        assert_eq!(c.next_back(), Some(4));
        assert_eq!(c.next(), Some(1));
    }

    #[test]
    fn test_rev_collect_string() {
        let result = reverse_string("hello");
        assert_eq!(result, "olleh");
    }

    #[test]
    fn test_is_palindrome() {
        assert!(is_palindrome("racecar".chars()));
        assert!(is_palindrome([1, 2, 3, 2, 1].iter()));
        assert!(!is_palindrome("hello".chars()));
    }

    #[test]
    fn test_from_both_ends() {
        let result = from_both_ends(Counter::new(5));
        assert_eq!(
            result,
            vec![(Some(1), Some(5)), (Some(2), Some(4)), (Some(3), None),]
        );
    }

    #[test]
    fn test_last_3_evens_reversed() {
        let last_3_even: Vec<i32> = (1..=20).filter(|x| x % 2 == 0).rev().take(3).collect();
        assert_eq!(last_3_even, vec![20, 18, 16]);
    }
}

(* 282. DoubleEndedIterator and rev() - OCaml *)
(* OCaml: List.rev creates new reversed list *)

let () =
  let nums = [1; 2; 3; 4; 5] in
  let reversed = List.rev nums in
  Printf.printf "Reversed: %s\n"
    (String.concat ", " (List.map string_of_int reversed));

  (* Consume from both ends simultaneously *)
  let arr = Array.of_list nums in
  let n = Array.length arr in
  let front = ref 0 and back = ref (n - 1) in
  Printf.printf "From both ends: " ;
  while !front <= !back do
    if !front = !back then Printf.printf "%d " arr.(!front)
    else Printf.printf "%d %d " arr.(!front) arr.(!back);
    incr front; decr back
  done;
  print_newline ();

  (* Reverse iterate *)
  for i = n - 1 downto 0 do
    Printf.printf "%d " arr.(i)
  done;
  print_newline ()

✓ Tests Rust test suite

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

    #[test]
    fn test_rev_range() {
        let result: Vec<i32> = (1..=5).rev().collect();
        assert_eq!(result, vec![5, 4, 3, 2, 1]);
    }

    #[test]
    fn test_custom_dei_rev() {
        let result: Vec<i32> = Counter::new(5).rev().collect();
        assert_eq!(result, vec![5, 4, 3, 2, 1]);
    }

    #[test]
    fn test_next_back() {
        let mut c = Counter::new(5);
        assert_eq!(c.next_back(), Some(5));
        assert_eq!(c.next_back(), Some(4));
        assert_eq!(c.next(), Some(1));
    }

    #[test]
    fn test_rev_collect_string() {
        let result = reverse_string("hello");
        assert_eq!(result, "olleh");
    }

    #[test]
    fn test_is_palindrome() {
        assert!(is_palindrome("racecar".chars()));
        assert!(is_palindrome([1, 2, 3, 2, 1].iter()));
        assert!(!is_palindrome("hello".chars()));
    }

    #[test]
    fn test_from_both_ends() {
        let result = from_both_ends(Counter::new(5));
        assert_eq!(
            result,
            vec![(Some(1), Some(5)), (Some(2), Some(4)), (Some(3), None),]
        );
    }

    #[test]
    fn test_last_3_evens_reversed() {
        let last_3_even: Vec<i32> = (1..=20).filter(|x| x % 2 == 0).rev().take(3).collect();
        assert_eq!(last_3_even, vec![20, 18, 16]);
    }
}

Deep Comparison

OCaml vs Rust: DoubleEndedIterator

Pattern 1: Reversing a Sequence

OCaml

let nums = [1; 2; 3; 4; 5] in
let reversed = List.rev nums  (* allocates new list *)

Rust

let reversed: Vec<i32> = (1..=5).rev().collect();
// No allocation until collect() - rev() just swaps direction

Pattern 2: Consuming from Both Ends

OCaml

let arr = Array.of_list nums in
let n = Array.length arr in
let front = ref 0 and back = ref (n - 1) in
while !front <= !back do
  Printf.printf "%d %d " arr.(!front) arr.(!back);
  incr front; decr back
done

Rust

let mut counter = Counter::new(5);
loop {
    match (counter.next(), counter.next_back()) {
        (Some(f), Some(b)) => println!("{} {}", f, b),
        (Some(x), None) | (None, Some(x)) => println!("{}", x),
        (None, None) => break,
    }
}

Pattern 3: Implementing DoubleEndedIterator

Rust

struct Counter { front: i32, back: i32 }

impl Iterator for Counter {
    type Item = i32;
    fn next(&mut self) -> Option<i32> {
        if self.front > self.back { return None; }
        let v = self.front;
        self.front += 1;
        Some(v)
    }
}

impl DoubleEndedIterator for Counter {
    fn next_back(&mut self) -> Option<i32> {
        if self.front > self.back { return None; }
        let v = self.back;
        self.back -= 1;
        Some(v)
    }
}

Key Differences

Aspect	OCaml	Rust
Reverse	`List.rev` allocates new list	`.rev()` is zero-allocation
Both ends	Manual index tracking	`next()` + `next_back()`
Trait	None built-in	`DoubleEndedIterator`
Custom impl	N/A	Implement `next_back()`
Mechanism	Creates new collection	Swaps roles of front/back

Exercises

Use rev() to compare a Vec<char> with its reverse, implementing a palindrome checker without allocating a reversed copy.

Implement DoubleEndedIterator on a custom GridRow type that iterates over a 2D matrix row from either end.

Use the two-pointer pattern: simultaneously consume elements from both ends of a DoubleEndedIterator to check if all pairs sum to the same value.

Open Source Repos

functional-rust

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

Rust