007: Flatten Nested List

Difficulty: 2 Level: Beginner Flatten an arbitrarily nested list structure into a flat list using a recursive enum.

The Problem This Solves

Real data is rarely flat. A file system has folders inside folders. A JSON document has arrays inside arrays. When you need to process every leaf value, you want a flat list — not a tree you have to recurse through manually every time. Without a proper recursive type and a `flatten` function, you end up writing the same recursive traversal everywhere, scattered across your codebase. The traversal logic leaks into business logic. Defining a `Node<T>` enum that can hold either a single value (`One`) or a list of further nodes (`Many`) lets you model the nesting once, and `flatten` handles the traversal cleanly.

The Intuition

Think of a Russian nesting doll. Each doll either contains a solid core (a `One`) or more dolls (a `Many`). Flattening means opening every doll until you've collected all the cores. In plain English: walk the list. When you see a `One(x)`, yield `x`. When you see a `Many(xs)`, recurse into `xs` and yield everything inside. Collect all yields into a flat `Vec`. This is a classic structural recursion — the function's shape mirrors the data's shape.

How It Works in Rust

#[derive(Debug, PartialEq, Clone)]
enum Node<T> {
 One(T),            // leaf: a single value
 Many(Vec<Node<T>>) // branch: more nodes inside
}

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

`flat_map` does two things at once: transform each element AND flatten one level. The `T: Clone` bound lets us extract owned values from borrowed nodes without consuming the input.

What This Unlocks

Recursive data processing — any tree-shaped data (ASTs, file trees, JSON) follows this same pattern.
Custom iterators — the recursive `flat_map` pattern is the foundation for writing tree-walking iterators.
Ownership discipline — choosing between `.clone()` here vs a consuming version (`into_iter`) teaches when copying pays off vs when ownership transfer is better.

Key Differences

Concept	OCaml	Rust
Recursive type	`type 'a node = One of 'a \	Many of 'a node list`	`enum Node<T> { One(T), Many(Vec<Node<T>>) }`
Heap allocation	Implicit (GC)	Explicit (`Vec` allocates on heap)
Value extraction	Free under GC	Requires `T: Clone` or ownership transfer
Tail-call safety	TCO guaranteed	No TCO — deep nesting can stack overflow
Traversal style	Tail-recursive helper with accumulator	`flat_map` + recursive call

// Flatten Nested List
// Rust translation from OCaml 99 Problems #7

// Define nested list type
#[derive(Debug, PartialEq, Clone)]
enum Node<T> {
    One(T),
    Many(Vec<Node<T>>),
}

// Flatten recursively
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()
}

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

    #[test]
    fn test_flatten() {
        use Node::*;
        assert_eq!(
            flatten(&[One(1), Many(vec![One(2), Many(vec![One(3), One(4)])]), One(5)]),
            vec![1, 2, 3, 4, 5]
        );
        assert_eq!(flatten::<i32>(&[]), Vec::<i32>::new());
        assert_eq!(flatten(&[One(1)]), vec![1]);
    }
}

fn main() {
    use Node::*;
    let nested = vec![One(1), Many(vec![One(2), One(3)])];
    println!("flatten(nested) = {:?}", flatten(&nested));
    println!("✓ Rust tests passed");
}

(* 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"

📊 Detailed Comparison

Comparison: Flatten Nested List

OCaml — Recursive with accumulator

🐪 Show OCaml equivalent

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

1. Rust enums are algebraic data types — same expressive power as OCaml variants 2. Without guaranteed TCO, prefer explicit stacks for potentially deep recursion in Rust 3. The ownership system forces you to decide: clone data or consume it — OCaml hides this choice 4. `flat_map` gives the most readable recursive solution but allocates intermediate vectors 5. The consuming version (`flatten_owned`) is uniquely Rust — it's impossible in GC languages where data is always shared