006 Fundamental

006 — Palindrome Check

Functional Programming

Tutorial

The Problem

A palindrome reads the same forwards and backwards — "racecar", "level", "A man a plan a canal Panama". Palindrome detection is a classic string processing problem that exercises iterator bidirectionality: comparing a sequence against its reverse without necessarily materializing the reverse. It appears in bioinformatics (DNA palindromes are recognition sites for restriction enzymes), signal processing (palindromic sequences), and string interview problems.

The problem also illustrates an important distinction between eager (allocating the reversed string) and lazy (comparing iterators without allocation) approaches — a recurring theme in functional programming where correctness comes first and optimization second.

🎯 Learning Outcomes

• Compare a sequence against its reverse using iterator bidirectionality

• Distinguish between allocating (collect to String) and non-allocating (.eq(rev())) approaches

• Handle Unicode correctly using chars() rather than byte-indexing

• Normalize input (lowercase, filter non-alphanumeric) for real-world palindrome checks

• Use Rust's DoubleEndedIterator for O(1) rev() without allocation

• Use s.chars().eq(s.chars().rev()) for zero-allocation palindrome checking that leverages DoubleEndedIterator

• Handle Unicode correctly with chars() rather than byte-level comparison

Code Example

#![allow(clippy::all)]
// 006: Palindrome Check

// Approach 1: Reverse and compare (allocating)
fn is_palindrome_rev(s: &str) -> bool {
    let reversed: String = s.chars().rev().collect();
    s == reversed
}

// Approach 2: Iterator comparison (zero allocation)
fn is_palindrome_iter(s: &str) -> bool {
    s.chars().eq(s.chars().rev())
}

// Approach 3: Case-insensitive, alphanumeric only
fn is_palindrome_clean(s: &str) -> bool {
    let clean: Vec<char> = s
        .chars()
        .filter(|c| c.is_alphanumeric())
        .map(|c| c.to_lowercase().next().unwrap())
        .collect();
    clean.iter().eq(clean.iter().rev())
}

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

    #[test]
    fn test_palindrome_rev() {
        assert!(is_palindrome_rev("racecar"));
        assert!(is_palindrome_rev("abba"));
        assert!(!is_palindrome_rev("hello"));
        assert!(is_palindrome_rev(""));
        assert!(is_palindrome_rev("a"));
    }

    #[test]
    fn test_palindrome_iter() {
        assert!(is_palindrome_iter("racecar"));
        assert!(!is_palindrome_iter("abc"));
    }

    #[test]
    fn test_palindrome_clean() {
        assert!(is_palindrome_clean("A man, a plan, a canal: Panama"));
        assert!(is_palindrome_clean("Race Car"));
        assert!(!is_palindrome_clean("hello world"));
    }
}

(* 006: Palindrome Check *)

(* Approach 1: Reverse and compare *)
let is_palindrome_rev s =
  let chars = List.of_seq (String.to_seq s) in
  chars = List.rev chars

(* Approach 2: Index-based comparison *)
let is_palindrome_idx s =
  let n = String.length s in
  let rec check i =
    if i >= n / 2 then true
    else if s.[i] <> s.[n - 1 - i] then false
    else check (i + 1)
  in
  check 0

