Example 011: Modified Run-Length Encoding

Difficulty: ⭐⭐ Category: Lists, Pattern Matching, Algebraic Data Types Concept: Modify standard RLE so that singletons are represented differently from runs. This requires a sum type (OCaml variant / Rust enum) to distinguish the two cases — a natural use of algebraic data types. OCaml → Rust key insight: OCaml's `type 'a rle = One of 'a | Many of int * 'a` maps directly to Rust's `enum RleItem<T> { One(T), Many(usize, T) }`.

// Modified Run-Length Encoding — 99 Problems #11
// Single elements stay unwrapped (One), runs get (count, elem) (Many)

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

/// Pack consecutive duplicates into groups, then encode.
fn pack<T: PartialEq + Clone>(lst: &[T]) -> Vec<Vec<T>> {
    let mut result: Vec<Vec<T>> = Vec::new();
    for item in lst {
        match result.last_mut() {
            Some(group) if group.last() == Some(item) => group.push(item.clone()),
            _ => result.push(vec![item.clone()]),
        }
    }
    result
}

fn encode<T: PartialEq + Clone>(lst: &[T]) -> Vec<Rle<T>> {
    pack(lst)
        .into_iter()
        .map(|group| {
            if group.len() == 1 {
                Rle::One(group.into_iter().next().unwrap())
            } else {
                let len = group.len();
                Rle::Many(len, group.into_iter().next().unwrap())
            }
        })
        .collect()
}

/// Direct recursive version without intermediate pack step.
fn encode_direct<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 x = x.clone();
                *result.last_mut().unwrap() = Rle::Many(2, x);
            }
            _ => result.push(Rle::One(item.clone())),
        }
    }
    result
}

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

    let direct = encode_direct(&input);
    println!("Direct:  {:?}", direct);

    let singles = vec!['a', 'b', 'c'];
    println!("Singles: {:?}", encode(&singles));
}

#[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_all_single() {
        assert_eq!(
            encode(&['a', 'b', 'c']),
            vec![Rle::One('a'), Rle::One('b'), Rle::One('c')]
        );
    }

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

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

(* Modified Run-Length Encoding — 99 Problems #11 *)
(* Single elements stay unwrapped, runs get (count, elem) *)

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

(* ── Pack consecutive duplicates into sublists ───────────── *)

let pack lst =
  let rec aux current acc = function
    | [] -> List.rev (current :: acc)
    | x :: rest ->
      match current with
      | [] -> aux [x] acc rest
      | y :: _ when x = y -> aux (x :: current) acc rest
      | _ -> aux [x] (current :: acc) rest
  in match lst with
  | [] -> []
  | h :: t -> aux [h] [] t

(* ── Modified RLE using pack ─────────────────────────────── *)

let encode lst =
  pack lst
  |> List.map (fun group ->
       match group with
       | [x] -> One x
       | x :: _ -> Many (List.length group, x)
       | [] -> failwith "impossible")

(* ── Direct recursive version ────────────────────────────── *)

let encode_direct lst =
  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
  in aux 0 [] lst

(* ── Tests ────────────────────────────────────────────────── *)
let () =
  assert (encode [] = []);
  assert (encode ['a';'b';'c'] = [One 'a'; One 'b'; One 'c']);
  assert (encode ['x';'x';'x'] = [Many (3, 'x')]);
  assert (encode ['a';'a';'a';'b';'c';'c'] = [Many (3,'a'); One 'b'; Many (2,'c')]);
  assert (encode_direct ['a';'a';'b';'c';'c';'c'] = [Many (2,'a'); One 'b'; Many (3,'c')]);
  print_endline "✓ Modified RLE tests passed"

📊 Detailed Comparison

Modified Run-Length Encoding: OCaml vs Rust

The Core Insight

This problem naturally requires a sum type to represent two kinds of elements: singles and runs. Both OCaml and Rust make this elegant with algebraic data types. The interesting part is how each language handles the stateful traversal — accumulating runs of equal elements while distinguishing singletons.

OCaml Approach

OCaml defines a parameterized variant type and uses pattern matching with accumulators:

🐪 Show OCaml equivalent

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

let encode lst =
pack lst |> List.map (fun group ->
 match group with
 | [x] -> One x
 | x :: _ -> Many (List.length group, x)
 | [] -> failwith "impossible")

The `pack` helper groups consecutive duplicates into sublists first, then `encode` classifies each group. The direct version tracks count in a recursive accumulator.

Rust Approach

Rust uses a generic enum with the same structure:

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

The idiomatic approach uses index-based iteration with equality checks. The recursive version uses `split_first()` or position-finding to identify runs. Both require `Clone` because Rust can't share data implicitly.

Key Differences

Aspect	OCaml	Rust
Sum type	`type 'a rle = One of 'a \	Many of int * 'a`	`enum RleItem<T> { One(T), Many(usize, T) }`
Type parameter	`'a` (implicit)	`<T: PartialEq + Clone>` (explicit bounds)
Equality	Structural (built-in)	Requires `PartialEq` trait
Copying	Automatic (GC)	Requires `Clone`
Grouping	`pack` into sublists, then map	Direct counting (no intermediate lists)
Pattern matching	`[x]` matches singleton list	No slice literal patterns in stable
Performance	O(n) with intermediate allocations	O(n) single pass possible

What Rust Learners Should Notice

Trait bounds are explicit: Where OCaml uses structural equality by default, Rust requires `PartialEq` to compare elements. This makes the contract visible.
Clone is the cost of ownership: OCaml freely copies values (GC handles it). Rust requires `Clone` when you want to put a value into an enum variant while still traversing the original slice.
No list pattern matching on slices: OCaml's `[x]` and `x :: rest` patterns don't exist for Rust slices (stable). You use `split_first()`, `.len()`, or index-based patterns instead.
Enums are the same concept: The translation from OCaml variant to Rust enum is nearly mechanical — add `#[derive]` for common traits, add trait bounds for generics.