🎬 Fearless Concurrency Threads, Arc>, channels — safe parallelism enforced by the compiler.

📝 Text version (for readers / accessibility)

• std::thread::spawn creates OS threads — closures must be Send + 'static

• Arc> provides shared mutable state across threads safely

• Channels (mpsc) enable message passing — multiple producers, single consumer

• Send and Sync marker traits enforce thread safety at compile time

• Data races are impossible — the type system prevents them before your code runs

Example 276: Parallel Letter Frequency

Difficulty: ⭐⭐ Category: Higher-Order Functions OCaml Source: https://exercism.org/tracks/ocaml/exercises/parallel-letter-frequency

Problem Statement

Count the frequency of each letter across multiple texts using a map-reduce pattern: map each text to a frequency table, then reduce (merge) all tables into one combined result.

Learning Outcomes

How to implement map-reduce with iterators and `fold`
Using `HashMap::entry` API for efficient in-place updates
Translating OCaml's `Map.Make` functor to Rust's `HashMap`
Pattern matching on slices for recursive decomposition

OCaml Approach

OCaml uses a functor-generated `Map.Make(Char)` for an ordered char map. `String.fold_left` builds per-text frequency maps, and `CMap.union` with a merge function combines them. The pipeline `|> List.map |> List.fold_left` is classic map-reduce.

Rust Approach

Rust uses `HashMap<char, usize>` with the `entry` API for ergonomic insert-or-update. The iterator chain `.iter().map().fold()` mirrors OCaml's pipeline. A recursive variant uses slice pattern matching `[head, rest @ ..]`.

Key Differences

1. Map type: OCaml uses `Map.Make(Char)` (ordered, functor-generated); Rust uses `HashMap` (unordered, generic) 2. Entry API: OCaml's `CMap.update` takes an `option -> option` function; Rust's `entry().or_insert()` is more ergonomic for counters 3. Merge strategy: OCaml's `CMap.union` takes a 3-argument merge function; Rust requires manual iteration over entries 4. Mutability: OCaml maps are immutable (each operation returns new map); Rust's `HashMap` is mutated in place for efficiency

use std::collections::HashMap;

/// Count letter frequencies in a single string.
fn letter_freq(s: &str) -> HashMap<char, usize> {
    s.chars().fold(HashMap::new(), |mut map, c| {
        let c = c.to_ascii_lowercase();
        if c.is_ascii_lowercase() {
            *map.entry(c).or_insert(0) += 1;
        }
        map
    })
}

/// Merge two frequency maps by summing counts.
fn merge_maps(mut a: HashMap<char, usize>, b: &HashMap<char, usize>) -> HashMap<char, usize> {
    for (&ch, &count) in b {
        *a.entry(ch).or_insert(0) += count;
    }
    a
}

/// Map-reduce: compute letter frequencies across multiple texts.
fn parallel_frequency(texts: &[&str]) -> HashMap<char, usize> {
    texts
        .iter()
        .map(|text| letter_freq(text))
        .fold(HashMap::new(), |acc, freq| merge_maps(acc, &freq))
}

/// Recursive version — processes texts one at a time.
fn parallel_frequency_recursive(texts: &[&str]) -> HashMap<char, usize> {
    match texts {
        [] => HashMap::new(),
        [single] => letter_freq(single),
        [head, rest @ ..] => {
            let head_freq = letter_freq(head);
            let rest_freq = parallel_frequency_recursive(rest);
            merge_maps(head_freq, &rest_freq)
        }
    }
}

fn main() {
    let texts = &["Hello World", "Functional Programming", "OCaml is Great"];
    let freq = parallel_frequency(texts);

    let mut entries: Vec<_> = freq.iter().collect();
    entries.sort_by_key(|&(ch, _)| *ch);
    for (ch, count) in &entries {
        print!("{}:{} ", ch, count);
    }
    println!();

    println!("'o' count = {}", freq[&'o']);

    // Verify recursive version matches
    let freq2 = parallel_frequency_recursive(texts);
    assert_eq!(freq, freq2);
    println!("Recursive matches iterative: ✓");
}

/* Output:
   a:4 c:2 d:1 e:2 f:1 g:3 h:1 i:3 l:5 m:3 n:3 o:5 p:1 r:4 s:1 t:2 u:1 w:1
   'o' count = 5
   Recursive matches iterative: ✓
*/

module CMap = Map.Make(Char)

