889 Intermediate

889-double-ended — DoubleEndedIterator

Functional Programming

Tutorial

The Problem

Most iterators traverse from front to back. Some algorithms benefit from bidirectional traversal: palindrome checking compares elements from both ends toward the center, taking the last N elements without knowing the total count, and simultaneous front-and-back consumption. Rust's DoubleEndedIterator extends Iterator with next_back(), enabling traversal from the end. This is implemented for slices, ranges, and many adapter types. The .rev() adapter wraps any DoubleEndedIterator to iterate in reverse. OCaml handles these cases with explicit List.rev or array indexing.

🎯 Learning Outcomes

• Use .rev() to iterate in reverse over any DoubleEndedIterator

• Use .next_back() to consume from the end of a bidirectional iterator

• Consume from both ends simultaneously for palindrome-style algorithms

• Implement take_last and ends using back-iteration without index arithmetic

• Compare with OCaml's List.rev and array-based back-access

Code Example

pub fn palindrome_check<T: PartialEq>(data: &[T]) -> bool {
    let mut iter = data.iter();
    loop {
        match (iter.next(), iter.next_back()) {
            (Some(a), Some(b)) => if a != b { return false; }
            _ => return true,
        }
    }
}

pub fn last_element<T>(data: &[T]) -> Option<&T> {
    data.iter().next_back()
}

(* Palindrome via array index arithmetic — O(n) allocation to convert list *)
let palindrome_check lst =
  let arr = Array.of_list lst in
  let n = Array.length arr in
  let rec aux i j =
    if i >= j then true
    else arr.(i) = arr.(j) && aux (i + 1) (j - 1)
  in
  aux 0 (n - 1)

(* Back access requires List.rev — copies the entire list *)
let last = function
  | [] -> None
  | lst -> Some (List.nth lst (List.length lst - 1))

Key Differences

Bidirectional without allocation: Rust next_back() on a slice iterator is O(1) and zero-allocation; OCaml List.rev is O(n) and allocates.

Simultaneous ends: Rust allows consuming from both ends of the same iterator object; OCaml requires two separate list traversals.

Adapter support: Many Rust adapters (.map(), .filter(), .chain()) preserve DoubleEndedIterator; OCaml adapters always produce new lists.

Slice specialization: SliceIter implements DoubleEndedIterator directly; .rev() on an array-backed iterator is zero-cost.

OCaml Approach

OCaml lists are singly-linked and have no DoubleEndedIterator equivalent. Back-access requires List.rev (O(n) allocation) or converting to arrays first. Palindrome check: list = List.rev list. Taking last n elements: List.filteri (fun i _ -> i >= len - n) list (O(n) scan). Arrays support O(1) back-access via negative-equivalent indexing (arr.(Array.length arr - 1 - i)). OCaml's lack of bidirectional iteration for lists is a notable contrast.

Full Source

#![allow(clippy::all)]
// Example 095: DoubleEndedIterator
// Iterate from both ends simultaneously using .rev(), .next_back(), and symmetric traversal.

// === Approach 1: Idiomatic Rust using DoubleEndedIterator ===

/// Returns the last `n` elements in original order, without reversing the full collection.
pub fn take_last<T: Clone>(data: &[T], n: usize) -> Vec<T> {
    // .rev().take(n) consumes from the back, then .rev() restores original order.
    data.iter()
        .rev()
        .take(n)
        .cloned()
        .collect::<Vec<_>>()
        .into_iter()
        .rev()
        .collect()
}

/// Returns the last element using back-iteration (no index arithmetic).
pub fn last_element<T>(data: &[T]) -> Option<&T> {
    data.iter().next_back()
}

/// Returns `(first, last)` by consuming from both ends of the same iterator.
pub fn ends(data: &[i32]) -> Option<(i32, i32)> {
    let mut iter = data.iter().copied();
    let first = iter.next()?;
    // If there is only one element, first == last.
    let last = iter.next_back().unwrap_or(first);
    Some((first, last))
}

