009 Intermediate

Pack Consecutive Duplicates

ListsGrouping

Tutorial Video

Text description (accessibility)

This video demonstrates the "Pack Consecutive Duplicates" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Lists, Grouping. Pack consecutive duplicate elements into sublists. Key difference from OCaml: 1. **Slice references**: `pack_slices` returns `&[T]` views — no data copied, impossible in OCaml's GC model

Tutorial

The Problem

Pack consecutive duplicate elements into sublists.

Packing consecutive duplicates is the run detection step of run-length encoding, tokenizers, and sequence analysis. Every compression algorithm starts by identifying runs. In bioinformatics, packing consecutive identical nucleotides is a preprocessing step for genome compression. In network protocols, packing repeated bytes enables efficient transmission. This problem is a concrete introduction to stateful accumulation — maintaining "current group" as you scan.

🎯 Learning Outcomes

• Build nested data structures (Vec<Vec<T>>) from flat input

• Use fold for stateful accumulation — the functional alternative to loops

• Understand zero-copy grouping with slice references (&[T])

• Compare OCaml's accumulator-based recursion with Rust's imperative and fold styles

• See how borrowing enables efficient grouping without cloning

🦀 The Rust Way

Imperative: Iterate with a mutable current group and result vector

Fold: fold() with last_mut() to extend or create groups — closest to OCaml's accumulator

Slice-based: Returns Vec<&[T]> — borrows into the original slice, zero copying

Code Example

pub fn pack<T: PartialEq + Clone>(list: &[T]) -> Vec<Vec<T>> {
    if list.is_empty() { return vec![]; }
    let mut result = Vec::new();
    let mut current = vec![list[0].clone()];
    for item in &list[1..] {
        if *item == current[0] {
            current.push(item.clone());
        } else {
            result.push(current);
            current = vec![item.clone()];
        }
    }
    result.push(current);
    result
}

let pack lst =
  let rec aux current acc = function
    | [] -> []
    | [x] -> (x :: current) :: acc
    | h1 :: (h2 :: _ as t) ->
        if h1 = h2 then aux (h1 :: current) acc t
        else aux [] ((h1 :: current) :: acc) t
  in
  List.rev (aux [] [] lst)

Key Differences

Slice references: pack_slices returns &[T] views — no data copied, impossible in OCaml's GC model

**last_mut()**: Rust can mutate the last element of a Vec through a mutable reference — efficient for the fold pattern

Ownership spectrum: Three levels offered — owned + cloned, owned + fold, borrowed slices

**No List.rev needed**: Rust's Vec::push appends to the end (O(1) amortized); OCaml prepends to lists and reverses

Memory layout: Rust's Vec<Vec<T>> is contiguous blocks; OCaml's 'a list list is chains of cons cells

Mutable accumulator: Rust's imperative version uses a current group and result accumulator explicitly. OCaml's version uses two accumulators in a tail-recursive helper, but the logic is the same.

Nested Vec: Vec<Vec<T>> in Rust requires two levels of allocation. OCaml's 'a list list uses linked lists at both levels — cheaper to prepend to, but more GC pressure.

Clone at boundaries: When a run ends, Rust clones elements into the new group via item.clone(). OCaml's GC shares values automatically.

Empty input: Both implementations return []/vec![] for empty input as a base case.

OCaml Approach

Uses a tail-recursive helper with two accumulators: current (current group) and acc (completed groups). Compares consecutive elements and either extends the current group or starts a new one. Returns reversed result.

Full Source

#![allow(clippy::all)]
//! # Pack Consecutive Duplicates
//! OCaml 99 Problems #9 — Pack consecutive duplicates into sublists.

/// Idiomatic Rust: imperative with explicit groups.
/// Slice-based input, returns owned Vec<Vec<T>>.
pub fn pack<T: PartialEq + Clone>(list: &[T]) -> Vec<Vec<T>> {
    if list.is_empty() {
        return vec![];
    }
    let mut result = Vec::new();
    let mut current = vec![list[0].clone()];
    for item in &list[1..] {
        if *item == current[0] {
            current.push(item.clone());
        } else {
            result.push(current);
            current = vec![item.clone()];
        }
    }
    result.push(current);
    result
}

/// Functional style: fold-based, mirrors the OCaml accumulator pattern.
pub fn pack_fold<T: PartialEq + Clone>(list: &[T]) -> Vec<Vec<T>> {
    list.iter().fold(Vec::new(), |mut acc: Vec<Vec<T>>, item| {
        match acc.last_mut() {
            Some(group) if group[0] == *item => {
                group.push(item.clone());
            }
            _ => {
                acc.push(vec![item.clone()]);
            }
        }
        acc
    })
}

