014 Intermediate

014 — Duplicate Elements

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "014 — Duplicate Elements" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Duplicating every element of a list (OCaml 99 Problems #14) — transforming `[a, b, c]` into `[a, a, b, b, c, c]` — is an exercise in `flat_map`: the structure-expanding operation that maps each input to multiple outputs and concatenates the results. Key difference from OCaml: 1. **`flat_map` vs `concat_map`**: Rust's `flat_map` and OCaml's `List.concat_map` are the same operation. Both exist in their respective standard libraries since recent versions.

Tutorial

The Problem

Duplicating every element of a list (OCaml 99 Problems #14) — transforming [a, b, c] into [a, a, b, b, c, c] — is an exercise in flat_map: the structure-expanding operation that maps each input to multiple outputs and concatenates the results. It is the simplest possible case of flat_map with a fixed expansion factor.

This operation appears in data augmentation pipelines (duplicating training examples), protocol framing (repeating sync bytes), audio processing (sample rate doubling by interpolation), and test harness generation. Understanding the flat_map pattern here prepares you for the generalized replicate_n_times in example 015.

🎯 Learning Outcomes

• Use flat_map to expand each element into multiple output elements

• Understand that flat_map is equivalent to map followed by flatten

• Compare iterative (loop), functional (flat_map), and recursive implementations

• Pre-allocate output Vec with Vec::with_capacity(len * 2) for performance

• Recognize duplication as a degenerate case of replicate(n=2)

• Pre-allocate output with Vec::with_capacity(list.len() * 2) to avoid reallocations

• Understand duplicate as a special case of replicate(n=2) — preparing for the generalization in example 015

Code Example

pub fn duplicate<T: Clone>(list: &[T]) -> Vec<T> {
    list.iter().flat_map(|x| vec![x.clone(), x.clone()]).collect()
}

let rec duplicate = function
  | [] -> []
  | h :: t -> h :: h :: duplicate t

Key Differences

**flat_map vs concat_map**: Rust's flat_map and OCaml's List.concat_map are the same operation. Both exist in their respective standard libraries since recent versions.

Clone necessity: Rust requires T: Clone to duplicate elements. OCaml's GC shares the same pointer for both copies — no actual duplication of heap data.

**@ vs extend**: OCaml's list append @ is O(n). Rust's Vec::extend is O(k) where k is the new elements. Use fold carefully in OCaml to avoid accidental O(n²) behavior.

Pre-allocation: Rust's Vec::with_capacity avoids reallocations when output size is known. OCaml lists do not support pre-allocation (they are singly-linked).

**flat_map vs loop:** flat_map(|x| vec![x, x]) is declarative. The imperative loop with push twice is more efficient (no intermediate Vec per element). Both are O(n).

Pre-allocation: Vec::with_capacity(n * 2) avoids reallocations. The flat_map version doesn't know the output size upfront, so it may reallocate. In performance-sensitive code, pre-allocation matters.

Clone semantics: x.clone() requires T: Clone. For Copy types (integers), .copied() is cheaper. OCaml's GC avoids this distinction entirely.

**Specialization of replicate:** duplicate is replicate(n=2). Understanding this prepares you for example 015's general replicate_n_times.

OCaml Approach

OCaml's version is: let duplicate lst = List.concat_map (fun x -> [x; x]) lst. Alternatively with List.fold_left: let duplicate lst = List.fold_left (fun acc x -> acc @ [x; x]) [] lst — but this is O(n²) because @ is O(n). The correct fold uses difference lists or reverses at the end: List.rev (List.fold_left (fun acc x -> x :: x :: acc) [] lst).

Full Source

#![allow(clippy::all)]
/// Duplicate Elements (99 Problems #14)
///
/// Duplicate every element of a list.
/// [a; b; c] → [a; a; b; b; c; c]

// ── Idiomatic Rust: flat_map ────────────────────────────────────────────────

pub fn duplicate<T: Clone>(list: &[T]) -> Vec<T> {
    list.iter()
        .flat_map(|x| vec![x.clone(), x.clone()])
        .collect()
}

// ── Using iterators more efficiently ────────────────────────────────────────

pub fn duplicate_iter<T: Clone>(list: &[T]) -> Vec<T> {
    let mut result = Vec::with_capacity(list.len() * 2);
    for item in list {
        result.push(item.clone());
        result.push(item.clone());
    }
    result
}

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

pub fn duplicate_recursive<T: Clone>(list: &[T]) -> Vec<T> {
    match list.split_first() {
        None => vec![],
        Some((head, tail)) => {
            let mut result = vec![head.clone(), head.clone()];
            result.extend(duplicate_recursive(tail));
            result
        }
    }
}

// ── Fold-based ──────────────────────────────────────────────────────────────

pub fn duplicate_fold<T: Clone>(list: &[T]) -> Vec<T> {
    list.iter()
        .fold(Vec::with_capacity(list.len() * 2), |mut acc, x| {
            acc.push(x.clone());
            acc.push(x.clone());
            acc
        })
}

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

    #[test]
    fn test_empty() {
        assert_eq!(duplicate::<i32>(&[]), vec![]);
        assert_eq!(duplicate_recursive::<i32>(&[]), vec![]);
    }

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

    #[test]
    fn test_multiple() {
        assert_eq!(duplicate(&[1, 2, 3]), vec![1, 1, 2, 2, 3, 3]);
        assert_eq!(duplicate_iter(&[1, 2, 3]), vec![1, 1, 2, 2, 3, 3]);
        assert_eq!(duplicate_recursive(&[1, 2, 3]), vec![1, 1, 2, 2, 3, 3]);
        assert_eq!(duplicate_fold(&[1, 2, 3]), vec![1, 1, 2, 2, 3, 3]);
    }

    #[test]
    fn test_strings() {
        assert_eq!(duplicate(&["a", "b"]), vec!["a", "a", "b", "b"]);
    }

    #[test]
    fn test_large() {
        let input: Vec<i32> = (0..100).collect();
        let result = duplicate(&input);
        assert_eq!(result.len(), 200);
        assert_eq!(result[0], 0);
        assert_eq!(result[1], 0);
        assert_eq!(result[198], 99);
        assert_eq!(result[199], 99);
    }
}

(* Duplicate Elements — 99 Problems #14 *)
(* Duplicate every element: [a;b;c] → [a;a;b;b;c;c] *)

(* ── Recursive ───────────────────────────────────────────── *)

let rec duplicate = function
  | [] -> []
  | h :: t -> h :: h :: duplicate t

(* ── Tail-recursive with accumulator ─────────────────────── *)

let duplicate_tr lst =
  let rec aux acc = function
    | [] -> List.rev acc
    | h :: t -> aux (h :: h :: acc) t
  in aux [] lst

(* ── Using concat_map ────────────────────────────────────── *)

let duplicate_map lst =
  List.concat_map (fun x -> [x; x]) lst

(* ── Tests ────────────────────────────────────────────────── *)
let () =
  assert (duplicate [] = []);
  assert (duplicate [1] = [1; 1]);
  assert (duplicate [1; 2; 3] = [1; 1; 2; 2; 3; 3]);
  assert (duplicate_tr ['a'; 'b'; 'c'] = ['a'; 'a'; 'b'; 'b'; 'c'; 'c']);
  assert (duplicate_map [1; 2] = [1; 1; 2; 2]);
  print_endline "✓ Duplicate elements tests passed"

✓ Tests Rust test suite

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

    #[test]
    fn test_empty() {
        assert_eq!(duplicate::<i32>(&[]), vec![]);
        assert_eq!(duplicate_recursive::<i32>(&[]), vec![]);
    }

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

    #[test]
    fn test_multiple() {
        assert_eq!(duplicate(&[1, 2, 3]), vec![1, 1, 2, 2, 3, 3]);
        assert_eq!(duplicate_iter(&[1, 2, 3]), vec![1, 1, 2, 2, 3, 3]);
        assert_eq!(duplicate_recursive(&[1, 2, 3]), vec![1, 1, 2, 2, 3, 3]);
        assert_eq!(duplicate_fold(&[1, 2, 3]), vec![1, 1, 2, 2, 3, 3]);
    }

    #[test]
    fn test_strings() {
        assert_eq!(duplicate(&["a", "b"]), vec!["a", "a", "b", "b"]);
    }

    #[test]
    fn test_large() {
        let input: Vec<i32> = (0..100).collect();
        let result = duplicate(&input);
        assert_eq!(result.len(), 200);
        assert_eq!(result[0], 0);
        assert_eq!(result[1], 0);
        assert_eq!(result[198], 99);
        assert_eq!(result[199], 99);
    }
}

Deep Comparison

Duplicate Elements: OCaml vs Rust

The Core Insight

Duplicating elements is a one-to-many transformation: each input produces exactly two outputs. It's a clean exercise in list construction — OCaml uses cons (::) to prepend two copies, while Rust uses flat_map or push-based iteration. The simplicity makes ownership differences especially visible.

OCaml Approach

OCaml's recursive solution is elegantly minimal:

let rec duplicate = function
  | [] -> []
  | h :: t -> h :: h :: duplicate t

Two cons operations prepend two copies of the head. The tail-recursive version reverses at the end:

let duplicate_tr lst =
  let rec aux acc = function
    | [] -> List.rev acc
    | h :: t -> aux (h :: h :: acc) t
  in aux [] lst

Rust Approach

Rust's iterator approach uses flat_map for the one-to-many expansion:

pub fn duplicate<T: Clone>(list: &[T]) -> Vec<T> {
    list.iter().flat_map(|x| vec![x.clone(), x.clone()]).collect()
}

The imperative version with push is more efficient (avoids intermediate vec allocation):

for item in list {
    result.push(item.clone());
    result.push(item.clone());
}

Key Differences

Aspect	OCaml	Rust
Construction	`h :: h :: tail` (O(1) prepend)	`push` (O(1) amortized append)
Copying	Automatic (values shared)	Explicit `clone()`
Direction	Builds front-to-back (cons)	Builds back via push
Memory	New list nodes (GC)	Pre-allocatable Vec
One-to-many	`concat_map (fun x -> [x;x])`	`flat_map(\\|x\\| vec![x,x])`

What Rust Learners Should Notice

• **with_capacity for known sizes**: When you know the output will be exactly 2 * input.len(), pre-allocate with Vec::with_capacity. OCaml can't do this with linked lists.

• **flat_map creates temporary Vecs**: flat_map(|x| vec![x, x]) allocates a small Vec per element. The push-based version avoids this overhead entirely.

• Clone is the explicit cost: In OCaml, h :: h :: t shares the same value. In Rust, Clone creates independent copies. For Copy types (integers, etc.), this is zero-cost.

• Simple problems reveal language philosophy: OCaml optimizes for expressiveness (one line!). Rust lets you choose between expressiveness (flat_map) and performance (push with pre-allocation).

Exercises

Triplicate: Generalize to triplicate<T: Clone>(list: &[T]) -> Vec<T> that produces three copies of each element. Then generalize to replicate<T: Clone>(list: &[T], n: usize) -> Vec<T>.

Interleave: Write interleave<T: Clone>(a: &[T], b: &[T]) -> Vec<T> that produces [a[0], b[0], a[1], b[1], ...]. Use zip and flat_map.

De-duplicate: Write dedup_consecutive<T: PartialEq + Clone>(list: &[T]) -> Vec<T> that removes consecutive duplicates (the inverse of duplicate). Use .windows(2) to detect adjacent pairs.

Interleave with separator: Implement intersperse(list: &[T], sep: T) -> Vec<T> that inserts sep between every pair of adjacent elements — [a, b, c] → [a, sep, b, sep, c]. This is flat_map with a conditional separator.

N-way interleave: Implement interleave_many(lists: &[Vec<T>]) -> Vec<T> that round-robins from multiple lists: [1,2], [a,b], [x,y] → [1, a, x, 2, b, y].

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

Duplicate Elements: OCaml vs Rust

The Core Insight

OCaml Approach

Rust Approach

Key Differences

What Rust Learners Should Notice

Further Reading

Exercises

Open Source Repos