1182 Intermediate

List.flatten — Flatten Nested Lists

Functional Programming

Tutorial

The Problem

Given a list of lists, produce a single flat list containing all elements in order. Also demonstrate concat_map (flat_map), which maps each element to a list and flattens the results.

🎯 Learning Outcomes

• How Iterator::flatten mirrors OCaml's List.flatten with zero manual recursion

• How flat_map / Iterator::flat_map corresponds to OCaml's List.concat_map

• Recursive slice pattern matching with [head, rest @ ..] to process nested structure

• Why Clone is needed when flattening slices of owned Vec<T> values

🦀 The Rust Way

Rust's Iterator::flatten works on any iterator of iterables. Combined with .cloned() it converts &[Vec<T>] to Vec<T> without explicit loops. flat_map is the direct counterpart to concat_map: it maps each element to an iterator and flattens the results. The recursive version uses Rust's slice pattern [head, rest @ ..] to destructure the nested structure idiomatically.

Code Example

pub fn flatten<T: Clone>(nested: &[Vec<T>]) -> Vec<T> {
    nested.iter().flatten().cloned().collect()
}

pub fn concat_map<T, U, F>(list: &[T], f: F) -> Vec<U>
where
    F: Fn(&T) -> Vec<U>,
{
    list.iter().flat_map(f).collect()
}

(* Idiomatic: built-in List.flatten *)
let flat = List.flatten [[1; 2]; [3; 4; 5]; [6]; [7; 8; 9; 10]]

(* Recursive: append head to flattened tail *)
let rec flatten_rec = function
  | [] -> []
  | head :: rest -> head @ flatten_rec rest

(* concat_map: map then flatten in one pass *)
let pairs = List.concat_map (fun x -> [x; x * 10]) [1; 2; 3]

Key Differences

Flattening: OCaml uses List.flatten; Rust uses .iter().flatten().cloned().collect()

concat_map: OCaml has List.concat_map f xs; Rust uses .iter().flat_map(f).collect()

Append: OCaml's @ operator concatenates lists; Rust uses Vec::extend or iterator chaining

Ownership: Rust requires .cloned() because iterating &Vec<T> yields &T references, not owned values

OCaml Approach

OCaml provides List.flatten as a built-in that concatenates a list of lists into one. List.concat_map f xs is equivalent to List.flatten (List.map f xs) but more efficient. The recursive implementation uses the @ operator to append the head list to the recursively flattened tail.

Full Source

/// Idiomatic Rust: flatten a slice of Vecs using Iterator::flatten
pub fn flatten<T: Clone>(nested: &[Vec<T>]) -> Vec<T> {
    nested.iter().flatten().cloned().collect()
}

/// Functional/recursive: build the flat list by processing head and tail
pub fn flatten_recursive<T: Clone>(nested: &[Vec<T>]) -> Vec<T> {
    match nested {
        [] => vec![],
        [head, rest @ ..] => {
            let mut result = head.clone();
            result.extend(flatten_recursive(rest));
            result
        }
    }
}

/// concat_map equivalent: flat_map each element to a list of derived values
pub fn concat_map<T, U, F>(list: &[T], f: F) -> Vec<U>
where
    F: Fn(&T) -> Vec<U>,
{
    list.iter().flat_map(f).collect()
}

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

    #[test]
    fn test_flatten_empty() {
        let nested: Vec<Vec<i32>> = vec![];
        assert_eq!(flatten(&nested), vec![]);
    }

    #[test]
    fn test_flatten_single_inner() {
        let nested = vec![vec![42]];
        assert_eq!(flatten(&nested), vec![42]);
    }

    #[test]
    fn test_flatten_multiple() {
        let nested = vec![vec![1, 2], vec![3, 4, 5], vec![6], vec![7, 8, 9, 10]];
        assert_eq!(flatten(&nested), vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
    }

    #[test]
    fn test_flatten_with_empty_sublists() {
        let nested = vec![vec![], vec![1, 2], vec![], vec![3]];
        assert_eq!(flatten(&nested), vec![1, 2, 3]);
    }

    #[test]
    fn test_flatten_recursive_empty() {
        let nested: Vec<Vec<i32>> = vec![];
        assert_eq!(flatten_recursive(&nested), vec![]);
    }

    #[test]
    fn test_flatten_recursive_matches_idiomatic() {
        let nested = vec![vec![1, 2], vec![3, 4, 5], vec![6], vec![7, 8, 9, 10]];
        assert_eq!(flatten_recursive(&nested), flatten(&nested));
    }

    #[test]
    fn test_concat_map_empty() {
        let list: Vec<i32> = vec![];
        assert_eq!(concat_map(&list, |x| vec![*x, x * 10]), vec![]);
    }

    #[test]
    fn test_concat_map_pairs() {
        let list = vec![1, 2, 3];
        assert_eq!(
            concat_map(&list, |x| vec![*x, x * 10]),
            vec![1, 10, 2, 20, 3, 30]
        );
    }
}

(* Idiomatic OCaml: List.flatten flattens a list of lists *)
let nested = [[1; 2]; [3; 4; 5]; [6]; [7; 8; 9; 10]]
let flat = List.flatten nested

(* Recursive OCaml: append head list to flattened tail *)
let rec flatten_rec = function
  | [] -> []
  | head :: rest -> head @ flatten_rec rest

