🎬 How Rust Iterators Work Lazy evaluation, chaining, collect(), and zero-cost abstractions.

📝 Text version (for readers / accessibility)

• Iterators are lazy — .map(), .filter(), .take() build a chain but do no work until consumed

• .collect() triggers evaluation, transforming the chain into a Vec, HashMap, or other collection

• Zero-cost abstraction: iterator chains compile to the same machine code as hand-written loops

• .iter() borrows, .into_iter() consumes, .iter_mut() borrows mutably

• Chaining replaces nested loops with a readable, composable pipeline

094: Run-Length Encoding

Difficulty: 1 Level: Beginner Compress a string by replacing runs of identical characters with a count and character.

The Problem This Solves

"AABCCCDEEEE" is 11 characters. "2AB3CD4E" is 8. Run-length encoding (RLE) exploits repetition: instead of storing each character individually, store how many times it appears consecutively. For inputs with long runs (fax images, simple graphics, repeated log entries), RLE achieves significant compression. Beyond compression, the grouping pattern — "track current element and count, flush when element changes" — appears constantly: counting word frequencies, summarising log streams, detecting transitions in sensor data.

The Intuition

Walk the string character by character. Keep a counter for the current character. When the next character matches the current one, increment the counter. When it doesn't match (or you reach the end), emit the count (if > 1) and the character, then reset. The key insight: you must flush the last group after the loop. It's easy to forget — a common off-by-one in grouping algorithms. The functional version uses `fold` to build a list of `(char, count)` pairs, then maps each pair to its encoded string. The "current group" becomes `groups.last_mut()` — mutate the last entry if the character matches, push a new entry if it doesn't.

How It Works in Rust

// Imperative — explicit loop with tracking
pub fn encode(s: &str) -> String {
 if s.is_empty() { return String::new(); }
 let chars: Vec<char> = s.chars().collect();
 let mut result = String::new();
 let mut count = 1;

 for i in 1..chars.len() {
     if chars[i] == chars[i - 1] {
         count += 1;
     } else {
         if count > 1 { result.push_str(&count.to_string()); }
         result.push(chars[i - 1]);
         count = 1;
     }
 }
 if count > 1 { result.push_str(&count.to_string()); }
 result.push(*chars.last().unwrap());  // flush last group
 result
}

// Fold-based — groups built functionally
pub fn encode_fold(s: &str) -> String {
 s.chars()
     .fold(Vec::<(char, usize)>::new(), |mut acc, c| {
         match acc.last_mut() {
             Some((last, count)) if *last == c => *count += 1,  // extend group
             _ => acc.push((c, 1)),                             // new group
         }
         acc
     })
     .iter()
     .map(|&(c, n)| if n > 1 { format!("{}{}", n, c) } else { c.to_string() })
     .collect()
}

The fold approach eliminates the "flush after loop" problem: every group is pushed explicitly when the character changes, and the last group is naturally the last element of `acc`. No special-case needed.

What This Unlocks

The "flush on change" pattern — the core of any consecutive-grouping algorithm: extend the current group, flush when the element changes.
Imperative vs functional grouping — the imperative version is explicit about state; the fold version makes the accumulation structure visible.
String building in Rust — `String::push_str`, `format!()`, and `collect::<String>()` are the three ways to build strings incrementally.

Key Differences

Concept	OCaml	Rust
String building	`Buffer.create` + `Buffer.add_string`	`String::push_str` or `collect::<String>()`
Current-group tracking	Mutable `current` + `count` in recursive helper	`last_mut()` on accumulator Vec
Functional grouping	Recursive with accumulator	`fold` building `Vec<(char, usize)>`
Flush last group	Handled at base case of recursion	`chars.last().unwrap()` after loop (imperative) or natural in fold
Type annotation	Inferred	`Vec::<(char, usize)>::new()` often needed for fold

//! # Run-Length Encoding — String Compression
//!
//! Encode consecutive repeated characters as count+char.
//! OCaml uses `Buffer` for incremental string building; Rust uses `String` directly.

// ---------------------------------------------------------------------------
// Approach A: Imperative — iterate with tracking
// ---------------------------------------------------------------------------

pub fn encode(s: &str) -> String {
    if s.is_empty() {
        return String::new();
    }
    let mut result = String::new();
    let chars: Vec<char> = s.chars().collect();
    let mut count = 1;

    for i in 1..chars.len() {
        if chars[i] == chars[i - 1] {
            count += 1;
        } else {
            if count > 1 {
                result.push_str(&count.to_string());
            }
            result.push(chars[i - 1]);
            count = 1;
        }
    }
    if count > 1 {
        result.push_str(&count.to_string());
    }
    result.push(*chars.last().unwrap());
    result
}

// ---------------------------------------------------------------------------
// Approach B: Iterator — chunk_by (nightly) or manual grouping
// ---------------------------------------------------------------------------