// === Approach 2: Algorithms using simultaneous front/back traversal ===

/// Palindrome check by comparing elements from both ends inward.
/// Zero allocation: `iter.next()` and `iter.next_back()` narrow the same slice view.
pub fn palindrome_check<T: PartialEq>(data: &[T]) -> bool {
    let mut iter = data.iter();
    loop {
        match (iter.next(), iter.next_back()) {
            (Some(a), Some(b)) => {
                if a != b {
                    return false;
                }
            }
            // Ends met in the middle (odd) or crossed (even) — done.
            _ => return true,
        }
    }
}

/// Interleave elements from the front and back, converging toward the middle.
/// e.g. [1,2,3,4,5] -> [1,5,2,4,3]
pub fn interleave_ends<T: Clone>(data: &[T]) -> Vec<T> {
    let mut result = Vec::with_capacity(data.len());
    let mut iter = data.iter();
    loop {
        match iter.next() {
            None => break,
            Some(front) => {
                result.push(front.clone());
                match iter.next_back() {
                    // Skip when front and back are the same element (odd-length middle).
                    Some(back) if !std::ptr::eq(front, back) => result.push(back.clone()),
                    _ => {}
                }
            }
        }
    }
    result
}

/// Functional/recursive palindrome check — mirrors the OCaml array-index approach.
pub fn palindrome_check_recursive<T: PartialEq>(data: &[T]) -> bool {
    match data {
        [] | [_] => true,
        [first, rest @ .., last] => first == last && palindrome_check_recursive(rest),
    }
}

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

    // --- take_last ---

    #[test]
    fn test_take_last_empty() {
        let empty: &[i32] = &[];
        assert_eq!(take_last(empty, 3), Vec::<i32>::new());
    }

    #[test]
    fn test_take_last_fewer_than_n() {
        assert_eq!(take_last(&[1, 2], 5), vec![1, 2]);
    }

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

    #[test]
    fn test_take_last_zero() {
        assert_eq!(take_last(&[1, 2, 3], 0), Vec::<i32>::new());
    }

    // --- last_element ---

    #[test]
    fn test_last_element_empty() {
        assert_eq!(last_element::<i32>(&[]), None);
    }

    #[test]
    fn test_last_element_single() {
        assert_eq!(last_element(&[42]), Some(&42));
    }

    #[test]
    fn test_last_element_multiple() {
        assert_eq!(last_element(&[1, 2, 3, 99]), Some(&99));
    }

    // --- ends ---

    #[test]
    fn test_ends_empty() {
        assert_eq!(ends(&[]), None);
    }

    #[test]
    fn test_ends_single() {
        assert_eq!(ends(&[7]), Some((7, 7)));
    }

    #[test]
    fn test_ends_multiple() {
        assert_eq!(ends(&[1, 2, 3, 4, 5]), Some((1, 5)));
    }

    // --- palindrome_check ---

    #[test]
    fn test_palindrome_empty() {
        assert!(palindrome_check::<i32>(&[]));
    }

    #[test]
    fn test_palindrome_single() {
        assert!(palindrome_check(&[1]));
    }

    #[test]
    fn test_palindrome_even_true() {
        assert!(palindrome_check(&[1, 2, 2, 1]));
    }

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

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

    #[test]
    fn test_palindrome_strings() {
        assert!(palindrome_check(&["a", "b", "b", "a"]));
        assert!(!palindrome_check(&["a", "b", "c"]));
    }

    // --- palindrome_check_recursive ---

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

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

    // --- interleave_ends ---

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

    #[test]
    fn test_interleave_single() {
        assert_eq!(interleave_ends(&[42]), vec![42]);
    }

    #[test]
    fn test_interleave_even() {
        assert_eq!(interleave_ends(&[1, 2, 3, 4]), vec![1, 4, 2, 3]);
    }

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

(* Example 095: Double-Ended Iterator *)
(* Iterate from both ends *)

