008 Fundamental

Eliminate Consecutive Duplicates

ListsHigher-Order Functions

Tutorial Video

Text description (accessibility)

This video demonstrates the "Eliminate Consecutive Duplicates" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Lists, Higher-Order Functions. Eliminate consecutive duplicate elements from a list. Key difference from OCaml: 1. **Mutation is explicit**: `dedup()` requires `&mut Vec<T>` — you can't accidentally mutate in Rust

Tutorial

The Problem

Eliminate consecutive duplicate elements from a list. Only remove duplicates that are adjacent — non-adjacent duplicates remain.

Removing consecutive duplicates is the decompression step for run-length encoding. It also appears in log deduplication (suppress duplicate consecutive log messages), text compression preprocessing, and clean-up of sensor data with stuck values. The key constraint — only consecutive duplicates are removed — makes this fundamentally different from removing all duplicates (which requires a HashSet). Run-length decoding produces this exact output.

🎯 Learning Outcomes

• Use dedup() for in-place mutation vs building a new collection

• Understand windows(2) for pairwise element comparison

• See how Rust's ownership model makes the mutation/immutation choice explicit

• Practice the fold pattern for building filtered results

• Compare OCaml's pattern matching on cons cells with Rust's slice patterns

🦀 The Rust Way

Mutable: Vec::dedup() — in-place, O(n), modifies the vector directly

Functional: Iterate with a result accumulator, comparing last() element

Windows: Use windows(2) to compare pairs, filter where different, collect

Code Example

pub fn compress_mut<T: PartialEq>(list: &mut Vec<T>) {
    list.dedup();
}

let rec compress = function
  | [] -> []
  | [x] -> [x]
  | h1 :: (h2 :: _ as t) ->
      if h1 = h2 then compress t
      else h1 :: compress t

Key Differences

Mutation is explicit: dedup() requires &mut Vec<T> — you can't accidentally mutate in Rust

No cons cells: Rust doesn't have linked-list pattern matching; slices and iterators fill that role

**windows(2) is unique to Rust**: Efficient pairwise comparison over contiguous memory

Trait bounds: Rust needs PartialEq explicitly; OCaml uses polymorphic equality

In-place vs functional: Rust naturally offers both; OCaml is functional-first (no in-place dedup on lists)

Mutation vs immutable: Rust's dedup() mutates in place. OCaml lists are immutable — compress always builds a new list.

**PartialEq vs structural equality:** Rust's dedup uses PartialEq for comparison. OCaml uses structural equality (=) by default, which works for most types.

**windows(2):** Rust's sliding-window iterator has no built-in OCaml equivalent — it's possible only on contiguous memory (slices/arrays), not linked lists.

Single pass: All three Rust implementations are single-pass O(n). OCaml's recursive version is also single-pass — it compares the head with the next element.

OCaml Approach

Pattern matches on the list head, comparing consecutive elements. When h1 = h2, skips the duplicate and recurses on the tail. Builds a new list (old one is GC'd).

Full Source

#![allow(clippy::all)]
//! # Eliminate Consecutive Duplicates
//! OCaml 99 Problems #8 — Remove consecutive duplicate elements from a list.

/// Idiomatic Rust: use `dedup` on a mutable Vec (in-place, O(n)).
/// This modifies the vector — Rust's ownership model makes mutation explicit.
pub fn compress_mut<T: PartialEq>(list: &mut Vec<T>) {
    list.dedup();
}

/// Functional style: build a new Vec by filtering consecutive duplicates.
/// Mirrors the OCaml recursive approach but uses iterators.
pub fn compress<T: PartialEq + Clone>(list: &[T]) -> Vec<T> {
    if list.is_empty() {
        return vec![];
    }
    let mut result = vec![list[0].clone()];
    for item in &list[1..] {
        if result.last() != Some(item) {
            result.push(item.clone());
        }
    }
    result
}

/// Iterator-based with windows — the most declarative approach.
/// Uses `windows(2)` to compare adjacent pairs.
pub fn compress_iter<T: PartialEq + Clone>(list: &[T]) -> Vec<T> {
    if list.is_empty() {
        return vec![];
    }
    let mut result: Vec<T> = list
        .windows(2)
        .filter(|w| w[0] != w[1])
        .map(|w| w[0].clone())
        .collect();
    // Always include the last element
    if let Some(last) = list.last() {
        result.push(last.clone());
    }
    result
}

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

    #[test]
    fn test_consecutive_duplicates() {
        let input = vec!["a", "a", "a", "b", "c", "c", "d", "e", "e", "e"];
        assert_eq!(compress(&input), vec!["a", "b", "c", "d", "e"]);
        assert_eq!(compress_iter(&input), vec!["a", "b", "c", "d", "e"]);
    }

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

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

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

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

    #[test]
    fn test_mut_version() {
        let mut v = vec![1, 1, 2, 2, 3];
        compress_mut(&mut v);
        assert_eq!(v, vec![1, 2, 3]);
    }
}

(* Eliminate Duplicates *)
(* OCaml 99 Problems #8 *)

(* Eliminate consecutive duplicates *)
let rec compress = function
  | [] -> []
  | [x] -> [x]
  | h1 :: (h2 :: _ as t) ->
      if h1 = h2 then compress t
      else h1 :: compress t

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

✓ Tests Rust test suite

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

    #[test]
    fn test_consecutive_duplicates() {
        let input = vec!["a", "a", "a", "b", "c", "c", "d", "e", "e", "e"];
        assert_eq!(compress(&input), vec!["a", "b", "c", "d", "e"]);
        assert_eq!(compress_iter(&input), vec!["a", "b", "c", "d", "e"]);
    }

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

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

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

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

    #[test]
    fn test_mut_version() {
        let mut v = vec![1, 1, 2, 2, 3];
        compress_mut(&mut v);
        assert_eq!(v, vec![1, 2, 3]);
    }
}

Deep Comparison

Comparison: Eliminate Consecutive Duplicates

OCaml — Pattern matching

let rec compress = function
  | [] -> []
  | [x] -> [x]
  | h1 :: (h2 :: _ as t) ->
      if h1 = h2 then compress t
      else h1 :: compress t

Rust — Idiomatic (in-place mutation)

pub fn compress_mut<T: PartialEq>(list: &mut Vec<T>) {
    list.dedup();
}

Rust — Functional (accumulator)

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

Comparison Table

Aspect	OCaml	Rust
Pattern	`h1 :: h2 :: _` (cons cell)	`&list[1..]` (slice)
Mutation	Not available on lists	`Vec::dedup()` in-place
Return	New list (GC frees old)	New `Vec` or mutate existing
Equality	`=` (polymorphic)	`PartialEq` trait
Edge cases	Pattern match `[]`, `[x]`	`is_empty()` check

Takeaways

Rust's dedup() is a one-liner for the imperative approach — stdlib is batteries-included

OCaml's pattern matching on cons cells is more elegant for list algorithms

The windows(2) approach has no OCaml equivalent — it leverages contiguous memory layout

Mutation in Rust is always a conscious choice (&mut), never accidental

Both languages handle edge cases (empty, single-element) but Rust uses conditionals where OCaml uses pattern arms

Exercises

Implement deduplicate_all (not just consecutive) — remove every duplicate from a list, keeping only the first occurrence of each element.

Write deduplicate_by that removes consecutive duplicates using a key function f: &T -> K for comparison, so you can deduplicate case-insensitively or by a struct field.

Implement run_length_from_dedup that uses eliminate_consecutive as a building block to produce run-length encoding in a single pipeline (no extra passes).

Open Source Repos

functional-rust

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

Rust