929 Fundamental

929-palindrome-check — Palindrome Check

Functional Programming

Tutorial

The Problem

A palindrome reads the same forwards and backwards: "racecar", [1,2,1], "madam". Palindrome checking exercises iterator-based bidirectional comparison, a fundamental algorithm pattern. The naive approach reverses the sequence and compares — O(n) time and O(n) space. The efficient approach compares from both ends using a double-ended iterator — O(n) time and O(1) space. This algorithm appears in DNA sequence analysis (palindromic restriction enzyme sites), string processing, and as a classic interview problem. Rust's .eq(iter.rev()) idiom makes it a clean one-liner.

🎯 Learning Outcomes

• Use .iter().eq(slice.iter().rev()) for a clean one-liner palindrome check

• Understand that this compares two iterators element-by-element with O(n) passes

• Implement the manual comparison approach for educational purposes

• Apply the generic palindrome check to both &[i32] and &str character slices

• Compare with OCaml's list = List.rev list approach

Code Example

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

let is_palindrome lst =
  lst = List.rev lst

Key Differences

One-liner: Rust list.iter().eq(list.iter().rev()) is elegant and generic; OCaml xs = List.rev xs is equally elegant but allocates a reversed copy.

Bidirectional: Rust's approach conceptually traverses from both ends via two iterators; OCaml reverses first then compares linearly.

Generic: Rust's <T: PartialEq> works for any type; OCaml's structural = also works for any type but may be slower for complex types.

Short-circuit: Rust's .eq() short-circuits on first mismatch; OCaml's list equality also short-circuits.

OCaml Approach

OCaml: let is_palindrome xs = xs = List.rev xs — reverse and compare using structural equality. This creates a new reversed list (O(n) allocation) then compares. More efficient: pattern matching from both ends is awkward with singly-linked lists — it requires converting to an array. let is_palindrome_arr xs = let arr = Array.of_list xs in let n = Array.length arr in let rec go i j = i >= j || arr.(i) = arr.(j) && go (i+1) (j-1) in go 0 (n-1).

Full Source

#![allow(clippy::all)]
// 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);
    }
}

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

✓ Tests Rust test suite

#[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);
    }
}

Deep Comparison

Comparison: Palindrome Check

OCaml — Using List.rev

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

Rust's DoubleEndedIterator eliminates the need for explicit list reversal

Slice-based random access makes palindrome checking more efficient than linked-list traversal

OCaml's structural equality is convenient but less flexible than Rust's trait-based PartialEq

The iterator approach (iter().eq(iter().rev())) is the closest Rust analog to OCaml's style

Rust's zero-cost abstractions mean the iterator version compiles to the same code as manual indexing

Exercises

Implement is_palindrome_str(s: &str) -> bool that handles Unicode correctly (comparing grapheme clusters, not bytes).

Write longest_palindromic_substring(s: &str) -> &str that finds the longest palindromic substring.

Implement make_palindrome<T: Clone>(prefix: &[T]) -> Vec<T> that appends the reverse of the prefix to make a palindrome.

Open Source Repos

functional-rust

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

Rust