(* concat_map: flat_map each element to a derived list *)
let pairs = List.concat_map (fun x -> [x; x * 10]) [1; 2; 3]

let () =
  assert (flat = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]);
  assert (flatten_rec nested = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]);
  assert (pairs = [1; 10; 2; 20; 3; 30]);
  Printf.printf "Flat: %s\n"
    (String.concat " " (List.map string_of_int flat));
  print_endline "ok"

✓ Tests Rust test suite

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

    #[test]
    fn test_flatten_empty() {
        let nested: Vec<Vec<i32>> = vec![];
        assert_eq!(flatten(&nested), vec![]);
    }

    #[test]
    fn test_flatten_single_inner() {
        let nested = vec![vec![42]];
        assert_eq!(flatten(&nested), vec![42]);
    }

    #[test]
    fn test_flatten_multiple() {
        let nested = vec![vec![1, 2], vec![3, 4, 5], vec![6], vec![7, 8, 9, 10]];
        assert_eq!(flatten(&nested), vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
    }

    #[test]
    fn test_flatten_with_empty_sublists() {
        let nested = vec![vec![], vec![1, 2], vec![], vec![3]];
        assert_eq!(flatten(&nested), vec![1, 2, 3]);
    }

    #[test]
    fn test_flatten_recursive_empty() {
        let nested: Vec<Vec<i32>> = vec![];
        assert_eq!(flatten_recursive(&nested), vec![]);
    }

    #[test]
    fn test_flatten_recursive_matches_idiomatic() {
        let nested = vec![vec![1, 2], vec![3, 4, 5], vec![6], vec![7, 8, 9, 10]];
        assert_eq!(flatten_recursive(&nested), flatten(&nested));
    }

    #[test]
    fn test_concat_map_empty() {
        let list: Vec<i32> = vec![];
        assert_eq!(concat_map(&list, |x| vec![*x, x * 10]), vec![]);
    }

    #[test]
    fn test_concat_map_pairs() {
        let list = vec![1, 2, 3];
        assert_eq!(
            concat_map(&list, |x| vec![*x, x * 10]),
            vec![1, 10, 2, 20, 3, 30]
        );
    }
}

Deep Comparison

OCaml vs Rust: List.flatten — Flatten Nested Lists

Side-by-Side Code

OCaml

(* Idiomatic: built-in List.flatten *)
let flat = List.flatten [[1; 2]; [3; 4; 5]; [6]; [7; 8; 9; 10]]

(* Recursive: append head to flattened tail *)
let rec flatten_rec = function
  | [] -> []
  | head :: rest -> head @ flatten_rec rest

(* concat_map: map then flatten in one pass *)
let pairs = List.concat_map (fun x -> [x; x * 10]) [1; 2; 3]

Rust (idiomatic)

pub fn flatten<T: Clone>(nested: &[Vec<T>]) -> Vec<T> {
    nested.iter().flatten().cloned().collect()
}

pub fn concat_map<T, U, F>(list: &[T], f: F) -> Vec<U>
where
    F: Fn(&T) -> Vec<U>,
{
    list.iter().flat_map(f).collect()
}

Rust (functional/recursive)

pub fn flatten_recursive<T: Clone>(nested: &[Vec<T>]) -> Vec<T> {
    match nested {
        [] => vec![],
        [head, rest @ ..] => {
            let mut result = head.clone();
            result.extend(flatten_recursive(rest));
            result
        }
    }
}

Type Signatures

Concept	OCaml	Rust
flatten	`val flatten : 'a list list -> 'a list`	`fn flatten<T: Clone>(nested: &[Vec<T>]) -> Vec<T>`
concat_map	`val concat_map : ('a -> 'b list) -> 'a list -> 'b list`	`fn concat_map<T, U, F: Fn(&T) -> Vec<U>>(list: &[T], f: F) -> Vec<U>`
List type	`'a list list`	`&[Vec<T>]` (slice of Vecs)
Flat result	`'a list`	`Vec<T>`

Key Insights

Iterator::flatten is direct: Rust's Iterator::flatten is the exact structural equivalent of OCaml's List.flatten — both collapse one layer of nesting. No manual recursion or accumulator needed.

flat_map vs concat_map: OCaml's List.concat_map f xs and Rust's .flat_map(f) are the same abstraction: map to collections, flatten the results. Rust's iterator lazy evaluation means no intermediate allocation.

Clone boundary: OCaml lists are persistent/immutable and sharing is free. Rust's &[Vec<T>] holds references, so producing an owned Vec<T> requires .cloned(). If T: Copy, you'd use .copied() instead.

Slice patterns mirror list patterns: OCaml's head :: rest destructuring maps cleanly to Rust's [head, rest @ ..] slice pattern, making the recursive version very readable.

Performance: The idiomatic Rust version is O(n) in total elements and allocates exactly once. The recursive version allocates at each level (like OCaml's @), making it O(n²) in the worst case.

When to Use Each Style

Use idiomatic Rust when: You have a flat collection to produce and want maximum efficiency — .iter().flatten().cloned().collect() is the canonical one-liner. Use recursive Rust when: Teaching the OCaml parallel explicitly, or when processing nested structure that also needs transformation at each level before flattening.

Open Source Repos

functional-rust

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

Rust