006: Palindrome Check

Difficulty: ⭐ Level: Beginner Determine if a sequence reads the same forwards and backwards — with zero extra memory.

The Problem This Solves

A palindrome reads the same in both directions: `[1, 2, 3, 2, 1]`, the word "racecar", a DNA sequence. You need to compare elements at mirror positions — first with last, second with second-to-last, and so on. The obvious approach: reverse the list, then compare. That works, but it allocates a whole new copy of your data just to compare it. If you're checking a 10MB log sequence, that's 10MB wasted. Rust's iterator model offers a better path: walk from both ends at the same time, without ever materializing the reversed sequence. Short-circuit on the first mismatch. Zero allocation. This is possible because Rust slices support efficient access from either end.

The Intuition

# Python — creates a full reversed copy
def is_palindrome(lst):
 return lst == lst[::-1]

# JavaScript — also creates a copy
function isPalindrome(arr) {
return arr.join(',') === [...arr].reverse().join(',');
}

Rust's iterator trick:

// Zero allocation — walks both ends toward the middle simultaneously
list.iter().eq(list.iter().rev())

`iter()` walks left-to-right. `iter().rev()` walks right-to-left. The `.eq()` method zips them together and compares element by element, stopping the moment it finds a mismatch. No reversed copy needed. It's like checking a palindrome by hand: you don't write it backwards on paper, you just point at the first letter and the last letter, then move your fingers toward the middle.

How It Works in Rust

// The idiomatic solution — O(n) time, O(1) space
fn is_palindrome<T: PartialEq>(list: &[T]) -> bool {
 list.iter().eq(list.iter().rev())
}

The `T: PartialEq` bound means "this works for any type that supports equality comparison" — integers, strings, custom structs (if they implement `PartialEq`). Alternative (mirrors the OCaml approach — creates a reversed copy):

fn is_palindrome_alloc<T: PartialEq + Clone>(list: &[T]) -> bool {
 let reversed: Vec<_> = list.iter().rev().cloned().collect();
 list == reversed.as_slice()
}

This is simpler to understand but allocates `O(n)` memory. The first version is preferred in production code.

// Edge cases — all handled correctly:
is_palindrome::<i32>(&[])          // true  (empty is a palindrome)
is_palindrome(&[1])                // true  (single element)
is_palindrome(&[1, 2, 3, 2, 1])   // true
is_palindrome(&[1, 2, 3, 4])      // false (stops at first mismatch)

What This Unlocks

Input validation — symmetric structures in parsers, network packets, or file formats
String palindromes — apply the same logic to `&[char]` or byte slices
DoubleEndedIterator — the trait that makes `.rev()` work; any iterator that supports it can use this pattern

Key Differences

Concept	OCaml	Rust
Idiomatic approach	`lst = List.rev lst` (allocates)	`iter().eq(iter().rev())` (zero alloc)
Reversal cost	Always O(n) allocation	Lazy — only if you `collect()`
Equality	Polymorphic `=` (implicit)	`PartialEq` trait (explicit bound)
Short-circuit	No (full reverse then compare)	Yes (stops at first mismatch)
Bidirectional iteration	Not available on linked lists	`DoubleEndedIterator` on slices

// Palindrome Check
// Rust translation from OCaml 99 Problems #6

// Idiomatic Rust
fn is_palindrome<T: PartialEq>(list: &[T]) -> bool {
    list.iter().eq(list.iter().rev())
}

// Alternative: manual comparison
fn is_palindrome_manual<T: PartialEq + Clone>(list: &[T]) -> bool {
    let reversed: Vec<_> = list.iter().rev().cloned().collect();
    list == reversed.as_slice()
}

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

    #[test]
    fn test_palindrome() {
        assert_eq!(is_palindrome(&[1, 2, 3, 2, 1]), true);
        assert_eq!(is_palindrome(&[1, 2, 3, 4]), false);
        assert_eq!(is_palindrome::<i32>(&[]), true);
        assert_eq!(is_palindrome(&[1]), true);
    }
}

fn main() {
    println!("is_palindrome([1,2,3,2,1]) = {}", is_palindrome(&[1, 2, 3, 2, 1]));
    println!("is_palindrome([1,2,3,4]) = {}", is_palindrome(&[1, 2, 3, 4]));
    println!("✓ Rust tests passed");
}

(* Palindrome Check *)
(* OCaml 99 Problems #6 *)

(* Solution 1: Using List.rev *)
let is_palindrome lst =
  lst = List.rev lst

(* Solution 2: Manual comparison *)
let is_palindrome_manual lst =
  let rec compare l1 l2 =
    match l1, l2 with
    | [], [] -> true
    | _, [] | [], _ -> false
    | h1 :: t1, h2 :: t2 -> h1 = h2 && compare t1 t2
  in
  compare lst (List.rev lst)

(* Tests *)
let () =
  assert (is_palindrome [1; 2; 3; 2; 1] = true);
  assert (is_palindrome [1; 2; 3; 4] = false);
  assert (is_palindrome [] = true);
  assert (is_palindrome [1] = true);
  print_endline "✓ OCaml tests passed"

📊 Detailed Comparison

Comparison: Palindrome Check

OCaml — Using List.rev

🐪 Show OCaml equivalent

let is_palindrome lst =
lst = List.rev lst

Rust — Idiomatic (index-based, zero allocation)

pub fn is_palindrome<T: PartialEq>(list: &[T]) -> bool {
 let n = list.len();
 (0..n / 2).all(|i| list[i] == list[n - 1 - i])
}

Rust — Functional (iterator-based)

pub fn is_palindrome_iter<T: PartialEq>(list: &[T]) -> bool {
 list.iter().eq(list.iter().rev())
}

Comparison Table

Aspect	OCaml	Rust
Input type	`'a list` (linked list)	`&[T]` (slice reference)
Equality	Structural `=` (polymorphic)	`PartialEq` trait bound
Reversal	`List.rev` → new list (O(n) alloc)	`iter().rev()` → zero alloc
Access pattern	Sequential only	Random access O(1)
Memory	GC-managed	Borrowed reference

Type Signatures

OCaml: `val is_palindrome : 'a list -> bool`
Rust: `fn is_palindrome<T: PartialEq>(list: &[T]) -> bool`

Takeaways

1. Rust's `DoubleEndedIterator` eliminates the need for explicit list reversal 2. Slice-based random access makes palindrome checking more efficient than linked-list traversal 3. OCaml's structural equality is convenient but less flexible than Rust's trait-based `PartialEq` 4. The iterator approach (`iter().eq(iter().rev())`) is the closest Rust analog to OCaml's style 5. Rust's zero-cost abstractions mean the iterator version compiles to the same code as manual indexing