262 Intermediate

Rose Tree — Multi-Way Tree with Fold

Trees

Tutorial Video

Text description (accessibility)

This video demonstrates the "Rose Tree — Multi-Way Tree with Fold" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Trees. Implement a rose tree (n-ary tree) where each node holds a value and a list of children. Key difference from OCaml: 1. **Data representation:** OCaml uses `Rose of 'a * 'a rose list` (variant with tuple); Rust uses a named struct with fields

Tutorial

The Problem

Implement a rose tree (n-ary tree) where each node holds a value and a list of children. Define a generic fold operation that processes the tree bottom-up, then derive size, depth, and string representation from fold.

🎯 Learning Outcomes

• Modeling n-ary trees with struct + Vec (vs OCaml's tuple-in-variant)

• Higher-order fold over recursive structures using trait objects (&dyn Fn)

• Deriving multiple operations from a single generic fold

• Understanding bottom-up vs top-down tree processing

🦀 The Rust Way

Rust uses a struct with a Vec<Rose<T>> for children (no Box needed since Vec already heap-allocates). The fold takes a &dyn Fn trait object for the combining function. Rust can't partially apply fold as elegantly, so derived functions are standalone.

Code Example

#[derive(Debug, Clone, PartialEq)]
pub struct Rose<T> {
    pub value: T,
    pub children: Vec<Rose<T>>,
}

impl<T> Rose<T> {
    pub fn fold<R>(&self, f: &dyn Fn(&T, Vec<R>) -> R) -> R {
        let child_results: Vec<R> = self.children.iter().map(|c| c.fold(f)).collect();
        f(&self.value, child_results)
    }
}

pub fn size<T>(tree: &Rose<T>) -> usize {
    tree.fold(&|_, sizes: Vec<usize>| 1 + sizes.iter().sum::<usize>())
}

type 'a rose = Rose of 'a * 'a rose list

let rec fold f (Rose (x, children)) =
  f x (List.map (fold f) children)

let size = fold (fun _ sizes -> 1 + List.fold_left (+) 0 sizes)
let depth = fold (fun _ depths -> 1 + List.fold_left max 0 depths)

let to_string = fold (fun x strs ->
  match strs with
  | [] -> x
  | _ -> x ^ "(" ^ String.concat "," strs ^ ")")

Key Differences

Data representation: OCaml uses Rose of 'a * 'a rose list (variant with tuple); Rust uses a named struct with fields

Higher-order functions: OCaml's fold returns a partially-applied function; Rust needs explicit function signatures

Children storage: OCaml uses a linked list; Rust uses Vec (better cache locality, random access)

Fold closure: OCaml passes closures freely; Rust uses &dyn Fn trait objects for recursive fold

OCaml Approach

OCaml wraps the value and children list in a single variant: Rose of 'a * 'a rose list. The fold function takes a combining function and recursively maps fold over children. Partial application makes size, depth, and to_string concise one-liners.

Full Source

#![allow(clippy::all)]
//! Rose Tree — Multi-Way Tree with Fold
//!
//! OCaml: `type 'a rose = Rose of 'a * 'a rose list`
//! Rust: `struct Rose<T> { value: T, children: Vec<Rose<T>> }`
//!
//! A rose tree (multi-way tree) where each node holds a value and
//! an arbitrary number of children. The fold operation processes
//! the tree bottom-up, combining child results with the node value.

//! A rose tree: each node has a value and zero or more children.
#[derive(Debug, Clone, PartialEq)]
pub struct Rose<T> {
    pub value: T,
    pub children: Vec<Rose<T>>,
}

impl<T> Rose<T> {
    /// Creates a leaf node (no children).
    pub fn leaf(value: T) -> Self {
        Rose {
            value,
            children: vec![],
        }
    }

    /// Creates a node with children.
    pub fn node(value: T, children: Vec<Rose<T>>) -> Self {
        Rose { value, children }
    }

    /// Recursive fold over the rose tree.
    ///
    /// OCaml: `let rec fold f (Rose (x, children)) = f x (List.map (fold f) children)`
    ///
    /// The function `f` receives the node value and a Vec of results
    /// from folding all children. This processes the tree bottom-up.
    pub fn fold<R>(&self, f: &dyn Fn(&T, Vec<R>) -> R) -> R {
        let child_results: Vec<R> = self.children.iter().map(|c| c.fold(f)).collect();
        f(&self.value, child_results)
    }
}

/// Counts total nodes in the tree.
/// OCaml: `let size = fold (fun _ sizes -> 1 + List.fold_left (+) 0 sizes)`
pub fn size<T>(tree: &Rose<T>) -> usize {
    tree.fold(&|_, sizes: Vec<usize>| 1 + sizes.iter().sum::<usize>())
}

/// Computes the depth (height) of the tree.
/// OCaml: `let depth = fold (fun _ depths -> 1 + List.fold_left max 0 depths)`
pub fn depth<T>(tree: &Rose<T>) -> usize {
    tree.fold(&|_, depths: Vec<usize>| 1 + depths.iter().copied().max().unwrap_or(0))
}

/// Converts tree to a string representation.
/// OCaml: `let to_string = fold (fun x strs -> match strs with | [] -> x | _ -> ...)`
pub fn to_string_repr(tree: &Rose<&str>) -> String {
    tree.fold(&|&x, strs: Vec<String>| {
        if strs.is_empty() {
            x.to_string()
        } else {
            format!("{}({})", x, strs.join(","))
        }
    })
}

/// Iterator-based approach: collects all values in pre-order.
pub fn preorder<T: Clone>(tree: &Rose<T>) -> Vec<T> {
    let mut result = vec![tree.value.clone()];
    for child in &tree.children {
        result.extend(preorder(child));
    }
    result
}

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

    fn sample_tree() -> Rose<&'static str> {
        Rose::node(
            "a",
            vec![
                Rose::node("b", vec![Rose::leaf("d"), Rose::leaf("e")]),
                Rose::node("c", vec![Rose::leaf("f")]),
            ],
        )
    }

    #[test]
    fn test_empty_leaf() {
        let tree = Rose::leaf(42);
        assert_eq!(size(&tree), 1);
        assert_eq!(depth(&tree), 1);
    }

    #[test]
    fn test_size() {
        let tree = sample_tree();
        assert_eq!(size(&tree), 6);
    }

    #[test]
    fn test_depth() {
        let tree = sample_tree();
        assert_eq!(depth(&tree), 3);
    }

    #[test]
    fn test_to_string() {
        let tree = sample_tree();
        assert_eq!(to_string_repr(&tree), "a(b(d,e),c(f))");
    }

    #[test]
    fn test_preorder() {
        let tree = sample_tree();
        assert_eq!(preorder(&tree), vec!["a", "b", "d", "e", "c", "f"]);
    }

    #[test]
    fn test_single_branch() {
        let tree = Rose::node("x", vec![Rose::node("y", vec![Rose::leaf("z")])]);
        assert_eq!(size(&tree), 3);
        assert_eq!(depth(&tree), 3);
        assert_eq!(to_string_repr(&tree), "x(y(z))");
    }
}

