Example 012: Decode Run-Length Encoding

Difficulty: ⭐⭐ Category: Lists, Pattern Matching Concept: The inverse of RLE encoding: expand a compressed representation back into the original list. Demonstrates flat_map/concat_map as the natural tool for one-to-many transformations. OCaml → Rust key insight: OCaml's `List.concat_map` is Rust's `.flat_map()` — both expand each element into zero or more elements and flatten the result.

// Decode Run-Length Encoding — 99 Problems #12
// Expand RLE back to original list

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

fn decode<T: Clone>(lst: &[Rle<T>]) -> Vec<T> {
    lst.iter()
        .flat_map(|item| match item {
            Rle::One(x) => vec![x.clone()],
            Rle::Many(n, x) => vec![x.clone(); *n],
        })
        .collect()
}

/// Tail-recursive style using an iterator accumulator.
fn decode_tr<T: Clone>(lst: &[Rle<T>]) -> Vec<T> {
    let mut result = Vec::new();
    for item in lst {
        match item {
            Rle::One(x) => result.push(x.clone()),
            Rle::Many(n, x) => {
                for _ in 0..*n {
                    result.push(x.clone());
                }
            }
        }
    }
    result
}

fn main() {
    let encoded = vec![
        Rle::Many(4usize, 'a'),
        Rle::One('b'),
        Rle::Many(2, 'c'),
        Rle::Many(2, 'a'),
        Rle::One('d'),
        Rle::Many(4, 'e'),
    ];
    println!("Encoded: {:?}", encoded);
    println!("Decoded: {:?}", decode(&encoded));
    println!("Decoded (tr): {:?}", decode_tr(&encoded));

    let singles = vec![Rle::One('x'), Rle::One('y')];
    println!("Singles decoded: {:?}", decode(&singles));
}

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

    #[test]
    fn test_decode_empty() {
        let empty: Vec<Rle<char>> = vec![];
        assert_eq!(decode(&empty), Vec::<char>::new());
    }

    #[test]
    fn test_decode_singles() {
        let encoded = vec![Rle::One('a'), Rle::One('b')];
        assert_eq!(decode(&encoded), vec!['a', 'b']);
    }

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

    #[test]
    fn test_decode_tr_matches_decode() {
        let encoded = vec![Rle::Many(2, 'x'), Rle::One('y')];
        assert_eq!(decode(&encoded), decode_tr(&encoded));
    }
}

(* Decode Run-Length Encoding — 99 Problems #12 *)

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

(* ── Using List.concat_map (OCaml 4.10+) ────────────────── *)

let decode lst =
  List.concat_map (function
    | One x -> [x]
    | Many (n, x) -> List.init n (fun _ -> x))
  lst

(* ── Recursive with accumulator ──────────────────────────── *)

let decode_recursive lst =
  let rec expand = function
    | One x -> [x]
    | Many (0, _) -> []
    | Many (n, x) -> x :: expand (Many (n - 1, x))
  in
  let rec aux acc = function
    | [] -> List.rev acc
    | item :: rest -> aux (List.rev_append (expand item) acc) rest
  in aux [] lst

(* ── Tail-recursive version ──────────────────────────────── *)

let decode_tr lst =
  let rec aux acc = function
    | [] -> List.rev acc
    | One x :: rest -> aux (x :: acc) rest
    | Many (0, _) :: rest -> aux acc rest
    | Many (n, x) :: rest -> aux (x :: acc) (Many (n - 1, x) :: rest)
  in aux [] lst

(* ── Tests ────────────────────────────────────────────────── *)
let () =
  assert (decode [] = []);
  assert (decode [One 'a'; One 'b'] = ['a'; 'b']);
  assert (decode [Many (3, 'x')] = ['x'; 'x'; 'x']);
  assert (decode [Many (3,'a'); One 'b'; Many (2,'c')] = ['a';'a';'a';'b';'c';'c']);
  assert (decode_recursive [Many (2,'x'); One 'y'] = ['x';'x';'y']);
  assert (decode_tr [Many (3,'a'); One 'b'] = ['a';'a';'a';'b']);
  print_endline "✓ Decode RLE tests passed"

📊 Detailed Comparison

Decode Run-Length Encoding: OCaml vs Rust

The Core Insight

Decoding RLE is a one-to-many expansion: each encoded item produces one or more output elements. This is the natural domain of `flat_map` (Rust) / `concat_map` (OCaml). The problem also shows how algebraic types guide the transformation — each variant has a clear expansion rule.

OCaml Approach

OCaml's `List.concat_map` (4.10+) handles the expansion cleanly:

🐪 Show OCaml equivalent

let decode lst =
List.concat_map (function
 | One x -> [x]
 | Many (n, x) -> List.init n (fun _ -> x))
lst

The recursive version pattern-matches to reduce `Many(n, x)` step by step, prepending x and decrementing n until it reaches zero.

Rust Approach

Rust's `flat_map` combined with `std::iter::repeat` is equally concise:

pub fn decode<T: Clone>(encoded: &[RleItem<T>]) -> Vec<T> {
 encoded.iter().flat_map(|item| match item {
     RleItem::One(x) => vec![x.clone()],
     RleItem::Many(n, x) => vec![x.clone(); *n],
 }).collect()
}

The `vec![val; count]` macro creates n copies, and `flat_map` concatenates all expansions.

Key Differences

Aspect	OCaml	Rust
Expansion	`List.concat_map`	`.flat_map()`
Repeat n times	`List.init n (fun _ -> x)`	`vec![x; n]` or `repeat(x).take(n)`
Pattern matching	`function \	One x -> ... \	Many (n,x) -> ...`	`match item { One(x) => ..., Many(n,x) => ... }`
Cloning	Automatic (GC)	Explicit `.clone()` required
Lazy vs eager	Eager (creates lists)	Lazy until `.collect()`

What Rust Learners Should Notice

`flat_map` is your friend: Whenever you need to produce zero, one, or many items per input, `flat_map` (OCaml: `concat_map`) is the right combinator. It's more general than `map`.
`vec![x; n]` clones: The macro `vec![x.clone(); n]` calls clone n times. For large n with expensive clones, consider `std::iter::repeat_with`.
Iterators compose lazily: Rust's `flat_map` doesn't create intermediate vectors — it yields elements one at a time. The `vec!` inside is allocated, but `repeat().take()` avoids even that.
The recursive approach shows ownership cost: Each recursive step in Rust needs `clone()` calls that OCaml avoids due to GC. This is the explicit trade-off.