007 Intermediate

Flatten Nested List

Recursive Data StructuresEnums

Tutorial Video

Text description (accessibility)

This video demonstrates the "Flatten Nested List" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Recursive Data Structures, Enums. Flatten an arbitrarily nested list structure into a flat list. Key difference from OCaml: 1. **Enum vs variant**: Rust's `enum Node<T>` is the same concept as OCaml's variant type, but owns its data on the heap

Tutorial

The Problem

Flatten an arbitrarily nested list structure into a flat list.

Flattening nested lists appears in JSON document processing (flatten nested arrays), compiler AST processing (flatten nested expression lists), and file system traversal (flatten directory trees). The problem requires a recursive data type — a list where each element is either a value or another list — and structural recursion over that type. This is the simplest non-trivial example of processing an algebraic data type.

🎯 Learning Outcomes

• Model recursive data structures with Rust enums (algebraic data types)

• Compare OCaml's type 'a node with Rust's enum Node<T>

• Understand ownership transfer vs borrowing for tree-like structures

• Practice stack-based iteration as an alternative to recursion

• See how flat_map provides a declarative recursive solution

🦀 The Rust Way

Three approaches:

flat_map recursive: Declarative, uses flat_map + pattern matching — clean but allocates intermediate Vecs

Stack-based: Explicit stack avoids recursion (Rust doesn't guarantee TCO), borrows data

Consuming/owned: Takes ownership via into_iter, zero cloning — most efficient when data isn't reused

Code Example

pub fn flatten<T: Clone>(list: &[Node<T>]) -> Vec<T> {
    list.iter()
        .flat_map(|node| match node {
            Node::One(x) => vec![x.clone()],
            Node::Many(xs) => flatten(xs),
        })
        .collect()
}

type 'a node = One of 'a | Many of 'a node list

let flatten lst =
  let rec aux acc = function
    | [] -> acc
    | One x :: t -> aux (x :: acc) t
    | Many xs :: t -> aux (aux acc xs) t
  in
  List.rev (aux [] lst)

Key Differences

Enum vs variant: Rust's enum Node<T> is the same concept as OCaml's variant type, but owns its data on the heap

No TCO guarantee: Rust doesn't optimize tail calls, so deep nesting could overflow; stack-based iteration is safer

Ownership matters: The consuming version (flatten_owned) avoids all cloning by taking ownership — impossible in GC languages where sharing is implicit

Clone bound: Borrowing versions need T: Clone to extract values; OCaml copies freely under GC

Memory layout: Rust's Vec<Node<T>> is a contiguous heap buffer; OCaml's list is a chain of heap-allocated cons cells

**Box for recursion:** Rust's Node::Many(Vec<Node<T>>) uses a Vec (not Box<Node>) because a Vec<Node> has a known size (pointer + length + capacity). OCaml's type 'a node = One of 'a | Many of 'a node list uses a GC-managed list directly.

**Clone bound:** flatten<T: Clone> requires cloning values extracted from the borrowed &Node<T>. OCaml's GC shares values without cloning.

Explicit stack: Rust's flatten_stack uses a manual Vec<&Node<T>> stack to avoid actual recursion, ensuring stack safety for deeply nested inputs. OCaml's TCO handles this automatically with tail-recursive accumulator style.

Ownership: Node::One(T) owns its value. Flattening requires moving or cloning values out of the tree — Rust forces this to be explicit.

OCaml Approach

Defines a recursive variant type 'a node = One of 'a | Many of 'a node list, then uses a tail-recursive helper with an accumulator to flatten. The GC handles all intermediate allocations.

Full Source

#![allow(clippy::all)]
//! # Flatten Nested List
//! OCaml 99 Problems #7 — Flatten an arbitrarily nested list structure.

/// Mirrors OCaml's `type 'a node = One of 'a | Many of 'a node list`.
/// Rust enum with owned data — no GC, explicit ownership.
#[derive(Debug, PartialEq, Clone)]
pub enum Node<T> {
    One(T),
    Many(Vec<Node<T>>),
}

/// Idiomatic Rust: use `flat_map` with recursive flattening.
/// Requires `Clone` because we extract values from a borrowed structure.
pub fn flatten<T: Clone>(list: &[Node<T>]) -> Vec<T> {
    list.iter()
        .flat_map(|node| match node {
            Node::One(x) => vec![x.clone()],
            Node::Many(xs) => flatten(xs),
        })
        .collect()
}

/// Functional style: tail-recursive with accumulator (mirrors OCaml's `aux acc`).
/// Uses a stack to avoid actual recursion — Rust doesn't guarantee TCO.
pub fn flatten_stack<T: Clone>(list: &[Node<T>]) -> Vec<T> {
    let mut result = Vec::new();
    // Explicit stack: process nodes right-to-left so result is in order
    let mut stack: Vec<&Node<T>> = list.iter().rev().collect();
    while let Some(node) = stack.pop() {
        match node {
            Node::One(x) => result.push(x.clone()),
            Node::Many(xs) => {
                for child in xs.iter().rev() {
                    stack.push(child);
                }
            }
        }
    }
    result
}

/// Consuming version: takes ownership, no cloning needed.
/// This is the most efficient Rust approach when you own the data.
pub fn flatten_owned<T>(list: Vec<Node<T>>) -> Vec<T> {
    let mut result = Vec::new();
    let mut stack: Vec<Node<T>> = list.into_iter().rev().collect();
    while let Some(node) = stack.pop() {
        match node {
            Node::One(x) => result.push(x),
            Node::Many(xs) => {
                for child in xs.into_iter().rev() {
                    stack.push(child);
                }
            }
        }
    }
    result
}

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

    #[test]
    fn test_nested() {
        let input = vec![
            One(1),
            Many(vec![One(2), Many(vec![One(3), One(4)])]),
            One(5),
        ];
        assert_eq!(flatten(&input), vec![1, 2, 3, 4, 5]);
        assert_eq!(flatten_stack(&input), vec![1, 2, 3, 4, 5]);
        assert_eq!(flatten_owned(input), vec![1, 2, 3, 4, 5]);
    }

    #[test]
    fn test_empty() {
        assert_eq!(flatten::<i32>(&[]), Vec::<i32>::new());
        assert_eq!(flatten_stack::<i32>(&[]), Vec::<i32>::new());
        assert_eq!(flatten_owned::<i32>(vec![]), Vec::<i32>::new());
    }

    #[test]
    fn test_single() {
        assert_eq!(flatten(&[One(42)]), vec![42]);
    }

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

    #[test]
    fn test_deeply_nested() {
        let input = vec![Many(vec![Many(vec![Many(vec![One(1)])])])];
        assert_eq!(flatten(&input), vec![1]);
    }

    #[test]
    fn test_empty_many() {
        let input: Vec<Node<i32>> = vec![Many(vec![]), One(1)];
        assert_eq!(flatten(&input), vec![1]);
    }
}

