015 Intermediate

015 — Replicate Elements N Times

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "015 — Replicate Elements N Times" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Replicating each element `n` times (OCaml 99 Problems #15) generalizes duplication: `replicate([a, b, c], 3)` produces `[a, a, a, b, b, b, c, c, c]`. Key difference from OCaml: 1. **`repeat().take(n)`**: Rust's `std::iter::repeat` produces an infinite iterator; `.take(n)` limits it. OCaml's `List.init n (fun _

Tutorial

The Problem

Replicating each element n times (OCaml 99 Problems #15) generalizes duplication: replicate([a, b, c], 3) produces [a, a, a, b, b, b, c, c, c]. This is a direct application of flat_map with std::iter::repeat, combining two fundamental iterator patterns: structure expansion and repetition.

Replicate-then-flatten appears in data pipelines (upsampling time series), image processing (nearest-neighbor scaling), protocol encoding (preamble repetition), and test data generation. std::iter::repeat(x).take(n) is Rust's idiomatic way to generate n identical values — understanding this combination unlocks a large class of iterator transformations.

🎯 Learning Outcomes

• Combine flat_map with std::iter::repeat(x).take(n) for efficient replication

• Pre-allocate output with Vec::with_capacity(list.len() * n) when n is known

• Understand that replicate(n=1) is identity, replicate(n=0) is filter-out-all

• Implement recursive replication with a nested helper

• Recognize this as the generalization of duplicate (example 014)

• Verify edge cases: replicate(list, 0) returns [] and replicate(list, 1) returns a copy of list

• Combine flat_map with std::iter::repeat(x.clone()).take(n) for lazy, allocation-efficient replication

Code Example

pub fn replicate<T: Clone>(list: &[T], n: usize) -> Vec<T> {
    list.iter()
        .flat_map(|x| std::iter::repeat(x.clone()).take(n))
        .collect()
}

let replicate lst n =
  let rec repeat x = function
    | 0 -> []
    | k -> x :: repeat x (k - 1)
  in List.concat_map (fun x -> repeat x n) lst

Key Differences

**repeat().take(n)**: Rust's std::iter::repeat produces an infinite iterator; .take(n) limits it. OCaml's List.init n (fun _ -> x) is finite by construction.

Laziness: Rust's repeat(x).take(n) is lazy — no allocation until consumed by flat_map. OCaml's List.init is eager.

Clone cost: Rust clones x once per copy. OCaml shares the same GC pointer for all n copies — O(1) space overhead per run in OCaml vs O(n) in Rust for heap-allocated types.

n=0 behavior: Both correctly produce an empty output for n=0. repeat(x).take(0) yields nothing; List.init 0 f produces [].

**repeat + take idiom:** std::iter::repeat(x).take(n) is the canonical Rust pattern for generating n copies of a value. It is lazy — no allocation until consumed by flat_map.

Pre-allocation wins: For large n, Vec::with_capacity(list.len() * n) with a nested loop is O(n) allocations saved. The flat_map version may allocate intermediate iterators.

**n=0 case:** replicate(list, 0) returns an empty Vec. OCaml's List.init 0 f also returns []. Edge cases matter for downstream callers.

**n=1 is identity:** replicate(list, 1) == list.to_vec(). This is a useful property test: verify it with proptest.

OCaml Approach

OCaml's version: let replicate lst n = List.concat_map (fun x -> List.init n (fun _ -> x)) lst. List.init n f creates [f 0; f 1; ...; f (n-1)]; using fun _ -> x ignores the index and produces n copies. The tail-recursive version accumulates copies reversed: List.rev (List.fold_left (fun acc x -> let copies = List.init n (fun _ -> x) in List.rev_append copies acc) [] lst).

Full Source

#![allow(clippy::all)]
/// Replicate Elements N Times (99 Problems #15)
///
/// Replicate every element of a list n times.
/// replicate [a; b; c] 3 → [a; a; a; b; b; b; c; c; c]

// ── Idiomatic Rust: flat_map + repeat ───────────────────────────────────────

pub fn replicate<T: Clone>(list: &[T], n: usize) -> Vec<T> {
    list.iter()
        .flat_map(|x| std::iter::repeat(x.clone()).take(n))
        .collect()
}

// ── Pre-allocated version ───────────────────────────────────────────────────

pub fn replicate_prealloc<T: Clone>(list: &[T], n: usize) -> Vec<T> {
    let mut result = Vec::with_capacity(list.len() * n);
    for item in list {
        for _ in 0..n {
            result.push(item.clone());
        }
    }
    result
}

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

pub fn replicate_recursive<T: Clone>(list: &[T], n: usize) -> Vec<T> {
    fn repeat_elem<T: Clone>(x: &T, n: usize) -> Vec<T> {
        if n == 0 {
            vec![]
        } else {
            let mut rest = repeat_elem(x, n - 1);
            rest.insert(0, x.clone());
            rest
        }
    }

    match list.split_first() {
        None => vec![],
        Some((head, tail)) => {
            let mut result = repeat_elem(head, n);
            result.extend(replicate_recursive(tail, n));
            result
        }
    }
}

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

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

    #[test]
    fn test_zero_times() {
        assert_eq!(replicate(&[1, 2, 3], 0), vec![]);
    }

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

    #[test]
    fn test_three_times() {
        assert_eq!(
            replicate(&['a', 'b', 'c'], 3),
            vec!['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c']
        );
        assert_eq!(
            replicate_prealloc(&['a', 'b', 'c'], 3),
            vec!['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c']
        );
        assert_eq!(
            replicate_recursive(&['a', 'b', 'c'], 3),
            vec!['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c']
        );
    }

    #[test]
    fn test_single_element() {
        assert_eq!(replicate(&[42], 5), vec![42, 42, 42, 42, 42]);
    }

    #[test]
    fn test_large() {
        let input: Vec<i32> = (0..10).collect();
        let result = replicate(&input, 100);
        assert_eq!(result.len(), 1000);
        // First 100 should all be 0
        assert!(result[..100].iter().all(|&x| x == 0));
        // Last 100 should all be 9
        assert!(result[900..].iter().all(|&x| x == 9));
    }
}

(* Replicate Elements N Times — 99 Problems #15 *)
(* replicate [a;b;c] 3 → [a;a;a;b;b;b;c;c;c] *)

(* ── Recursive with helper ───────────────────────────────── *)

let replicate lst n =
  let rec repeat x = function
    | 0 -> []
    | k -> x :: repeat x (k - 1)
  in
  let rec aux = function
    | [] -> []
    | h :: t -> repeat h n @ aux t
  in aux lst

(* ── Tail-recursive ──────────────────────────────────────── *)

let replicate_tr lst n =
  let rec aux acc = function
    | [] -> List.rev acc
    | h :: t ->
      let rec add_n acc = function
        | 0 -> aux acc t
        | k -> add_n (h :: acc) (k - 1)
      in add_n acc n
  in aux [] lst

(* ── Using concat_map + List.init ────────────────────────── *)

let replicate_map lst n =
  List.concat_map (fun x -> List.init n (fun _ -> x)) lst

(* ── Tests ────────────────────────────────────────────────── *)
let () =
  assert (replicate [] 5 = []);
  assert (replicate [1;2;3] 0 = []);
  assert (replicate [1;2;3] 1 = [1;2;3]);
  assert (replicate ['a';'b';'c'] 3 = ['a';'a';'a';'b';'b';'b';'c';'c';'c']);
  assert (replicate_tr [1;2] 3 = [1;1;1;2;2;2]);
  assert (replicate_map [1;2] 2 = [1;1;2;2]);
  print_endline "✓ Replicate tests passed"

✓ Tests Rust test suite

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

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

    #[test]
    fn test_zero_times() {
        assert_eq!(replicate(&[1, 2, 3], 0), vec![]);
    }

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

    #[test]
    fn test_three_times() {
        assert_eq!(
            replicate(&['a', 'b', 'c'], 3),
            vec!['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c']
        );
        assert_eq!(
            replicate_prealloc(&['a', 'b', 'c'], 3),
            vec!['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c']
        );
        assert_eq!(
            replicate_recursive(&['a', 'b', 'c'], 3),
            vec!['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c']
        );
    }

    #[test]
    fn test_single_element() {
        assert_eq!(replicate(&[42], 5), vec![42, 42, 42, 42, 42]);
    }

    #[test]
    fn test_large() {
        let input: Vec<i32> = (0..10).collect();
        let result = replicate(&input, 100);
        assert_eq!(result.len(), 1000);
        // First 100 should all be 0
        assert!(result[..100].iter().all(|&x| x == 0));
        // Last 100 should all be 9
        assert!(result[900..].iter().all(|&x| x == 9));
    }
}

Deep Comparison

Replicate Elements N Times: OCaml vs Rust

The Core Insight

Replication is the general case of duplication — produce n copies of each element. It's a clean demonstration of repetition combinators: OCaml's List.init and Rust's std::iter::repeat().take(). The problem also highlights pre-allocation in Rust: since you know the output size exactly (len * n), you can avoid all reallocation.

OCaml Approach

A recursive helper generates n copies, then the main function maps over the list:

let replicate lst n =
  let rec repeat x = function
    | 0 -> []
    | k -> x :: repeat x (k - 1)
  in List.concat_map (fun x -> repeat x n) lst

Or more concisely with List.init:

let replicate lst n = List.concat_map (fun x -> List.init n (fun _ -> x)) lst

Rust Approach

std::iter::repeat combined with take and flat_map is elegant:

pub fn replicate<T: Clone>(list: &[T], n: usize) -> Vec<T> {
    list.iter()
        .flat_map(|x| std::iter::repeat(x.clone()).take(n))
        .collect()
}

The pre-allocated imperative version is optimal for performance:

let mut result = Vec::with_capacity(list.len() * n);
for item in list { for _ in 0..n { result.push(item.clone()); } }

Key Differences

Aspect	OCaml	Rust
Repeat combinator	`List.init n (fun _ -> x)`	`repeat(x).take(n)`
Expansion	`concat_map`	`flat_map`
Memory	Intermediate lists (GC)	Lazy iterator (zero-cost)
Pre-allocation	Not possible (linked list)	`Vec::with_capacity(len * n)`
n = 0	Returns `[]` naturally	Returns empty Vec

What Rust Learners Should Notice

• **std::iter::repeat is lazy**: Unlike vec![x; n] which allocates immediately, repeat(x).take(n) yields elements one at a time. Inside flat_map, this means no intermediate allocation.

• Pre-allocation matters: Vec::with_capacity(list.len() * n) allocates once. Without it, the Vec may reallocate multiple times as it grows. OCaml lists can't pre-allocate.

• Clone cost scales with n: Each element is cloned n times. For expensive-to-clone types, consider Rc<T> to share instead of copy.

• Edge case: n = 0: All implementations naturally return empty for n=0 — take(0) yields nothing, and the recursive base case 0 -> [] handles it.

Exercises

Benchmark: Compare replicate (with flat_map) vs replicate_prealloc (with with_capacity + loop) on a Vec<String> of 1000 elements with n=100. Which is faster and why?

Replicate with index: Write replicate_indexed(list: &[i32], n: usize) -> Vec<(usize, i32)> that produces n copies of each element tagged with their original index: [(0, a), (0, a), (1, b), (1, b), ...].

Variable replication: Write replicate_var(list: &[i32], counts: &[usize]) -> Vec<i32> where counts[i] specifies how many times to repeat list[i]. Use zip and flat_map.

Variable replication: Implement replicate_by(list: &[T], counts: &[usize]) -> Vec<T> where each element is replicated a different number of times from the counts slice. Hint: zip then flat_map.

Downsample: Implement every_nth(list: &[T], n: usize) -> Vec<T> that keeps every nth element — the inverse of replication when used for downsampling data.

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

Replicate Elements N Times: OCaml vs Rust

The Core Insight

OCaml Approach

Rust Approach

Key Differences

What Rust Learners Should Notice

Further Reading

Exercises

Open Source Repos