012 Intermediate

012 — Decode Run-Length Encoding

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "012 — Decode Run-Length Encoding" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Decoding run-length encoding (OCaml 99 Problems #12) is the inverse of encoding: given a sequence of `(count, element)` or `element` items, reconstruct the original uncompressed sequence. Key difference from OCaml: 1. **`flat_map` naming**: Rust calls it `flat_map`, OCaml calls it `concat_map` (stdlib 4.10+) or implements it as `List.flatten (List.map f lst)`. Both mean the same operation: map then flatten one level.

Tutorial

The Problem

Decoding run-length encoding (OCaml 99 Problems #12) is the inverse of encoding: given a sequence of (count, element) or element items, reconstruct the original uncompressed sequence. This is the decompression side of a codec — used in fax machines (CCITT T.4), BMP images, PCX format, and simple network protocols.

Decoding exercises flat_map: each encoded item expands into zero or more output elements. flat_map (also called concat_map in OCaml) is the fundamental operation for structure-expanding transformations. It generalizes map by allowing each input to produce multiple outputs, and it is the monadic bind operation for lists.

🎯 Learning Outcomes

• Use flat_map to expand encoded items into multiple output elements

• Use std::iter::repeat(x).take(n) to generate n copies of a value

• Understand flat_map as monadic bind for Vec/iterators

• Compare eager (flat_map + collect) vs recursive decoding approaches

• Recognize the encode/decode round-trip invariant for testing

• Use std::iter::repeat(x).take(n) to generate n copies of a value lazily without allocation

• Verify the encode-decode round-trip invariant: decode(encode(list)) == list

Code Example

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()
}

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

Key Differences

**flat_map naming**: Rust calls it flat_map, OCaml calls it concat_map (stdlib 4.10+) or implements it as List.flatten (List.map f lst). Both mean the same operation: map then flatten one level.

**repeat vs List.init**: Rust's std::iter::repeat(x).take(n) is more direct than OCaml's List.init n (fun _ -> x). Both produce n copies without mutation.

Clone requirement: Rust needs T: Clone to produce multiple copies from a reference. OCaml's GC allows sharing the same value across all copies without cloning.

Laziness: Rust's flat_map(...).collect() is lazy until collect. OCaml's List.concat_map is eager — it builds the full list immediately.

**flat_map as monadic bind:** flat_map on iterators is the iterator monad's bind operation. v.flat_map(f) = v.map(f).flatten(). OCaml's equivalent: List.concat_map f l (OCaml 4.10+) or List.concat (List.map f l).

**repeat + take:** std::iter::repeat(x).take(n) is idiomatic Rust for generating n copies. OCaml: List.init n (fun _ -> x). Both are O(n).

Owned vs borrowed: decode borrows the encoded slice; it must clone values into the output Vec. OCaml shares values via GC — no cloning needed for the typical case.

Round-trip invariant: decode(encode(list)) == list for any list. This is a strong property test that should be verified with proptest or quickcheck.

OCaml Approach

OCaml's decode uses List.concat_map (or List.flatten (List.map f lst)). The typical implementation is: let decode lst = List.concat_map (function One x -> [x] | Many (n, x) -> List.init n (fun _ -> x)) lst. List.init n f creates a list of length n by calling f with indices 0 to n-1. The recursive approach matches on the head and expands it before processing the tail.

Full Source

#![allow(clippy::all)]
/// Decode Run-Length Encoding (99 Problems #12)
///
/// Given a modified RLE list, reconstruct the original list by expanding
/// `Many(n, x)` into n copies of x and keeping `One(x)` as-is.

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

// ── Idiomatic Rust: flat_map with repeat ────────────────────────────────────

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()
}

// ── Iterator-based with std::iter::repeat ───────────────────────────────────

pub fn decode_iter<T: Clone>(encoded: &[RleItem<T>]) -> Vec<T> {
    encoded
        .iter()
        .flat_map(|item| {
            let (count, value) = match item {
                RleItem::One(x) => (1, x),
                RleItem::Many(n, x) => (*n, x),
            };
            std::iter::repeat(value.clone()).take(count)
        })
        .collect()
}

// ── Recursive style ─────────────────────────────────────────────────────────