pub fn encode_functional(s: &str) -> String {
    if s.is_empty() {
        return String::new();
    }
    let chars: Vec<char> = s.chars().collect();
    let mut groups: Vec<(char, usize)> = vec![];
    for &c in &chars {
        match groups.last_mut() {
            Some((last, count)) if *last == c => *count += 1,
            _ => groups.push((c, 1)),
        }
    }
    groups
        .iter()
        .map(|&(c, n)| {
            if n > 1 {
                format!("{}{}", n, c)
            } else {
                c.to_string()
            }
        })
        .collect()
}

// ---------------------------------------------------------------------------
// Approach C: Fold-based grouping
// ---------------------------------------------------------------------------

pub fn encode_fold(s: &str) -> String {
    s.chars()
        .fold(Vec::<(char, usize)>::new(), |mut acc, c| {
            match acc.last_mut() {
                Some((last, count)) if *last == c => *count += 1,
                _ => acc.push((c, 1)),
            }
            acc
        })
        .iter()
        .map(|&(c, n)| if n > 1 { format!("{}{}", n, c) } else { c.to_string() })
        .collect()
}

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

    #[test]
    fn test_basic() {
        assert_eq!(encode("AABCCCDEEEE"), "2AB3CD4E");
    }

    #[test]
    fn test_no_repeats() {
        assert_eq!(encode("ABCDE"), "ABCDE");
    }

    #[test]
    fn test_all_same() {
        assert_eq!(encode("AAAA"), "4A");
    }

    #[test]
    fn test_empty() {
        assert_eq!(encode(""), "");
    }

    #[test]
    fn test_single() {
        assert_eq!(encode("A"), "A");
    }

    #[test]
    fn test_functional() {
        assert_eq!(encode_functional("AABCCCDEEEE"), "2AB3CD4E");
    }

    #[test]
    fn test_fold() {
        assert_eq!(encode_fold("AABCCCDEEEE"), "2AB3CD4E");
    }
}

fn main() {
    println!("{:?}", encode("AABCCCDEEEE"), "2AB3CD4E");
    println!("{:?}", encode("ABCDE"), "ABCDE");
    println!("{:?}", encode("AAAA"), "4A");
}

let encode s =
  let n = String.length s in
  if n = 0 then "" else
  let buf = Buffer.create n in
  let rec go i c count =
    if i = n then begin
      if count > 1 then Buffer.add_string buf (string_of_int count);
      Buffer.add_char buf c
    end else if s.[i] = c then go (i+1) c (count+1)
    else begin
      if count > 1 then Buffer.add_string buf (string_of_int count);
      Buffer.add_char buf c;
      go (i+1) s.[i] 1
    end
  in
  go 1 s.[0] 1;
  Buffer.contents buf

let () =
  Printf.printf "%s\n" (encode "AABCCCDEEEE")

📊 Detailed Comparison

Comparison: Run-Length Encoding — OCaml vs Rust

Core Insight

Both languages build the result string incrementally. OCaml's `Buffer` module is the explicit choice for this; Rust's `String` is inherently a growable UTF-8 buffer. The recursive vs iterative style differs, but the core algorithm — tracking the current character and its count — is identical.

OCaml

🐪 Show OCaml equivalent

let encode s =
let buf = Buffer.create (String.length s) in
let rec go i c count =
 if i = String.length s then begin
   if count > 1 then Buffer.add_string buf (string_of_int count);
   Buffer.add_char buf c end
 else if s.[i] = c then go (i+1) c (count+1)
 else begin
   if count > 1 then Buffer.add_string buf (string_of_int count);
   Buffer.add_char buf c; go (i+1) s.[i] 1 end
in go 1 s.[0] 1; Buffer.contents buf

Rust — Fold-based

pub fn encode_fold(s: &str) -> String {
 s.chars()
     .fold(Vec::<(char, usize)>::new(), |mut acc, c| {
         match acc.last_mut() {
             Some((last, count)) if *last == c => *count += 1,
             _ => acc.push((c, 1)),
         }; acc
     })
     .iter()
     .map(|&(c, n)| if n > 1 { format!("{n}{c}") } else { c.to_string() })
     .collect()
}

Comparison Table

Aspect	OCaml	Rust
String builder	`Buffer.create n`	`String::new()` / `String::with_capacity`
Char access	`s.[i]`	`chars[i]` after collect
Int to string	`string_of_int count`	`count.to_string()` or `format!`
Grouping	Recursive with acc	`fold` with `last_mut()`
String concat	`Buffer.add_string`	`push_str` / `push`

Learner Notes

`last_mut()`: Rust lets you mutably borrow the last vector element — perfect for accumulating groups
No `chunk_by` in stable: Rust nightly has `slice::chunk_by`, but stable requires manual grouping
`format!` cost: Each `format!("{n}{c}")` allocates; for hot paths, use `write!` into a single `String`
OCaml's Buffer: Similar to Java's `StringBuilder` — explicit mutable string building in an otherwise immutable world