(* Flatten Nested List *)
(* OCaml 99 Problems #7 *)

(* Define nested list type *)
type 'a node =
  | One of 'a
  | Many of 'a node list

(* Flatten recursively *)
let flatten lst =
  let rec aux acc = function
    | [] -> acc
    | One x :: t -> aux (x :: acc) t
    | Many xs :: t -> aux (aux acc xs) t
  in
  List.rev (aux [] lst)

(* Tests *)
let () =
  assert (flatten [One 1; Many [One 2; Many [One 3; One 4]]; One 5] = [1; 2; 3; 4; 5]);
  assert (flatten [] = []);
  assert (flatten [One 1] = [1]);
  print_endline "✓ OCaml tests passed"

✓ Tests Rust test suite

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

    #[test]
    fn test_nested() {
        let input = vec![
            One(1),
            Many(vec![One(2), Many(vec![One(3), One(4)])]),
            One(5),
        ];
        assert_eq!(flatten(&input), vec![1, 2, 3, 4, 5]);
        assert_eq!(flatten_stack(&input), vec![1, 2, 3, 4, 5]);
        assert_eq!(flatten_owned(input), vec![1, 2, 3, 4, 5]);
    }

    #[test]
    fn test_empty() {
        assert_eq!(flatten::<i32>(&[]), Vec::<i32>::new());
        assert_eq!(flatten_stack::<i32>(&[]), Vec::<i32>::new());
        assert_eq!(flatten_owned::<i32>(vec![]), Vec::<i32>::new());
    }

    #[test]
    fn test_single() {
        assert_eq!(flatten(&[One(42)]), vec![42]);
    }

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

    #[test]
    fn test_deeply_nested() {
        let input = vec![Many(vec![Many(vec![Many(vec![One(1)])])])];
        assert_eq!(flatten(&input), vec![1]);
    }

    #[test]
    fn test_empty_many() {
        let input: Vec<Node<i32>> = vec![Many(vec![]), One(1)];
        assert_eq!(flatten(&input), vec![1]);
    }
}

Deep Comparison

Comparison: Flatten Nested List

OCaml — Recursive with accumulator

type 'a node = One of 'a | Many of 'a node list

let flatten lst =
  let rec aux acc = function
    | [] -> acc
    | One x :: t -> aux (x :: acc) t
    | Many xs :: t -> aux (aux acc xs) t
  in
  List.rev (aux [] lst)

Rust — Idiomatic (flat_map)

pub fn flatten<T: Clone>(list: &[Node<T>]) -> Vec<T> {
    list.iter()
        .flat_map(|node| match node {
            Node::One(x) => vec![x.clone()],
            Node::Many(xs) => flatten(xs),
        })
        .collect()
}

Rust — Stack-based (no recursion)

pub fn flatten_stack<T: Clone>(list: &[Node<T>]) -> Vec<T> {
    let mut result = Vec::new();
    let mut stack: Vec<&Node<T>> = list.iter().rev().collect();
    while let Some(node) = stack.pop() {
        match node {
            Node::One(x) => result.push(x.clone()),
            Node::Many(xs) => {
                for child in xs.iter().rev() {
                    stack.push(child);
                }
            }
        }
    }
    result
}

Comparison Table

Aspect	OCaml	Rust
Type definition	`type 'a node = One of 'a \\| Many of 'a node list`	`enum Node<T> { One(T), Many(Vec<Node<T>>) }`
Recursion	Tail-recursive with accumulator	Stack-based iteration (safer)
Memory	GC-managed cons cells	Owned `Vec` on heap
Copying	Implicit (GC)	Explicit `Clone` trait bound
Ownership	Shared by default	Must choose: borrow (`&`) or consume

Takeaways

Rust enums are algebraic data types — same expressive power as OCaml variants

Without guaranteed TCO, prefer explicit stacks for potentially deep recursion in Rust

The ownership system forces you to decide: clone data or consume it — OCaml hides this choice

flat_map gives the most readable recursive solution but allocates intermediate vectors

The consuming version (flatten_owned) is uniquely Rust — it's impossible in GC languages where data is always shared

Exercises

Implement flatten_depth that flattens a nested list structure only up to a specified depth d, leaving deeper nesting intact.

Write flatten_unique that flattens a list-of-lists and removes duplicates, preserving the first occurrence of each element.

Implement flatten_with that flattens a nested structure while applying a transformation function to each leaf element before collecting results.

Open Source Repos

functional-rust

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

Rust