930 Fundamental

930-pangram-check — Pangram Check

Functional Programming

Tutorial

The Problem

A pangram is a sentence containing every letter of the alphabet at least once. "The quick brown fox jumps over the lazy dog" is the famous example, used for font demonstrations and keyboard testing. Checking for a pangram is a set-membership problem: does the set of distinct lowercase letters in the sentence contain all 26 letters? Three approaches illuminate different algorithmic ideas: set-based (clear and general), bitflag (memory-minimal, no heap allocation), and recursive (OCaml-style demonstration). The bitflag approach — one bit per letter in a 32-bit integer — is a classic compact set representation for small fixed-universe sets.

🎯 Learning Outcomes

• Use HashSet<char> to collect unique letters and check for 26 distinct entries

• Implement the bitflag approach using u32 as a 26-bit set — zero heap allocation

• Recognize 1 << idx as the set-insert operation and (1 << 26) - 1 as the "all set" check

• Implement a recursive approach mirroring OCaml's style

• Compare the three approaches' trade-offs in readability, allocation, and performance

Code Example

#![allow(clippy::all)]
/// # Pangram Check
///
/// A pangram is a sentence using every letter of the alphabet at least once.
/// Demonstrates set-based string analysis.
use std::collections::HashSet;

/// Idiomatic Rust using HashSet and iterator chains.
/// The `collect()` into HashSet automatically deduplicates.
pub fn is_pangram(sentence: &str) -> bool {
    // Filter to only alphabetic chars, lowercase them, collect unique into set
    let unique_letters: HashSet<char> = sentence
        .chars()
        .filter(|c| c.is_ascii_alphabetic())
        .map(|c| c.to_ascii_lowercase())
        .collect();
    unique_letters.len() == 26
}

/// Bitflag approach — uses a u32 as a compact set of 26 bits.
/// Each bit represents a letter: bit 0 = 'a', bit 1 = 'b', etc.
/// No heap allocation needed!
pub fn is_pangram_bitflag(sentence: &str) -> bool {
    let mut seen: u32 = 0;
    for c in sentence.chars() {
        if c.is_ascii_alphabetic() {
            let idx = c.to_ascii_lowercase() as u32 - 'a' as u32;
            seen |= 1 << idx;
        }
    }
    seen == (1 << 26) - 1
}

/// Recursive approach — checks if each letter 'a'..'z' exists in the string.
pub fn is_pangram_recursive(sentence: &str) -> bool {
    fn has_all(sentence: &str, letter: u8) -> bool {
        if letter > b'z' {
            return true;
        }
        let lower = sentence.to_ascii_lowercase();
        lower.contains(letter as char) && has_all(sentence, letter + 1)
    }
    has_all(sentence, b'a')
}

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

    #[test]
    fn test_classic_pangram() {
        assert!(is_pangram("The quick brown fox jumps over the lazy dog"));
    }

    #[test]
    fn test_not_pangram() {
        assert!(!is_pangram("Hello world"));
    }

    #[test]
    fn test_empty_string() {
        assert!(!is_pangram(""));
    }

    #[test]
    fn test_missing_x() {
        assert!(!is_pangram("The quick brown fo jumps over the lazy dog"));
    }

    #[test]
    fn test_mixed_case() {
        assert!(is_pangram("THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG"));
    }

    #[test]
    fn test_with_numbers_and_punctuation() {
        assert!(is_pangram(
            "The 1 quick brown fox jumps! over the 2 lazy dogs."
        ));
    }

    #[test]
    fn test_bitflag_version() {
        assert!(is_pangram_bitflag(
            "The quick brown fox jumps over the lazy dog"
        ));
        assert!(!is_pangram_bitflag("Hello world"));
    }

    #[test]
    fn test_recursive_version() {
        assert!(is_pangram_recursive(
            "The quick brown fox jumps over the lazy dog"
        ));
        assert!(!is_pangram_recursive("abc"));
    }
}

(* Pangram Check — Set-based string analysis *)

module CS = Set.Make(Char)

let alphabet =
  List.init 26 (fun i -> Char.chr (i + Char.code 'a'))
  |> CS.of_list

(* Idiomatic OCaml: filter to alpha chars, build set, check subset *)
let is_pangram s =
  let chars = s |> String.lowercase_ascii |> String.to_seq
    |> Seq.filter (fun c -> c >= 'a' && c <= 'z')
    |> CS.of_seq in
  CS.subset alphabet chars

(* Recursive: check each letter exists *)
let is_pangram_recursive s =
  let lower = String.lowercase_ascii s in
  let rec check c =
    if c > 'z' then true
    else String.contains lower c && check (Char.chr (Char.code c + 1))
  in
  check 'a'