pub fn decode_recursive<T: Clone>(encoded: &[RleItem<T>]) -> Vec<T> {
    fn expand<T: Clone>(item: &RleItem<T>) -> Vec<T> {
        match item {
            RleItem::One(x) => vec![x.clone()],
            RleItem::Many(n, x) => {
                // Recursive expansion (functional style)
                if *n == 0 {
                    vec![]
                } else {
                    let mut rest = expand(&RleItem::Many(n - 1, x.clone()));
                    rest.insert(0, x.clone());
                    rest
                }
            }
        }
    }

    match encoded.split_first() {
        None => vec![],
        Some((head, tail)) => {
            let mut result = expand(head);
            result.extend(decode_recursive(tail));
            result
        }
    }
}

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

    #[test]
    fn test_empty() {
        assert_eq!(decode::<char>(&[]), vec![]);
    }

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

    #[test]
    fn test_all_runs() {
        let encoded = vec![Many(3, 'x'), Many(2, 'y')];
        assert_eq!(decode(&encoded), vec!['x', 'x', 'x', 'y', 'y']);
    }

    #[test]
    fn test_mixed() {
        let encoded = vec![Many(3, 'a'), One('b'), Many(2, 'c'), Many(4, 'd')];
        let expected = vec!['a', 'a', 'a', 'b', 'c', 'c', 'd', 'd', 'd', 'd'];
        assert_eq!(decode(&encoded), expected);
        assert_eq!(decode_iter(&encoded), expected);
        assert_eq!(decode_recursive(&encoded), expected);
    }

    #[test]
    fn test_single_item() {
        assert_eq!(decode(&[One(42)]), vec![42]);
        assert_eq!(decode(&[Many(1, 42)]), vec![42]);
    }

    #[test]
    fn test_roundtrip_property() {
        // Encode then decode should give back the original (for valid inputs)
        let original = vec![1, 1, 1, 2, 3, 3];
        let encoded = vec![Many(3, 1), One(2), Many(2, 3)];
        assert_eq!(decode(&encoded), original);
    }
}

(* 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"

✓ Tests Rust test suite

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

    #[test]
    fn test_empty() {
        assert_eq!(decode::<char>(&[]), vec![]);
    }

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

    #[test]
    fn test_all_runs() {
        let encoded = vec![Many(3, 'x'), Many(2, 'y')];
        assert_eq!(decode(&encoded), vec!['x', 'x', 'x', 'y', 'y']);
    }

    #[test]
    fn test_mixed() {
        let encoded = vec![Many(3, 'a'), One('b'), Many(2, 'c'), Many(4, 'd')];
        let expected = vec!['a', 'a', 'a', 'b', 'c', 'c', 'd', 'd', 'd', 'd'];
        assert_eq!(decode(&encoded), expected);
        assert_eq!(decode_iter(&encoded), expected);
        assert_eq!(decode_recursive(&encoded), expected);
    }

    #[test]
    fn test_single_item() {
        assert_eq!(decode(&[One(42)]), vec![42]);
        assert_eq!(decode(&[Many(1, 42)]), vec![42]);
    }

    #[test]
    fn test_roundtrip_property() {
        // Encode then decode should give back the original (for valid inputs)
        let original = vec![1, 1, 1, 2, 3, 3];
        let encoded = vec![Many(3, 1), One(2), Many(2, 3)];
        assert_eq!(decode(&encoded), original);
    }
}

Deep 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:

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.

Exercises

Round-trip test: Write a property-based test that generates random Vec<char> inputs, encodes them with encode_modified from example 011, decodes with decode, and asserts equality.

Streaming decode: Rewrite decode to accept impl Iterator<Item=RleItem<T>> and return impl Iterator<Item=T> without collecting to Vec at any step. Use flat_map on the input iterator.

RLE of RLE: What happens when you RLE-encode an already-encoded RLE sequence? Write a function that detects whether further compression is beneficial.

Streaming decode: Implement a version that returns an impl Iterator<Item = T> instead of Vec<T> — allowing the decoded stream to be consumed lazily without allocating the full output.

Bidirectional codec: Write encode (from Vec<T> to Vec<RleItem<T>>) and decode (inverse), then verify that decode(encode(v)) == v for arbitrary inputs using a property test.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust

Tutorial Video

Tutorial

The Problem

🎯 Learning Outcomes

Code Example

Key Differences

OCaml Approach

Full Source

Deep Comparison

Decode Run-Length Encoding: OCaml vs Rust

The Core Insight

OCaml Approach

Rust Approach

Key Differences

What Rust Learners Should Notice

Further Reading

Exercises

Open Source Repos