type 'a rose = Rose of 'a * 'a rose list

let rec fold f (Rose (x, children)) =
  f x (List.map (fold f) children)

let size = fold (fun _ sizes -> 1 + List.fold_left (+) 0 sizes)
let depth = fold (fun _ depths ->
  1 + List.fold_left max 0 depths)

let to_string = fold (fun x strs ->
  match strs with
  | [] -> x
  | _ -> x ^ "(" ^ String.concat "," strs ^ ")")

let () =
  let tree = Rose ("a", [
    Rose ("b", [Rose ("d", []); Rose ("e", [])]);
    Rose ("c", [Rose ("f", [])])
  ]) in
  assert (size tree = 6);
  assert (depth tree = 3);
  assert (to_string tree = "a(b(d,e),c(f))");
  print_endline "ok"

✓ Tests Rust test suite

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

    fn sample_tree() -> Rose<&'static str> {
        Rose::node(
            "a",
            vec![
                Rose::node("b", vec![Rose::leaf("d"), Rose::leaf("e")]),
                Rose::node("c", vec![Rose::leaf("f")]),
            ],
        )
    }

    #[test]
    fn test_empty_leaf() {
        let tree = Rose::leaf(42);
        assert_eq!(size(&tree), 1);
        assert_eq!(depth(&tree), 1);
    }

    #[test]
    fn test_size() {
        let tree = sample_tree();
        assert_eq!(size(&tree), 6);
    }

    #[test]
    fn test_depth() {
        let tree = sample_tree();
        assert_eq!(depth(&tree), 3);
    }

    #[test]
    fn test_to_string() {
        let tree = sample_tree();
        assert_eq!(to_string_repr(&tree), "a(b(d,e),c(f))");
    }

    #[test]
    fn test_preorder() {
        let tree = sample_tree();
        assert_eq!(preorder(&tree), vec!["a", "b", "d", "e", "c", "f"]);
    }

    #[test]
    fn test_single_branch() {
        let tree = Rose::node("x", vec![Rose::node("y", vec![Rose::leaf("z")])]);
        assert_eq!(size(&tree), 3);
        assert_eq!(depth(&tree), 3);
        assert_eq!(to_string_repr(&tree), "x(y(z))");
    }
}