let () =
  assert (is_pangram "The quick brown fox jumps over the lazy dog");
  assert (not (is_pangram "Hello world"));
  assert (is_pangram_recursive "The quick brown fox jumps over the lazy dog");
  assert (not (is_pangram_recursive "abc"));
  Printf.printf "All pangram tests passed!\n"

Key Differences

Set implementation: Rust HashSet<char> vs OCaml Hashtbl or List.sort_uniq — same semantics, different APIs.

Bitflag safety: Rust's u32 bitfield uses safe arithmetic; OCaml's lsl on native integers can overflow (63-bit on 64-bit systems).

Recursive style: Rust's recursion over u8 (letter codes) mirrors OCaml's style but requires explicit bounds checking.

Char comparison: Rust uses 'a' as u32 numeric conversion; OCaml uses Char.code 'a'.

OCaml Approach

OCaml is_pangram s = let letters = s |> String.lowercase_ascii |> String.to_seq |> Seq.filter (fun c -> c >= 'a' && c <= 'z') |> List.of_seq |> List.sort_uniq compare in List.length letters = 26. Or using a Hashtbl. The bitflag approach: let check_pangram s = let seen = ref 0 in String.iter (fun c -> if c >= 'a' && c <= 'z' then seen := !seen lor (1 lsl (Char.code c - Char.code 'a'))) s; !seen = (1 lsl 26) - 1. OCaml's lsl for left shift vs Rust's <<.

Full Source

#![allow(clippy::all)]
/// # Pangram Check
///
/// A pangram is a sentence using every letter of the alphabet at least once.
/// Demonstrates set-based string analysis.
use std::collections::HashSet;

/// Idiomatic Rust using HashSet and iterator chains.
/// The `collect()` into HashSet automatically deduplicates.
pub fn is_pangram(sentence: &str) -> bool {
    // Filter to only alphabetic chars, lowercase them, collect unique into set
    let unique_letters: HashSet<char> = sentence
        .chars()
        .filter(|c| c.is_ascii_alphabetic())
        .map(|c| c.to_ascii_lowercase())
        .collect();
    unique_letters.len() == 26
}

/// Bitflag approach — uses a u32 as a compact set of 26 bits.
/// Each bit represents a letter: bit 0 = 'a', bit 1 = 'b', etc.
/// No heap allocation needed!
pub fn is_pangram_bitflag(sentence: &str) -> bool {
    let mut seen: u32 = 0;
    for c in sentence.chars() {
        if c.is_ascii_alphabetic() {
            let idx = c.to_ascii_lowercase() as u32 - 'a' as u32;
            seen |= 1 << idx;
        }
    }
    seen == (1 << 26) - 1
}

/// Recursive approach — checks if each letter 'a'..'z' exists in the string.
pub fn is_pangram_recursive(sentence: &str) -> bool {
    fn has_all(sentence: &str, letter: u8) -> bool {
        if letter > b'z' {
            return true;
        }
        let lower = sentence.to_ascii_lowercase();
        lower.contains(letter as char) && has_all(sentence, letter + 1)
    }
    has_all(sentence, b'a')
}

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

    #[test]
    fn test_classic_pangram() {
        assert!(is_pangram("The quick brown fox jumps over the lazy dog"));
    }

    #[test]
    fn test_not_pangram() {
        assert!(!is_pangram("Hello world"));
    }

    #[test]
    fn test_empty_string() {
        assert!(!is_pangram(""));
    }

    #[test]
    fn test_missing_x() {
        assert!(!is_pangram("The quick brown fo jumps over the lazy dog"));
    }

    #[test]
    fn test_mixed_case() {
        assert!(is_pangram("THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG"));
    }

    #[test]
    fn test_with_numbers_and_punctuation() {
        assert!(is_pangram(
            "The 1 quick brown fox jumps! over the 2 lazy dogs."
        ));
    }

    #[test]
    fn test_bitflag_version() {
        assert!(is_pangram_bitflag(
            "The quick brown fox jumps over the lazy dog"
        ));
        assert!(!is_pangram_bitflag("Hello world"));
    }

    #[test]
    fn test_recursive_version() {
        assert!(is_pangram_recursive(
            "The quick brown fox jumps over the lazy dog"
        ));
        assert!(!is_pangram_recursive("abc"));
    }
}

(* Pangram Check — Set-based string analysis *)

module CS = Set.Make(Char)

let alphabet =
  List.init 26 (fun i -> Char.chr (i + Char.code 'a'))
  |> CS.of_list