(* Count letter frequencies in a single string *)
let letter_freq s =
  String.fold_left (fun m c ->
    let c = Char.lowercase_ascii c in
    if c >= 'a' && c <= 'z' then
      CMap.update c (function None -> Some 1 | Some n -> Some (n+1)) m
    else m
  ) CMap.empty s

(* Merge two frequency maps by summing counts *)
let merge_maps =
  CMap.union (fun _ a b -> Some (a + b))

(* Map-reduce: map each text to freq, then fold-merge *)
let parallel_frequency texts =
  texts
  |> List.map letter_freq
  |> List.fold_left merge_maps CMap.empty

let () =
  let texts = ["Hello World"; "Functional Programming"; "OCaml is Great"] in
  let freq = parallel_frequency texts in
  CMap.iter (Printf.printf "%c:%d ") freq;
  print_newline ();
  (* Basic assertions *)
  assert (CMap.find 'o' freq = 5);
  assert (CMap.mem 'h' freq);
  print_endline "ok"

📊 Detailed Comparison

OCaml vs Rust: Parallel Letter Frequency

Side-by-Side Code

OCaml

🐪 Show OCaml equivalent

module CMap = Map.Make(Char)

let letter_freq s =
String.fold_left (fun m c ->
 let c = Char.lowercase_ascii c in
 if c >= 'a' && c <= 'z' then
   CMap.update c (function None -> Some 1 | Some n -> Some (n+1)) m
 else m
) CMap.empty s

let merge_maps =
CMap.union (fun _ a b -> Some (a + b))

let parallel_frequency texts =
texts |> List.map letter_freq |> List.fold_left merge_maps CMap.empty

Rust (idiomatic)

fn letter_freq(s: &str) -> HashMap<char, usize> {
 s.chars().fold(HashMap::new(), |mut map, c| {
     let c = c.to_ascii_lowercase();
     if c.is_ascii_lowercase() {
         *map.entry(c).or_insert(0) += 1;
     }
     map
 })
}

fn merge_maps(mut a: HashMap<char, usize>, b: &HashMap<char, usize>) -> HashMap<char, usize> {
 for (&ch, &count) in b {
     *a.entry(ch).or_insert(0) += count;
 }
 a
}

fn parallel_frequency(texts: &[&str]) -> HashMap<char, usize> {
 texts.iter().map(|t| letter_freq(t)).fold(HashMap::new(), |acc, f| merge_maps(acc, &f))
}

Rust (functional/recursive)

fn parallel_frequency_recursive(texts: &[&str]) -> HashMap<char, usize> {
 match texts {
     [] => HashMap::new(),
     [single] => letter_freq(single),
     [head, rest @ ..] => {
         let head_freq = letter_freq(head);
         let rest_freq = parallel_frequency_recursive(rest);
         merge_maps(head_freq, &rest_freq)
     }
 }
}

Type Signatures

Concept	OCaml	Rust
Frequency map	`char CMap.t` (via `Map.Make(Char)`)	`HashMap<char, usize>`
Count type	`int`	`usize`
Text list	`string list`	`&[&str]` (slice of string slices)
Update function	`CMap.update : key -> (val option -> val option) -> map -> map`	`map.entry(key).or_insert(default)` returns `&mut V`
Merge function	`CMap.union : (key -> val -> val -> val option) -> map -> map -> map`	Manual iteration + entry API

Key Insights

1. Functor vs generic: OCaml needs `Map.Make(Char)` to create a char-keyed map module; Rust's `HashMap<K, V>` is generic out of the box — no functor ceremony needed 2. Immutable vs mutable maps: OCaml's `CMap.update` returns a new map each time (persistent data structure); Rust mutates the HashMap in place, which is more cache-friendly 3. Entry API elegance: Rust's `entry().or_insert()` pattern replaces OCaml's `function None -> Some 1 | Some n -> Some (n+1)` — less boilerplate for the common "upsert" pattern 4. Union vs manual merge: OCaml's `CMap.union` is a single elegant call with a merge function; Rust has no built-in HashMap merge, requiring explicit iteration 5. Pipeline preservation: Both languages express map-reduce cleanly — OCaml with `|>` pipeline, Rust with `.iter().map().fold()` method chain

When to Use Each Style

Use idiomatic Rust when: You want maximum performance — in-place mutation avoids allocation overhead of creating new maps on every insert. This is the natural Rust approach for frequency counting.

Use recursive Rust when: Teaching the map-reduce concept explicitly — the recursive decomposition `[head, rest @ ..]` makes the "divide and conquer" structure visible, matching OCaml's mental model of list processing.