891 Intermediate

891-flatten-iterator — Flatten Iterator

Functional Programming

Tutorial

The Problem

Nested data structures are pervasive: lists of lists, optional values that may or may not be present, results that may succeed or fail. Flattening removes exactly one level of nesting, collapsing Vec<Vec<T>> into Vec<T>, Option<Option<T>> into Option<T>, or Vec<Option<T>> into Vec<T>. This is formally the monadic join operation. In Haskell, concat and >>= (bind) express this. OCaml has List.concat and Option.join. Rust's .flatten() and .flat_map() (which is map followed by flatten) are the standard tools. This example covers all the flatten patterns across nested containers.

🎯 Learning Outcomes

• Use .flatten() to remove exactly one level of iterator nesting

• Use .flat_map(f) as the composition of .map(f).flatten()

• Flatten Vec<Option<T>> to keep only Some values (equivalent to filter_map)

• Understand .flatten() as the monadic join operation

• Compare with OCaml's List.concat, Option.join, and List.concat_map

Code Example

fn flatten_vecs(nested: Vec<Vec<i32>>) -> Vec<i32> {
    nested.into_iter().flatten().collect()
}

fn words_in_sentences(sentences: &[&str]) -> Vec<String> {
    sentences.iter()
        .flat_map(|s| s.split_whitespace())
        .map(String::from)
        .collect()
}

fn flatten_options(opts: Vec<Option<i32>>) -> Vec<i32> {
    opts.into_iter().flatten().collect()
}

(* Flatten a list of lists *)
let flatten_lists = List.flatten

(* flat_map = map + flatten *)
let flat_map f lst = List.flatten (List.map f lst)

let words_in_sentences sentences =
  flat_map (String.split_on_char ' ') sentences

(* Flatten options using filter_map *)
let flatten_options lst =
  List.filter_map Fun.id lst

Key Differences

Uniform interface: Rust .flatten() works on any Iterator<Item = IntoIterator>; OCaml has separate List.concat, Option.join, Array.concat per type.

Option as iterator: Rust Option<T> implements IntoIterator (0 or 1 elements), enabling .flatten() on Vec<Option<T>>; OCaml requires List.filter_map.

Monadic identity: Both express join = flatten from category theory, but Rust makes it syntactically uniform across container types.

Laziness: Rust .flatten() is lazy when chained; OCaml List.concat is always eager.

OCaml Approach

OCaml's List.concat: 'a list list -> 'a list flattens one level. List.concat_map: 'a list -> ('a -> 'b list) -> 'b list is flat_map. Option.join: 'a option option -> 'a option flattens nested options. List.filter_map: ('a -> 'b option) -> 'a list -> 'b list flattens list of options while mapping. For sequences, Seq.flat_map provides lazy flattening. OCaml lacks a single flatten that works uniformly across container types — each has its own.

Full Source

#![allow(clippy::all)]
// Example 097: Flatten Iterator
// Collapse one level of nesting using .flatten() and .flat_map()

// === Approach 1: flatten Vec<Vec<T>> ===

pub fn flatten_vecs(nested: Vec<Vec<i32>>) -> Vec<i32> {
    nested.into_iter().flatten().collect()
}

// === Approach 2: flat_map — map then flatten ===

pub fn words_in_sentences(sentences: &[&str]) -> Vec<String> {
    sentences
        .iter()
        .flat_map(|s| s.split_whitespace())
        .map(String::from)
        .collect()
}

pub fn expand_ranges(ranges: &[(i32, i32)]) -> Vec<i32> {
    ranges.iter().flat_map(|&(lo, hi)| lo..=hi).collect()
}

pub fn chars_of_words(words: &[&str]) -> Vec<char> {
    words.iter().flat_map(|w| w.chars()).collect()
}

// === Approach 3: Flatten Option<T> — Some yields one item, None yields none ===

pub fn flatten_options(opts: Vec<Option<i32>>) -> Vec<i32> {
    opts.into_iter().flatten().collect()
}

pub fn parse_ints(strs: &[&str]) -> Vec<i32> {
    strs.iter().filter_map(|s| s.parse::<i32>().ok()).collect()
}

// === Approach 4: Flatten Result<T, E> — Ok yields one item, Err is skipped ===

pub fn collect_ok<T: Clone, E>(results: &[Result<T, E>]) -> Vec<T> {
    results
        .iter()
        .filter_map(|r| r.as_ref().ok().cloned())
        .collect()
}

// === Approach 5: Two levels deep ===