/// Slice-based: returns groups as index ranges (zero-copy where possible).
/// Most efficient — avoids cloning entirely, returns `&[T]` slices.
pub fn pack_slices<T: PartialEq>(list: &[T]) -> Vec<&[T]> {
    if list.is_empty() {
        return vec![];
    }
    let mut result = Vec::new();
    let mut start = 0;
    for i in 1..list.len() {
        if list[i] != list[start] {
            result.push(&list[start..i]);
            start = i;
        }
    }
    result.push(&list[start..]);
    result
}

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

    #[test]
    fn test_pack() {
        let input = vec!["a", "a", "b", "c", "c", "c"];
        let expected = vec![vec!["a", "a"], vec!["b"], vec!["c", "c", "c"]];
        assert_eq!(pack(&input), expected);
        assert_eq!(pack_fold(&input), expected);
    }

    #[test]
    fn test_empty() {
        assert_eq!(pack::<i32>(&[]), Vec::<Vec<i32>>::new());
        assert_eq!(pack_fold::<i32>(&[]), Vec::<Vec<i32>>::new());
        assert_eq!(pack_slices::<i32>(&[]), Vec::<&[i32]>::new());
    }

    #[test]
    fn test_single() {
        assert_eq!(pack(&[1]), vec![vec![1]]);
        assert_eq!(pack_fold(&[1]), vec![vec![1]]);
    }

    #[test]
    fn test_no_duplicates() {
        assert_eq!(pack(&[1, 2, 3]), vec![vec![1], vec![2], vec![3]]);
    }

    #[test]
    fn test_all_same() {
        assert_eq!(pack(&[5, 5, 5]), vec![vec![5, 5, 5]]);
    }

    #[test]
    fn test_slices() {
        let input = [1, 1, 2, 3, 3];
        let result = pack_slices(&input);
        assert_eq!(result, vec![&[1, 1][..], &[2][..], &[3, 3][..]]);
    }
}

(* Pack Consecutive *)
(* OCaml 99 Problems #9 *)

(* Pack consecutive duplicates *)
let pack lst =
  let rec aux current acc = function
    | [] -> []
    | [x] -> (x :: current) :: acc
    | h1 :: (h2 :: _ as t) ->
        if h1 = h2 then aux (h1 :: current) acc t
        else aux [] ((h1 :: current) :: acc) t
  in
  List.rev (aux [] [] lst)

(* Tests *)
let () =
  assert (pack ["a";"a";"b";"c";"c";"c"] = [["a";"a"];["b"];["c";"c";"c"]]);
  assert (pack [] = []);
  assert (pack [1] = [[1]]);
  print_endline "✓ OCaml tests passed"

✓ Tests Rust test suite

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

    #[test]
    fn test_pack() {
        let input = vec!["a", "a", "b", "c", "c", "c"];
        let expected = vec![vec!["a", "a"], vec!["b"], vec!["c", "c", "c"]];
        assert_eq!(pack(&input), expected);
        assert_eq!(pack_fold(&input), expected);
    }

    #[test]
    fn test_empty() {
        assert_eq!(pack::<i32>(&[]), Vec::<Vec<i32>>::new());
        assert_eq!(pack_fold::<i32>(&[]), Vec::<Vec<i32>>::new());
        assert_eq!(pack_slices::<i32>(&[]), Vec::<&[i32]>::new());
    }

    #[test]
    fn test_single() {
        assert_eq!(pack(&[1]), vec![vec![1]]);
        assert_eq!(pack_fold(&[1]), vec![vec![1]]);
    }

    #[test]
    fn test_no_duplicates() {
        assert_eq!(pack(&[1, 2, 3]), vec![vec![1], vec![2], vec![3]]);
    }

    #[test]
    fn test_all_same() {
        assert_eq!(pack(&[5, 5, 5]), vec![vec![5, 5, 5]]);
    }

    #[test]
    fn test_slices() {
        let input = [1, 1, 2, 3, 3];
        let result = pack_slices(&input);
        assert_eq!(result, vec![&[1, 1][..], &[2][..], &[3, 3][..]]);
    }
}

Deep Comparison

Comparison: Pack Consecutive Duplicates

OCaml — Accumulator recursion

let pack lst =
  let rec aux current acc = function
    | [] -> []
    | [x] -> (x :: current) :: acc
    | h1 :: (h2 :: _ as t) ->
        if h1 = h2 then aux (h1 :: current) acc t
        else aux [] ((h1 :: current) :: acc) t
  in
  List.rev (aux [] [] lst)

Rust — Idiomatic (imperative)

pub fn pack<T: PartialEq + Clone>(list: &[T]) -> Vec<Vec<T>> {
    if list.is_empty() { return vec![]; }
    let mut result = Vec::new();
    let mut current = vec![list[0].clone()];
    for item in &list[1..] {
        if *item == current[0] {
            current.push(item.clone());
        } else {
            result.push(current);
            current = vec![item.clone()];
        }
    }
    result.push(current);
    result
}

Rust — Functional (fold)

pub fn pack_fold<T: PartialEq + Clone>(list: &[T]) -> Vec<Vec<T>> {
    list.iter().fold(Vec::new(), |mut acc, item| {
        match acc.last_mut() {
            Some(group) if group[0] == *item => group.push(item.clone()),
            _ => acc.push(vec![item.clone()]),
        }
        acc
    })
}

Comparison Table

Aspect	OCaml	Rust
Accumulator	Two: `current` + `acc`	One: `Vec<Vec<T>>` with `last_mut()`
List building	Prepend + reverse	Append (amortized O(1))
Zero-copy	Not possible	`pack_slices` returns `&[T]`
Pattern matching	`h1 :: (h2 :: _ as t)`	Iterator + conditional
Empty handling	Pattern match `[]`	Early return on `is_empty()`

Takeaways

Rust's last_mut() enables elegant fold-based grouping without OCaml's double-accumulator pattern

The slice-based version (pack_slices) showcases Rust's borrowing — zero-copy grouping

Vec::push appending eliminates the List.rev step needed in OCaml

Both languages use the same core algorithm — iterate and group — but express it differently

The ownership choice (clone vs borrow) is explicit in Rust, invisible in OCaml

Exercises

Implement pack_by — a variant that groups consecutive elements using a key function f: &T -> K instead of direct equality.

Write pack_into_counts that converts a packed list into a list of (usize, T) pairs representing run lengths, using your pack function as a building block.

Implement unpack — the inverse: given a list of (usize, T) pairs, produce the original expanded list.

Open Source Repos

functional-rust

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

Rust