(* Idiomatic OCaml: filter to alpha chars, build set, check subset *)
let is_pangram s =
  let chars = s |> String.lowercase_ascii |> String.to_seq
    |> Seq.filter (fun c -> c >= 'a' && c <= 'z')
    |> CS.of_seq in
  CS.subset alphabet chars

(* Recursive: check each letter exists *)
let is_pangram_recursive s =
  let lower = String.lowercase_ascii s in
  let rec check c =
    if c > 'z' then true
    else String.contains lower c && check (Char.chr (Char.code c + 1))
  in
  check 'a'

let () =
  assert (is_pangram "The quick brown fox jumps over the lazy dog");
  assert (not (is_pangram "Hello world"));
  assert (is_pangram_recursive "The quick brown fox jumps over the lazy dog");
  assert (not (is_pangram_recursive "abc"));
  Printf.printf "All pangram tests passed!\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_classic_pangram() {
        assert!(is_pangram("The quick brown fox jumps over the lazy dog"));
    }

    #[test]
    fn test_not_pangram() {
        assert!(!is_pangram("Hello world"));
    }

    #[test]
    fn test_empty_string() {
        assert!(!is_pangram(""));
    }

    #[test]
    fn test_missing_x() {
        assert!(!is_pangram("The quick brown fo jumps over the lazy dog"));
    }

    #[test]
    fn test_mixed_case() {
        assert!(is_pangram("THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG"));
    }

    #[test]
    fn test_with_numbers_and_punctuation() {
        assert!(is_pangram(
            "The 1 quick brown fox jumps! over the 2 lazy dogs."
        ));
    }

    #[test]
    fn test_bitflag_version() {
        assert!(is_pangram_bitflag(
            "The quick brown fox jumps over the lazy dog"
        ));
        assert!(!is_pangram_bitflag("Hello world"));
    }

    #[test]
    fn test_recursive_version() {
        assert!(is_pangram_recursive(
            "The quick brown fox jumps over the lazy dog"
        ));
        assert!(!is_pangram_recursive("abc"));
    }
}

Deep Comparison

Pangram Check — OCaml vs Rust Comparison

Core Insight

Both languages excel at set operations on characters, but Rust offers a zero-allocation bitflag approach alongside the idiomatic HashSet version. OCaml's Set.Make functor creates a balanced tree set, while Rust's HashSet is hash-based.

OCaml Approach

Uses the Set.Make(Char) functor to create a character set module. Characters are filtered with Seq.filter, collected with CS.of_seq, and checked with CS.subset. The functor system requires declaring a module upfront.

Rust Approach

Iterator chain: .chars().filter().map().collect::<HashSet<_>>() — the type drives collect() to deduplicate automatically. The bitflag variant uses u32 as a 26-bit set with zero heap allocation, which has no direct OCaml equivalent without manual bit manipulation.

Comparison Table

Aspect	OCaml	Rust
Memory	Tree-based set (heap nodes)	HashSet (heap) or u32 bitflag (stack)
Null safety	N/A (bool result)	N/A (bool result)
Errors	Not applicable	Not applicable
Iteration	`Seq.filter` + `CS.of_seq`	`.chars().filter().map().collect()`
Set type	`Set.Make` functor (balanced tree)	`HashSet` (hash table)

Things Rust Learners Should Notice

**collect() is polymorphic** — collecting into HashSet vs Vec changes behavior (dedup vs preserve)

Bitflag sets are a common Rust idiom for small fixed domains — zero allocation, cache-friendly

**is_ascii_alphabetic()** — Rust has rich character classification methods built in

No module functor needed — HashSet<char> works directly without declaring a module

**to_ascii_lowercase()** works on individual chars, not just strings

Exercises

Generalize is_pangram to covers_all<T: Hash + Eq>(text: impl IntoIterator<Item=T>, required: impl IntoIterator<Item=T>) -> bool.

Implement pangram_missing_letters(s: &str) -> Vec<char> that returns the alphabetically sorted list of missing letters.

Write shortest_pangram(words: &[&str]) -> Option<Vec<&str>> that finds the minimum-word-count subset that forms a pangram.

Open Source Repos

functional-rust

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

Rust

Tutorial

The Problem

🎯 Learning Outcomes

Code Example

Key Differences

OCaml Approach

Full Source

Deep Comparison

Pangram Check — OCaml vs Rust Comparison

Core Insight

OCaml Approach

Rust Approach

Comparison Table

Things Rust Learners Should Notice

Further Reading

Exercises

Open Source Repos