🦀 Functional Rust

095: DoubleEndedIterator

Difficulty: 3 Level: Intermediate Iterate from both ends simultaneously — `.rev()`, `.next_back()`, palindrome checks, and symmetric traversal.

The Problem This Solves

Some algorithms naturally work inward from both ends: palindrome verification, symmetric reductions, trimming from both sides, interleaving front and back. Without bidirectional traversal, you'd reverse the entire collection first — allocating a copy just to read it backwards. `DoubleEndedIterator` makes both ends available simultaneously. You can pull from the front with `.next()` and from the back with `.next_back()`, narrowing toward the middle without any extra allocation. This is what makes `.rev()` zero-cost — it just swaps which end `.next()` reads from.

The Intuition

Think of a double-ended queue (deque): `.next()` pops the front, `.next_back()` pops the back. Both shrink the same underlying view. OCaml lists are singly-linked — back access requires `List.rev` which copies. Arrays work with index arithmetic. Rust slices implement `DoubleEndedIterator` natively, so both directions work on the same data without copies. Python's `reversed()` creates a separate reversed iterator — similar but doesn't allow simultaneous front/back consumption.

How It Works in Rust

// Palindrome: compare elements from both ends moving inward
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; },
         // Met in the middle (odd length) or exhausted (even length)
         _ => return true,
     }
 }
}

// Get first and last without two separate passes
fn ends(data: &[i32]) -> Option<(i32, i32)> {
 let mut iter = data.iter();
 let first = iter.next()?;
 let last = iter.next_back().unwrap_or(first); // handles single-element
 Some((*first, *last))
}

// .rev() is zero-cost: just swaps next() ↔ next_back()
fn last_n<T: Clone>(data: &[T], n: usize) -> Vec<T> {
 data.iter()
     .rev()
     .take(n)
     .cloned()
     .collect::<Vec<_>>()
     .into_iter()
     .rev()  // restore original order
     .collect()
}

// rfind: search from the back (built-in on DoubleEndedIterator)
fn last_even(data: &[i32]) -> Option<&i32> {
 data.iter().rfind(|&&x| x % 2 == 0)
}
Note: adapters like `.filter()` remove `DoubleEndedIterator` because they can't know the back length. `.map()` and `.take()` preserve it.

What This Unlocks

Key Differences

ConceptOCamlRust
Back iteration`List.rev` then forward`.next_back()` built-in
Reverse`List.rev` (O(n) copy)`.rev()` zero-cost adapter
rfindManual`.rfind()` built-in
Simultaneous endsNot possible on lists`iter.next()` + `iter.next_back()`
filter preserves DEIN/ANo (unknown back length)
// Example 095: DoubleEndedIterator
// Iterate from both ends

// === Approach 1: Basic rev and back iteration ===
fn take_last<T: Clone>(data: &[T], n: usize) -> Vec<T> {
    data.iter().rev().take(n).cloned().collect::<Vec<_>>().into_iter().rev().collect()
}

fn last_element<T: Clone>(data: &[T]) -> Option<T> {
    data.iter().cloned().last()
}

// Using next_back directly
fn ends(data: &[i32]) -> Option<(i32, i32)> {
    let mut iter = data.iter();
    let first = iter.next()?;
    let last = iter.next_back().unwrap_or(first);
    Some((*first, *last))
}

// === Approach 2: Algorithms using double-ended ===
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,
        }
    }
}

fn interleave_ends<T: Clone>(data: &[T]) -> Vec<T> {
    let mut result = Vec::with_capacity(data.len());
    let mut front = data.iter();
    let mut back = data.iter().rev();
    let mut take_front = true;

    for _ in 0..data.len() {
        if take_front {
            result.push(front.next().unwrap().clone());
        } else {
            result.push(back.next().unwrap().clone());
        }
        take_front = !take_front;
    }
    result
}

// === Approach 3: rfind, rposition, rfold ===
fn rfind_demo(data: &[i32], pred: impl Fn(&i32) -> bool) -> Option<&i32> {
    data.iter().rfind(|x| pred(x))
}