(* Approach 1: List reversal for back-iteration *)
let take_last n lst =
  let len = List.length lst in
  if n >= len then lst
  else List.filteri (fun i _ -> i >= len - n) lst

let last = function
  | [] -> None
  | lst -> Some (List.nth lst (List.length lst - 1))

(* Approach 2: Array-based bidirectional access *)
let palindrome_check lst =
  let arr = Array.of_list lst in
  let n = Array.length arr in
  let rec aux i j =
    if i >= j then true
    else arr.(i) = arr.(j) && aux (i + 1) (j - 1)
  in
  aux 0 (n - 1)

let interleave_ends lst =
  let arr = Array.of_list lst in
  let n = Array.length arr in
  let result = ref [] in
  let lo = ref 0 and hi = ref (n - 1) in
  while !lo <= !hi do
    result := arr.(!lo) :: !result;
    if !lo <> !hi then result := arr.(!hi) :: !result;
    incr lo;
    decr hi
  done;
  List.rev !result

(* Approach 3: Deque-like operations *)
let trim_while pred lst =
  let trimmed_front = List.to_seq lst |> Seq.drop_while pred |> List.of_seq in
  List.rev trimmed_front |> List.to_seq |> Seq.drop_while pred |> List.of_seq |> List.rev

(* Tests *)
let () =
  assert (take_last 3 [1;2;3;4;5] = [3;4;5]);
  assert (take_last 10 [1;2;3] = [1;2;3]);
  assert (last [1;2;3] = Some 3);
  assert (last [] = None);

  assert (palindrome_check [1;2;3;2;1]);
  assert (not (palindrome_check [1;2;3;4;5]));
  assert (palindrome_check []);
  assert (palindrome_check [1]);

  assert (interleave_ends [1;2;3;4;5] = [1;5;2;4;3]);

  assert (trim_while (fun x -> x = 0) [0;0;1;2;3;0;0] = [1;2;3]);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    // --- take_last ---

    #[test]
    fn test_take_last_empty() {
        let empty: &[i32] = &[];
        assert_eq!(take_last(empty, 3), Vec::<i32>::new());
    }

    #[test]
    fn test_take_last_fewer_than_n() {
        assert_eq!(take_last(&[1, 2], 5), vec![1, 2]);
    }

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

    #[test]
    fn test_take_last_zero() {
        assert_eq!(take_last(&[1, 2, 3], 0), Vec::<i32>::new());
    }

    // --- last_element ---

    #[test]
    fn test_last_element_empty() {
        assert_eq!(last_element::<i32>(&[]), None);
    }

    #[test]
    fn test_last_element_single() {
        assert_eq!(last_element(&[42]), Some(&42));
    }

    #[test]
    fn test_last_element_multiple() {
        assert_eq!(last_element(&[1, 2, 3, 99]), Some(&99));
    }

    // --- ends ---

    #[test]
    fn test_ends_empty() {
        assert_eq!(ends(&[]), None);
    }

    #[test]
    fn test_ends_single() {
        assert_eq!(ends(&[7]), Some((7, 7)));
    }

    #[test]
    fn test_ends_multiple() {
        assert_eq!(ends(&[1, 2, 3, 4, 5]), Some((1, 5)));
    }

    // --- palindrome_check ---

    #[test]
    fn test_palindrome_empty() {
        assert!(palindrome_check::<i32>(&[]));
    }

    #[test]
    fn test_palindrome_single() {
        assert!(palindrome_check(&[1]));
    }

    #[test]
    fn test_palindrome_even_true() {
        assert!(palindrome_check(&[1, 2, 2, 1]));
    }

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

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

    #[test]
    fn test_palindrome_strings() {
        assert!(palindrome_check(&["a", "b", "b", "a"]));
        assert!(!palindrome_check(&["a", "b", "c"]));
    }

    // --- palindrome_check_recursive ---

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

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

    // --- interleave_ends ---

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

    #[test]
    fn test_interleave_single() {
        assert_eq!(interleave_ends(&[42]), vec![42]);
    }

    #[test]
    fn test_interleave_even() {
        assert_eq!(interleave_ends(&[1, 2, 3, 4]), vec![1, 4, 2, 3]);
    }

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