Deep Comparison

OCaml vs Rust: Rose Tree — Multi-Way Tree with Fold

Side-by-Side Code

OCaml

type 'a rose = Rose of 'a * 'a rose list

let rec fold f (Rose (x, children)) =
  f x (List.map (fold f) children)

let size = fold (fun _ sizes -> 1 + List.fold_left (+) 0 sizes)
let depth = fold (fun _ depths -> 1 + List.fold_left max 0 depths)

let to_string = fold (fun x strs ->
  match strs with
  | [] -> x
  | _ -> x ^ "(" ^ String.concat "," strs ^ ")")

Rust (idiomatic)

#[derive(Debug, Clone, PartialEq)]
pub struct Rose<T> {
    pub value: T,
    pub children: Vec<Rose<T>>,
}

impl<T> Rose<T> {
    pub fn fold<R>(&self, f: &dyn Fn(&T, Vec<R>) -> R) -> R {
        let child_results: Vec<R> = self.children.iter().map(|c| c.fold(f)).collect();
        f(&self.value, child_results)
    }
}

pub fn size<T>(tree: &Rose<T>) -> usize {
    tree.fold(&|_, sizes: Vec<usize>| 1 + sizes.iter().sum::<usize>())
}

Rust (functional/recursive preorder)

pub fn preorder<T: Clone>(tree: &Rose<T>) -> Vec<T> {
    let mut result = vec![tree.value.clone()];
    for child in &tree.children {
        result.extend(preorder(child));
    }
    result
}

Type Signatures

Concept	OCaml	Rust
Rose tree	`'a rose`	`Rose<T>`
Fold	`('a -> 'b list -> 'b) -> 'a rose -> 'b`	`fn fold<R>(&self, f: &dyn Fn(&T, Vec<R>) -> R) -> R`
Children	`'a rose list`	`Vec<Rose<T>>`
Size	`'a rose -> int`	`fn size<T>(tree: &Rose<T>) -> usize`
Depth	`'a rose -> int`	`fn depth<T>(tree: &Rose<T>) -> usize`

Key Insights

Struct vs variant: OCaml packs value and children into a single variant constructor; Rust separates them into named struct fields, improving readability

Vec vs list for children: Rust's Vec gives O(1) random access and better cache locality than OCaml's linked list; both support iteration

Trait objects for recursive HOF: Rust needs &dyn Fn to pass closures through recursive fold calls; OCaml handles this transparently

Partial application gap: OCaml's let size = fold (fun ...) partially applies fold elegantly; Rust needs a standalone function wrapper

Collect pattern: OCaml's List.map naturally maps over children; Rust uses .iter().map().collect() — more explicit but equally clear

When to Use Each Style

Use fold-based derivation when: you have multiple operations over the same tree structure — write fold once, derive everything Use direct recursion when: you need fine-grained control over traversal order or want to short-circuit early

Exercises

Implement a map for the rose tree that transforms every node value using a provided function, analogous to Vec::iter().map().

Write a depth function that returns the maximum depth of the rose tree using a fold.

Implement flatten for the rose tree that returns all values in pre-order traversal order, and use fold as the underlying mechanism.

Open Source Repos

functional-rust

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

Rust