(* Approach 3: Case-insensitive, alphanumeric only *)
let is_palindrome_clean s =
  let clean =
    s
    |> String.lowercase_ascii
    |> String.to_seq
    |> Seq.filter (fun c ->
      (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9'))
    |> List.of_seq
  in
  clean = List.rev clean

(* Tests *)
let () =
  assert (is_palindrome_rev "racecar");
  assert (is_palindrome_rev "abba");
  assert (not (is_palindrome_rev "hello"));
  assert (is_palindrome_rev "");
  assert (is_palindrome_rev "a");
  assert (is_palindrome_idx "racecar");
  assert (not (is_palindrome_idx "abc"));
  assert (is_palindrome_clean "A man, a plan, a canal: Panama");
  assert (is_palindrome_clean "Race Car");
  assert (not (is_palindrome_clean "hello world"));
  Printf.printf "✓ All tests passed\n"

Key Differences

Zero-copy rev: Rust's DoubleEndedIterator allows rev() on any iterator without allocation. OCaml's String.rev allocates a new string; you need a custom approach for zero-copy comparison.

Unicode: Rust's .chars() correctly iterates Unicode scalar values. Naive byte indexing (s.as_bytes()) breaks on multibyte characters. OCaml's s.[i] is byte-level by default; use Uchar for Unicode.

Normalization: Both languages require explicit lowercasing and filtering. Rust's char::to_lowercase() returns an iterator (handling ligatures that expand to multiple chars). OCaml's Char.lowercase_ascii is simpler but ASCII-only.

Comparison: Rust's iterator .eq() short-circuits at the first difference. OCaml's = on lists is structural equality that traverses the full list.

**DoubleEndedIterator:** Rust's .rev() on Chars works because Chars implements DoubleEndedIterator — it can be read from both ends. OCaml strings lack this; reversing requires String.init or a manual loop.

Unicode correctness: s.chars() iterates Unicode scalar values (code points). Byte-level reversal (s.bytes().rev()) would corrupt multi-byte characters. OCaml's strings are byte sequences — Unicode handling requires separate libraries.

Zero allocation: s.chars().eq(s.chars().rev()) allocates nothing — it compares lazily. OCaml's s = String.init (String.length s) (fun i -> s.[String.length s - 1 - i]) allocates a new string.

Normalization: Real-world palindrome checks require lowercasing and stripping non-alphanumeric characters. The to_lowercase() method in Rust returns an iterator (some Unicode characters expand to multiple chars), so .next().unwrap() is needed for single-char values.

OCaml Approach

OCaml's String module lacks a built-in String.rev, but it is easily constructed: let rev s = String.init (String.length s) (fun i -> s.[String.length s - 1 - i]). Character-level access is s.[i]. For the clean version, OCaml uses String.to_seq and Seq.filter, then compares sequences. The functional style avoids mutation: build a clean char list, compare it with its reverse using List.for_all2.

Full Source

#![allow(clippy::all)]
// 006: Palindrome Check

// Approach 1: Reverse and compare (allocating)
fn is_palindrome_rev(s: &str) -> bool {
    let reversed: String = s.chars().rev().collect();
    s == reversed
}

// Approach 2: Iterator comparison (zero allocation)
fn is_palindrome_iter(s: &str) -> bool {
    s.chars().eq(s.chars().rev())
}

// Approach 3: Case-insensitive, alphanumeric only
fn is_palindrome_clean(s: &str) -> bool {
    let clean: Vec<char> = s
        .chars()
        .filter(|c| c.is_alphanumeric())
        .map(|c| c.to_lowercase().next().unwrap())
        .collect();
    clean.iter().eq(clean.iter().rev())
}

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

    #[test]
    fn test_palindrome_rev() {
        assert!(is_palindrome_rev("racecar"));
        assert!(is_palindrome_rev("abba"));
        assert!(!is_palindrome_rev("hello"));
        assert!(is_palindrome_rev(""));
        assert!(is_palindrome_rev("a"));
    }

    #[test]
    fn test_palindrome_iter() {
        assert!(is_palindrome_iter("racecar"));
        assert!(!is_palindrome_iter("abc"));
    }

    #[test]
    fn test_palindrome_clean() {
        assert!(is_palindrome_clean("A man, a plan, a canal: Panama"));
        assert!(is_palindrome_clean("Race Car"));
        assert!(!is_palindrome_clean("hello world"));
    }
}

(* 006: Palindrome Check *)

(* Approach 1: Reverse and compare *)
let is_palindrome_rev s =
  let chars = List.of_seq (String.to_seq s) in
  chars = List.rev chars

(* Approach 2: Index-based comparison *)
let is_palindrome_idx s =
  let n = String.length s in
  let rec check i =
    if i >= n / 2 then true
    else if s.[i] <> s.[n - 1 - i] then false
    else check (i + 1)
  in
  check 0

(* Approach 3: Case-insensitive, alphanumeric only *)
let is_palindrome_clean s =
  let clean =
    s
    |> String.lowercase_ascii
    |> String.to_seq
    |> Seq.filter (fun c ->
      (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9'))
    |> List.of_seq
  in
  clean = List.rev clean

(* Tests *)
let () =
  assert (is_palindrome_rev "racecar");
  assert (is_palindrome_rev "abba");
  assert (not (is_palindrome_rev "hello"));
  assert (is_palindrome_rev "");
  assert (is_palindrome_rev "a");
  assert (is_palindrome_idx "racecar");
  assert (not (is_palindrome_idx "abc"));
  assert (is_palindrome_clean "A man, a plan, a canal: Panama");
  assert (is_palindrome_clean "Race Car");
  assert (not (is_palindrome_clean "hello world"));
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_palindrome_rev() {
        assert!(is_palindrome_rev("racecar"));
        assert!(is_palindrome_rev("abba"));
        assert!(!is_palindrome_rev("hello"));
        assert!(is_palindrome_rev(""));
        assert!(is_palindrome_rev("a"));
    }

    #[test]
    fn test_palindrome_iter() {
        assert!(is_palindrome_iter("racecar"));
        assert!(!is_palindrome_iter("abc"));
    }

    #[test]
    fn test_palindrome_clean() {
        assert!(is_palindrome_clean("A man, a plan, a canal: Panama"));
        assert!(is_palindrome_clean("Race Car"));
        assert!(!is_palindrome_clean("hello world"));
    }
}

Deep Comparison

Core Insight

A palindrome reads the same forwards and backwards. The simplest check: reverse and compare. Both languages make this a one-liner, but the underlying data structures differ (OCaml string vs Rust UTF-8 String).

OCaml Approach

• Convert string to char list, reverse, compare

• Or use index-based comparison from both ends

• String.to_seq + List.of_seq for char extraction

Rust Approach

• s.chars().rev().collect::<String>() == s

• Or s.chars().eq(s.chars().rev()) — no allocation

• .chars() handles UTF-8 correctly

Comparison Table

Feature	OCaml	Rust
Reverse string	`String.to_seq \\|> List.of_seq \\|> List.rev`	`s.chars().rev()`
Compare	`=` structural equality	`==` or `.eq()`
UTF-8	Byte-based strings	`.chars()` for Unicode
Zero-alloc check	Index loop	`.chars().eq(s.chars().rev())`

Exercises

Largest palindrome substring: Write largest_palindrome(s: &str) -> &str that returns the longest palindromic substring using Manacher's algorithm or naive O(n²) expansion.

Palindrome pairs: Given a list of words, find all pairs (i, j) where concatenating words i and j forms a palindrome.

Streaming check: Write is_palindrome_stream(iter: impl Iterator<Item=char>) -> bool that checks if a character stream is a palindrome by collecting to Vec<char> then comparing with its reverse.

Longest palindrome substring: Implement Manacher's algorithm (or a simpler O(n²) version) to find the longest palindromic substring of a given string.

Palindrome pairs: Given a list of words, find all pairs (i, j) where words[i] + words[j] is a palindrome, using HashSet for O(n) lookup.

Open Source Repos

functional-rust

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

Rust