Deep Comparison

OCaml vs Rust: DoubleEndedIterator

Side-by-Side Code

OCaml

(* Palindrome via array index arithmetic — O(n) allocation to convert list *)
let palindrome_check lst =
  let arr = Array.of_list lst in
  let n = Array.length arr in
  let rec aux i j =
    if i >= j then true
    else arr.(i) = arr.(j) && aux (i + 1) (j - 1)
  in
  aux 0 (n - 1)

(* Back access requires List.rev — copies the entire list *)
let last = function
  | [] -> None
  | lst -> Some (List.nth lst (List.length lst - 1))

Rust (idiomatic — DoubleEndedIterator)

pub fn palindrome_check<T: PartialEq>(data: &[T]) -> bool {
    let mut iter = data.iter();
    loop {
        match (iter.next(), iter.next_back()) {
            (Some(a), Some(b)) => if a != b { return false; }
            _ => return true,
        }
    }
}

pub fn last_element<T>(data: &[T]) -> Option<&T> {
    data.iter().next_back()
}

Rust (functional/recursive — mirrors OCaml index approach)

pub fn palindrome_check_recursive<T: PartialEq>(data: &[T]) -> bool {
    match data {
        [] | [_] => true,
        [first, rest @ .., last] => first == last && palindrome_check_recursive(rest),
    }
}

Type Signatures

Concept	OCaml	Rust
Palindrome	`val palindrome_check : 'a list -> bool`	`fn palindrome_check<T: PartialEq>(data: &[T]) -> bool`
Last element	`val last : 'a list -> 'a option`	`fn last_element<T>(data: &[T]) -> Option<&T>`
Back iterator	N/A (no trait)	`iter.next_back()` via `DoubleEndedIterator`
Reversed iteration	`List.rev lst \\|> List.iter`	`data.iter().rev()` — zero cost, no allocation

Key Insights

Back access cost: OCaml lists are singly-linked — List.nth lst (len-1) is O(n) and List.rev allocates a copy. Rust slices implement DoubleEndedIterator natively, so .next_back() is O(1) and zero-allocation.

**.rev() is free in Rust:** Iterator::rev() is a zero-cost adaptor that merely swaps which end .next() reads from. It does not create a reversed copy of the data — unlike OCaml's List.rev.

Simultaneous traversal: Rust's DoubleEndedIterator allows .next() and .next_back() on the same iterator, so front and back converge toward the middle. OCaml has no equivalent trait; you need explicit index variables or a converted array.

Slice pattern matching: The recursive Rust version uses [first, rest @ .., last] — a slice pattern that deconstructs both ends in one match arm, directly mirroring OCaml's structural recursion without allocating an array.

Ownership safety: Rust's iterator protocol ensures the front and back pointers never cross — the iterator becomes exhausted safely. In OCaml, the index-based aux i j loop relies on the programmer maintaining i <= j; Rust enforces this invariant in the type system via the iterator's internal state.

When to Use Each Style

Use idiomatic Rust (DoubleEndedIterator) when: you want zero-allocation bidirectional traversal on slices, strings, or any collection that implements the trait — palindrome checks, symmetric reductions, trimming from both ends.

Use recursive Rust (slice patterns) when: the algorithm is naturally expressed as structural recursion and you want a direct correspondence with functional OCaml code for clarity or teaching purposes.

Exercises

Implement longest_palindromic_prefix(s: &str) -> &str that uses a double-ended char iterator to find the palindrome prefix.

Write interleave_ends<T: Clone>(data: &[T]) -> Vec<T> that alternates front and back elements: [a0, an, a1, an-1, ...].

Implement symmetric_filter<T: PartialEq + Clone>(data: &[T], pred: impl Fn(&T) -> bool) -> Vec<T> that uses a double-ended iterator to filter from both ends simultaneously.

Open Source Repos

functional-rust

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

Rust