pub fn deep_flatten(nested: Vec<Vec<Vec<i32>>>) -> Vec<i32> {
    nested.into_iter().flatten().flatten().collect()
}

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

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

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

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

    #[test]
    fn test_words_in_sentences() {
        let sentences = ["hello world", "foo bar baz"];
        assert_eq!(
            words_in_sentences(&sentences),
            vec!["hello", "world", "foo", "bar", "baz"]
        );
    }

    #[test]
    fn test_expand_ranges() {
        let ranges = [(1, 3), (7, 9)];
        assert_eq!(expand_ranges(&ranges), vec![1, 2, 3, 7, 8, 9]);
    }

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

    #[test]
    fn test_chars_of_words() {
        let words = ["hi", "yo"];
        assert_eq!(chars_of_words(&words), vec!['h', 'i', 'y', 'o']);
    }

    #[test]
    fn test_flatten_options_mixed() {
        let opts = vec![Some(1), None, Some(3), None, Some(5)];
        assert_eq!(flatten_options(opts), vec![1, 3, 5]);
    }

    #[test]
    fn test_flatten_options_all_none() {
        let opts: Vec<Option<i32>> = vec![None, None];
        assert_eq!(flatten_options(opts), vec![]);
    }

    #[test]
    fn test_parse_ints() {
        let strs = ["1", "two", "3", "four", "5"];
        assert_eq!(parse_ints(&strs), vec![1, 3, 5]);
    }

    #[test]
    fn test_collect_ok() {
        let results: Vec<Result<i32, &str>> = vec![Ok(1), Err("bad"), Ok(3)];
        assert_eq!(collect_ok(&results), vec![1, 3]);
    }

    #[test]
    fn test_deep_flatten() {
        let nested = vec![vec![vec![1, 2], vec![3]], vec![vec![4, 5, 6]]];
        assert_eq!(deep_flatten(nested), vec![1, 2, 3, 4, 5, 6]);
    }
}

(* Example 097: Flatten Iterator *)
(* flat_map vs flatten *)

(* Approach 1: List.flatten *)
let flatten_lists = List.flatten

let nested = [[1;2;3]; [4;5]; [6;7;8;9]]
(* flatten_lists nested = [1;2;3;4;5;6;7;8;9] *)

(* Approach 2: flat_map = map + flatten *)
let flat_map f lst = List.flatten (List.map f lst)

let words_in_sentences sentences =
  flat_map (String.split_on_char ' ') sentences

let expand_ranges ranges =
  flat_map (fun (lo, hi) -> List.init (hi - lo + 1) (fun i -> lo + i)) ranges

(* Approach 3: Flatten options — filter_map *)
let flatten_options lst =
  List.filter_map Fun.id lst

let parse_ints strs =
  List.filter_map (fun s ->
    try Some (int_of_string s) with _ -> None
  ) strs

(* Nested flatten *)
let deep_flatten lll =
  List.flatten (List.flatten lll)

let flatten_tree t =
  let rec aux = function
    | `Leaf x -> [x]
    | `Node children -> flat_map aux children
  in
  aux t

(* Tests *)
let () =
  assert (flatten_lists [[1;2]; [3;4]; [5]] = [1;2;3;4;5]);

  assert (words_in_sentences ["hello world"; "foo bar baz"]
          = ["hello"; "world"; "foo"; "bar"; "baz"]);

  assert (expand_ranges [(1,3); (7,9)] = [1;2;3;7;8;9]);

  assert (flatten_options [Some 1; None; Some 2; None; Some 3] = [1;2;3]);

  assert (parse_ints ["1"; "abc"; "3"; ""; "5"] = [1;3;5]);

  assert (deep_flatten [[[1;2]; [3]]; [[4]; [5;6]]] = [1;2;3;4;5;6]);

  let tree = `Node [`Leaf 1; `Node [`Leaf 2; `Leaf 3]; `Leaf 4] in
  assert (flatten_tree tree = [1;2;3;4]);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

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

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

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

    #[test]
    fn test_words_in_sentences() {
        let sentences = ["hello world", "foo bar baz"];
        assert_eq!(
            words_in_sentences(&sentences),
            vec!["hello", "world", "foo", "bar", "baz"]
        );
    }

    #[test]
    fn test_expand_ranges() {
        let ranges = [(1, 3), (7, 9)];
        assert_eq!(expand_ranges(&ranges), vec![1, 2, 3, 7, 8, 9]);
    }

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

    #[test]
    fn test_chars_of_words() {
        let words = ["hi", "yo"];
        assert_eq!(chars_of_words(&words), vec!['h', 'i', 'y', 'o']);
    }

    #[test]
    fn test_flatten_options_mixed() {
        let opts = vec![Some(1), None, Some(3), None, Some(5)];
        assert_eq!(flatten_options(opts), vec![1, 3, 5]);
    }

    #[test]
    fn test_flatten_options_all_none() {
        let opts: Vec<Option<i32>> = vec![None, None];
        assert_eq!(flatten_options(opts), vec![]);
    }

    #[test]
    fn test_parse_ints() {
        let strs = ["1", "two", "3", "four", "5"];
        assert_eq!(parse_ints(&strs), vec![1, 3, 5]);
    }

    #[test]
    fn test_collect_ok() {
        let results: Vec<Result<i32, &str>> = vec![Ok(1), Err("bad"), Ok(3)];
        assert_eq!(collect_ok(&results), vec![1, 3]);
    }

    #[test]
    fn test_deep_flatten() {
        let nested = vec![vec![vec![1, 2], vec![3]], vec![vec![4, 5, 6]]];
        assert_eq!(deep_flatten(nested), vec![1, 2, 3, 4, 5, 6]);
    }
}