fn rposition_demo(data: &[i32], pred: impl Fn(&i32) -> bool) -> Option<usize> {
    data.iter().rposition(|x| pred(x))
}

fn trim_zeros(data: &[i32]) -> Vec<i32> {
    let start = data.iter().position(|&x| x != 0).unwrap_or(data.len());
    let end = data.iter().rposition(|&x| x != 0).map(|p| p + 1).unwrap_or(0);
    if start >= end { vec![] } else { data[start..end].to_vec() }
}

fn reverse_words(sentence: &str) -> String {
    sentence.split_whitespace().rev().collect::<Vec<_>>().join(" ")
}

fn main() {
    println!("Last 3: {:?}", take_last(&[1,2,3,4,5], 3));
    println!("Ends: {:?}", ends(&[1,2,3,4,5]));
    println!("Palindrome [1,2,1]: {}", palindrome_check(&[1,2,1]));
    println!("Interleave: {:?}", interleave_ends(&[1,2,3,4,5]));
    println!("rfind >3: {:?}", rfind_demo(&[1,2,3,4,5], |x| *x > 3));
    println!("rposition >3: {:?}", rposition_demo(&[1,2,3,4,5], |x| *x > 3));
    println!("Trim zeros: {:?}", trim_zeros(&[0,0,1,2,3,0,0]));
    println!("Reverse words: {}", reverse_words("hello world foo"));
}

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

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

    #[test]
    fn test_ends() {
        assert_eq!(ends(&[1,2,3,4,5]), Some((1, 5)));
        assert_eq!(ends(&[42]), Some((42, 42)));
        assert_eq!(ends::<i32>(&[]), None);
    }

    #[test]
    fn test_palindrome() {
        assert!(palindrome_check(&[1,2,3,2,1]));
        assert!(!palindrome_check(&[1,2,3,4,5]));
        assert!(palindrome_check::<i32>(&[]));
        assert!(palindrome_check(&['a','b','a']));
    }

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

    #[test]
    fn test_rfind() {
        assert_eq!(rfind_demo(&[1,2,3,4,5], |x| *x > 3), Some(&5));
        assert_eq!(rfind_demo(&[1,2,3], |x| *x > 10), None);
    }

    #[test]
    fn test_rposition() {
        assert_eq!(rposition_demo(&[1,2,3,2,1], |x| *x == 2), Some(3));
    }

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

    #[test]
    fn test_reverse_words() {
        assert_eq!(reverse_words("hello world"), "world hello");
    }
}

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

📊 Detailed Comparison

Comparison: DoubleEndedIterator

Palindrome Check

OCaml:

🐪 Show OCaml equivalent
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)

Rust: 

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,
     }
 }
}

Take Last N

OCaml:

🐪 Show OCaml equivalent
let take_last n lst =
let len = List.length lst in
List.filteri (fun i _ -> i >= len - n) lst

Rust: 

fn take_last<T: Clone>(data: &[T], n: usize) -> Vec<T> {
 data.iter().rev().take(n).cloned().collect::<Vec<_>>().into_iter().rev().collect()
}

Trim from Both Ends

OCaml:

🐪 Show OCaml equivalent
let trim_while pred lst =
let front = List.to_seq lst |> Seq.drop_while pred |> List.of_seq in
List.rev front |> List.to_seq |> Seq.drop_while pred |> List.of_seq |> List.rev

Rust: 

fn trim_zeros(data: &[i32]) -> Vec<i32> {
 let start = data.iter().position(|&x| x != 0).unwrap_or(data.len());
 let end = data.iter().rposition(|&x| x != 0).map(|p| p + 1).unwrap_or(0);
 data[start..end].to_vec()
}

Related Examples

#888 094: Peekable Iterator 🌱 #890 096: ExactSizeIterator 🌱 #887 093: Windows and Chunks 🌱 #891 097: Flatten Iterator 🌱
All Examples