008: Eliminate Consecutive Duplicates

Difficulty: ⭐ Level: Beginner Remove repeated adjacent elements from a list, keeping one of each run.

The Problem This Solves

You have a sequence with repeated runs: `["a", "a", "a", "b", "c", "c", "d", "e", "e"]`. You want: `["a", "b", "c", "d", "e"]`. This comes up in log deduplication, compressing repeated sensor readings, processing run-length encoded data, or collapsing repeated keypresses. Note the "consecutive" qualifier: only adjacent duplicates are removed. `["a", "b", "a"]` stays as-is — the two `"a"`s are not adjacent. If you want to remove all duplicates regardless of position, that's a different problem (use a `HashSet`). The loop-based approach is straightforward but wordy: track the "last seen" element, compare, conditionally push. Rust offers two cleaner paths: a one-liner for in-place mutation, and a functional version for when you need a new collection.

The Intuition

# Python — no built-in, need itertools or a loop
from itertools import groupby
result = [k for k, _ in groupby(lst)]

# JavaScript — no built-in, manual filter
const result = arr.filter((x, i) => i === 0 || x !== arr[i-1]);

// Rust — in-place, one line
vec.dedup();

// Or functional — returns a new Vec
let result: Vec<_> = list.iter()
 .enumerate()
 .filter(|(i, x)| *i == 0 || list[i-1] != **x)
 .map(|(_, x)| x.clone())
 .collect();

`dedup()` is short for "deduplicate". It's built into `Vec<T>` and runs in a single pass, O(n) time, O(1) extra space. It requires `T: PartialEq` — the elements must be comparable.

How It Works in Rust

// Option 1: In-place mutation (fastest, no allocation)
fn compress(list: &mut Vec<T>) where T: PartialEq {
 list.dedup();  // modifies the Vec directly
}

// Option 2: Functional — returns a new Vec (input unchanged)
fn compress_functional<T: PartialEq + Clone>(list: &[T]) -> Vec<T> {
 list.iter()
     .enumerate()
     .filter(|(i, x)| *i == 0 || list[i - 1] != **x)
     .map(|(_, x)| x.clone())
     .collect()
}

The `&mut` in Option 1 is explicit — you're saying "I'm modifying this data." In JavaScript, mutation is implicit and often surprising. In Rust, you can't mutate without opt-in. The `windows(2)` approach compares adjacent pairs directly:

// Using windows — reads naturally as "pairs of neighbors"
fn compress_windows<T: PartialEq + Clone>(list: &[T]) -> Vec<T> {
 if list.is_empty() { return vec![]; }
 
 let mut result = vec![list[0].clone()];
 result.extend(
     list.windows(2)
         .filter(|w| w[0] != w[1])
         .map(|w| w[1].clone())
 );
 result
}

`windows(2)` gives you overlapping pairs: `[a,b]`, `[b,c]`, `[c,d]`... wherever two neighbors differ, the second one belongs in the result.

What This Unlocks

Log deduplication — collapse repeated identical log lines before storing
Signal processing — remove identical consecutive sensor readings (noise elimination)
Run-length encoding — `dedup` is the preprocessing step before counting runs (see example 010)

Key Differences

Concept	OCaml	Rust
Idiomatic approach	Recursive pattern match on cons cells	`vec.dedup()` (in-place)
In-place option	Not available (immutable lists)	`dedup()` with `&mut Vec<T>`
Pairwise comparison	`h1 :: h2 :: _` pattern	`windows(2)` iterator
Equality	Polymorphic `=`	`PartialEq` trait bound
New list vs mutation	Always new list	Explicit choice (`&` vs `&mut`)

// Eliminate Duplicates
// Rust translation from OCaml 99 Problems #8

// Idiomatic Rust (in-place)
fn compress<T: PartialEq>(list: &mut Vec<T>) {
    list.dedup();
}

// Functional style (returns new vec)
fn compress_functional<T: PartialEq + Clone>(list: &[T]) -> Vec<T> {
    list.iter()
        .enumerate()
        .filter(|(i, x)| *i == 0 || list[i - 1] != **x)
        .map(|(_, x)| x.clone())
        .collect()
}

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

    #[test]
    fn test_compress() {
        assert_eq!(
            compress_functional(&["a","a","a","b","c","c","d","e","e","e"]),
            vec!["a","b","c","d","e"]
        );
        assert_eq!(compress_functional::<i32>(&[]), Vec::<i32>::new());
        assert_eq!(compress_functional(&[1]), vec![1]);
    }
}

fn main() {
    let list = vec!["a","a","a","b","c","c"];
    println!("compress({:?}) = {:?}", list, compress_functional(&list));
    println!("✓ Rust tests passed");
}

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

📊 Detailed Comparison

Comparison: Eliminate Consecutive Duplicates

OCaml — Pattern matching

🐪 Show OCaml equivalent

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

1. Rust's `dedup()` is a one-liner for the imperative approach — stdlib is batteries-included 2. OCaml's pattern matching on cons cells is more elegant for list algorithms 3. The `windows(2)` approach has no OCaml equivalent — it leverages contiguous memory layout 4. Mutation in Rust is always a conscious choice (`&mut`), never accidental 5. Both languages handle edge cases (empty, single-element) but Rust uses conditionals where OCaml uses pattern arms