Deep Comparison

OCaml vs Rust: Flatten Iterator

Side-by-Side Code

OCaml

(* Flatten a list of lists *)
let flatten_lists = List.flatten

(* flat_map = map + flatten *)
let flat_map f lst = List.flatten (List.map f lst)

let words_in_sentences sentences =
  flat_map (String.split_on_char ' ') sentences

(* Flatten options using filter_map *)
let flatten_options lst =
  List.filter_map Fun.id lst

Rust (idiomatic — iterator chains)

fn flatten_vecs(nested: Vec<Vec<i32>>) -> Vec<i32> {
    nested.into_iter().flatten().collect()
}

fn words_in_sentences(sentences: &[&str]) -> Vec<String> {
    sentences.iter()
        .flat_map(|s| s.split_whitespace())
        .map(String::from)
        .collect()
}

fn flatten_options(opts: Vec<Option<i32>>) -> Vec<i32> {
    opts.into_iter().flatten().collect()
}

Rust (functional/recursive — manual via fold)

fn flatten_vecs_fold(nested: Vec<Vec<i32>>) -> Vec<i32> {
    nested.into_iter().fold(Vec::new(), |mut acc, inner| {
        acc.extend(inner);
        acc
    })
}

Type Signatures

Concept	OCaml	Rust
Flatten nested lists	`val flatten : 'a list list -> 'a list`	`fn flatten_vecs(nested: Vec<Vec<i32>>) -> Vec<i32>`
flat_map	`List.flatten (List.map f lst)`	`.flat_map(f)` directly on iterator
Flatten options	`List.filter_map Fun.id lst`	`.into_iter().flatten().collect()`
Generic constraint	`'a list list`	`Iterator<Item: IntoIterator>`

Key Insights

**Option and Result implement IntoIterator** — In Rust, Some(x) yields one item and None yields zero, so .flatten() on Vec<Option<T>> is equivalent to OCaml's List.filter_map Fun.id. This is a beautiful unification: the same combinator works on nested Vecs, optional values, and fallible results.

**.flat_map(f) = .map(f).flatten()** — Both languages share this equivalence. OCaml expresses it as List.flatten (List.map f lst); Rust has a dedicated .flat_map() adaptor that fuses the two steps without an intermediate allocation.

Ownership-aware flattening — Vec<Vec<T>>.into_iter().flatten() moves each inner Vec and its elements. Using .iter().flatten() instead would yield &T references, avoiding moves. OCaml's GC hides this distinction entirely; Rust makes ownership explicit at the type level.

Depth is explicit — .flatten() removes exactly one layer of nesting. To flatten two levels you chain .flatten().flatten(). OCaml's List.flatten is likewise single-depth; deep_flatten requires two calls. Neither language provides automatic arbitrary-depth flattening.

Zero-cost laziness — Rust's iterator adaptors are lazy; nothing is allocated until .collect(). OCaml's List.flatten builds an intermediate list eagerly. For large datasets, the Rust version is more memory-efficient because elements flow directly into the output collection.

When to Use Each Style

**Use .flatten()** when you already have an Iterator<Item: IntoIterator> and want to collapse one nesting level — Vec<Vec<T>>, Vec<Option<T>>, or Vec<Result<T, E>>.

**Use .flat_map(f)** when the mapping step itself produces an iterable (e.g., splitting strings into words, expanding ranges). It is strictly more composable than .map().flatten() and communicates intent more clearly.

**Use the fold/recursive style** only when you need to accumulate state during flattening, or when teaching the underlying mechanics explicitly.

Exercises

Use .flat_map() to implement combinations(xs: &[i32], k: usize) -> Vec<Vec<i32>> generating all k-element subsets.

Implement flatten_result_ok<T, E>(results: Vec<Result<Vec<T>, E>>) -> Result<Vec<T>, E> that flattens on success or returns the first error.

Write cartesian_product(a: &[i32], b: &[i32]) -> Vec<(i32, i32)> using a single .flat_map() and .map() chain.

Open Source Repos

functional-rust

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

Rust