Example 013: Direct Run-Length Encoding

Difficulty: ⭐⭐ Category: Lists, Stateful Recursion Concept: Unlike the two-step RLE (pack then count), direct RLE counts consecutive duplicates in a single pass. This tests your ability to carry state through recursion or folds. OCaml → Rust key insight: OCaml's recursive accumulator pattern (`aux count acc = function ...`) translates to Rust's `fold` with mutable accumulator state, or imperative `while` loops — both are idiomatic.

// Direct Run-Length Encoding — 99 Problems #13
// Encode without creating intermediate sublists

#[derive(Debug, PartialEq, Clone)]
enum Rle<T> {
    One(T),
    Many(usize, T),
}

/// Direct single-pass encoding using a fold-like approach.
fn encode<T: PartialEq + Clone>(lst: &[T]) -> Vec<Rle<T>> {
    let mut result: Vec<Rle<T>> = Vec::new();
    for item in lst {
        match result.last_mut() {
            Some(Rle::Many(n, x)) if x == item => *n += 1,
            Some(Rle::One(x)) if x == item => {
                let val = x.clone();
                *result.last_mut().unwrap() = Rle::Many(2, val);
            }
            _ => result.push(Rle::One(item.clone())),
        }
    }
    result
}

/// Fold-based version — explicitly uses fold semantics.
fn encode_fold<T: PartialEq + Clone>(lst: &[T]) -> Vec<Rle<T>> {
    lst.iter().fold(Vec::new(), |mut acc, x| {
        match acc.last_mut() {
            Some(Rle::Many(n, y)) if y == x => *n += 1,
            Some(Rle::One(y)) if y == x => {
                let val = y.clone();
                *acc.last_mut().unwrap() = Rle::Many(2, val);
            }
            _ => acc.push(Rle::One(x.clone())),
        }
        acc
    })
}

fn main() {
    let input = vec!['a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e'];
    println!("Input:      {:?}", input);
    println!("Encoded:    {:?}", encode(&input));
    println!("Fold enc:   {:?}", encode_fold(&input));

    println!("Singles:    {:?}", encode(&['a', 'b', 'c']));
    println!("All-same:   {:?}", encode(&['x', 'x', 'x']));
}

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

    #[test]
    fn test_encode_empty() {
        let empty: Vec<char> = vec![];
        assert_eq!(encode(&empty), vec![]);
    }

    #[test]
    fn test_encode_singles() {
        assert_eq!(
            encode(&['a', 'b', 'c']),
            vec![Rle::One('a'), Rle::One('b'), Rle::One('c')]
        );
    }

    #[test]
    fn test_encode_long() {
        let input = vec!['a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e'];
        assert_eq!(
            encode(&input),
            vec![
                Rle::Many(4, 'a'),
                Rle::One('b'),
                Rle::Many(2, 'c'),
                Rle::Many(2, 'a'),
                Rle::One('d'),
                Rle::Many(4, 'e'),
            ]
        );
    }

    #[test]
    fn test_encode_fold_matches() {
        let input = vec!['a', 'a', 'b'];
        assert_eq!(encode(&input), encode_fold(&input));
    }
}

(* Direct Run-Length Encoding — 99 Problems #13 *)
(* Encode directly without creating intermediate sublists *)

type 'a rle =
  | One of 'a
  | Many of int * 'a

(* ── Direct recursive with counting ──────────────────────── *)

let encode lst =
  let rec aux count acc = function
    | [] -> List.rev acc
    | [x] ->
      let item = if count = 0 then One x else Many (count + 1, x) in
      List.rev (item :: acc)
    | x :: (y :: _ as rest) ->
      if x = y then aux (count + 1) acc rest
      else
        let item = if count = 0 then One x else Many (count + 1, x) in
        aux 0 (item :: acc) rest
  in aux 0 [] lst

(* ── Fold-based approach ─────────────────────────────────── *)

let encode_fold lst =
  let update acc x =
    match acc with
    | Many (n, y) :: rest when y = x -> Many (n + 1, y) :: rest
    | One y :: rest when y = x -> Many (2, y) :: rest
    | _ -> One x :: acc
  in
  List.fold_left update [] lst |> List.rev

(* ── Tests ────────────────────────────────────────────────── *)
let () =
  assert (encode [] = []);
  assert (encode ['a';'b';'c'] = [One 'a'; One 'b'; One 'c']);
  assert (encode ['a';'a';'a';'a';'b';'c';'c';'a';'a';'d';'e';'e';'e';'e']
    = [Many (4,'a'); One 'b'; Many (2,'c'); Many (2,'a'); One 'd'; Many (4,'e')]);
  assert (encode_fold ['a';'a';'b'] = [Many (2,'a'); One 'b']);
  print_endline "✓ Direct RLE tests passed"

📊 Detailed Comparison

Direct Run-Length Encoding: OCaml vs Rust

The Core Insight

Direct RLE eliminates the intermediate step of grouping — it counts runs on the fly. This requires carrying mutable state (the current count) through traversal. OCaml does this with recursive accumulators; Rust offers both fold-based and imperative approaches, with the fold version being particularly interesting because it mutates the accumulator in place.

OCaml Approach

The recursive version carries a `count` alongside the accumulator:

🐪 Show OCaml equivalent

let rec aux count acc = function
| [] -> List.rev acc
| [x] -> List.rev ((if count = 0 then One x else Many (count+1, x)) :: acc)
| x :: (y :: _ as rest) ->
 if x = y then aux (count+1) acc rest
 else let item = if count = 0 then One x else Many (count+1, x) in
      aux 0 (item :: acc) rest

The fold version builds the result in reverse, checking the head of the accumulator to extend the current run.

Rust Approach

Rust's fold approach modifies the last element of the accumulator in place:

list.iter().fold(Vec::new(), |mut acc, x| {
 match acc.last_mut() {
     Some(RleItem::Many(n, ref y)) if y == x => { *n += 1; }
     Some(RleItem::One(ref y)) if y == x => {
         *acc.last_mut().unwrap() = RleItem::Many(2, y.clone());
     }
     _ => acc.push(RleItem::One(x.clone())),
 }
 acc
})

The `last_mut()` method gives a mutable reference to the last element — a pattern impossible in pure functional OCaml but natural in Rust.

Key Differences

Aspect	OCaml	Rust
State threading	Explicit parameters (`count`, `acc`)	`fold` with mutable accumulator
Mutation	Never (new list nodes)	In-place via `last_mut()`
Peeking ahead	`x :: (y :: _ as rest)` pattern	`tail.first()` or index comparison
Reverse at end	`List.rev acc` (common pattern)	Not needed (push appends)
Two-element look-ahead	Native with pattern matching	Requires explicit index logic

What Rust Learners Should Notice

`last_mut()` enables accumulator mutation: Rust's ownership system lets you mutate the last element of a Vec through a mutable reference — something OCaml can't do with immutable lists.
OCaml's two-element pattern is cleaner: `x :: (y :: _ as rest)` naturally looks at two elements. Rust requires comparing `list[i]` with `list[i-1]` or using `windows(2)`.
Both approaches are O(n): The algorithmic complexity is identical. The difference is stylistic — OCaml's recursive version is more declarative, Rust's fold version is more imperative.
Direct encoding avoids allocation: Both languages benefit from not creating intermediate sublists, making this more memory-efficient than the two-step approach.