866 Fundamental

Foldable Trait

Functional Programming

Tutorial

The Problem

Folding — reducing a collection to a single value by repeatedly applying a combining function — is the most general way to consume a data structure. sum, product, max, min, to_vec, count, any, all, find are all specific instances of fold. A Foldable trait abstracts this: any type that supports fold_left and fold_right can be reduced to any type. This powers generic algorithms that work over trees, lists, and custom containers without knowing the specific structure. OCaml's List.fold_left and Haskell's Foldable typeclass are the canonical implementations. Rust's Iterator::fold is the iterator-based equivalent.

🎯 Learning Outcomes

• Define the Foldable trait with fold_left and fold_right methods

• Implement for List<T> (linked list) and Tree<T> (binary tree)

• Derive useful operations from fold: sum, length, to_vec, max, min, any, all

• Understand left vs. right fold: different associativity, different stack behavior

• Recognize that fold_right is naturally recursive; fold_left is tail-recursive for lists

Code Example

trait Foldable {
    type Item;
    fn fold_left<B, F: FnMut(B, &Self::Item) -> B>(&self, init: B, f: F) -> B;
    fn fold_right<B, F: FnMut(&Self::Item, B) -> B>(&self, init: B, f: F) -> B;
}

module type FOLDABLE = sig
  type 'a t
  val fold_left : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b
  val fold_right : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b
end

Key Differences

Aspect	Rust	OCaml
Trait/signature	`trait Foldable`	`module type FOLDABLE`
Associated type	`type Item`	`type 'a t` parameterized
Generic over F	`<C: Foldable<Item=i32>>`	First-class module `(module FOLDABLE)`
List fold order	`fold_left` is left-to-right	Same
Tree fold order	Implementation-defined	Same
Stack safety	`fold_right` recurses	OCaml TCO for tail-recursive folds

OCaml Approach

OCaml's Foldable as a module signature: module type FOLDABLE = sig type 'a t; val fold_left : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b; val fold_right : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b end. Derived operations: let sum (module F: FOLDABLE with type 'a t = int t) = F.fold_left (+) 0. OCaml's List.fold_left and Array.fold_left implement this for their respective types. The Tree implementation uses pattern matching: Leaf -> acc, Node(l, v, r) -> fold_right f r (f (fold_right f l acc) v).

Full Source

#![allow(clippy::all)]
// Example 067: Foldable Trait
// Custom fold over tree/list structures

// Foldable trait
trait Foldable {
    type Item;
    fn fold_left<B, F: FnMut(B, &Self::Item) -> B>(&self, init: B, f: F) -> B;
    fn fold_right<B, F: FnMut(&Self::Item, B) -> B>(&self, init: B, f: F) -> B;

    // Derived operations
    fn to_vec(&self) -> Vec<Self::Item>
    where
        Self::Item: Clone,
    {
        self.fold_right(Vec::new(), |x, mut acc| {
            acc.insert(0, x.clone());
            acc
        })
    }

    fn length(&self) -> usize {
        self.fold_left(0, |acc, _| acc + 1)
    }
}

// Approach 1: Foldable for custom list
#[derive(Debug)]
enum MyList<T> {
    Nil,
    Cons(T, Box<MyList<T>>),
}

impl<T> MyList<T> {
    fn cons(x: T, xs: MyList<T>) -> Self {
        MyList::Cons(x, Box::new(xs))
    }
}

impl<T> Foldable for MyList<T> {
    type Item = T;
    fn fold_left<B, F: FnMut(B, &T) -> B>(&self, init: B, mut f: F) -> B {
        let mut acc = init;
        let mut current = self;
        loop {
            match current {
                MyList::Nil => return acc,
                MyList::Cons(x, xs) => {
                    acc = f(acc, x);
                    current = xs;
                }
            }
        }
    }
    fn fold_right<B, F: FnMut(&T, B) -> B>(&self, init: B, mut f: F) -> B {
        // Collect references, then fold from right
        let mut items = Vec::new();
        let mut current = self;
        loop {
            match current {
                MyList::Nil => break,
                MyList::Cons(x, xs) => {
                    items.push(x);
                    current = xs;
                }
            }
        }
        let mut acc = init;
        for x in items.into_iter().rev() {
            acc = f(x, acc);
        }
        acc
    }
}

// Approach 2: Foldable for binary tree
#[derive(Debug)]
enum Tree<T> {
    Leaf,
    Node(Box<Tree<T>>, T, Box<Tree<T>>),
}

impl<T> Tree<T> {
    fn node(l: Tree<T>, v: T, r: Tree<T>) -> Self {
        Tree::Node(Box::new(l), v, Box::new(r))
    }
}

impl<T> Foldable for Tree<T> {
    type Item = T;
    fn fold_left<B, F: FnMut(B, &T) -> B>(&self, init: B, mut f: F) -> B {
        // In-order traversal using explicit stack
        let mut stack = Vec::new();
        let mut current = self;
        let mut acc = init;

        enum Action<'a, T> {
            Visit(&'a Tree<T>),
            Process(&'a T),
        }

        stack.push(Action::Visit(current));
        while let Some(action) = stack.pop() {
            match action {
                Action::Visit(Tree::Leaf) => {}
                Action::Visit(Tree::Node(l, v, r)) => {
                    stack.push(Action::Visit(r));
                    stack.push(Action::Process(v));
                    stack.push(Action::Visit(l));
                }
                Action::Process(v) => {
                    acc = f(acc, v);
                }
            }
        }
        acc
    }
    fn fold_right<B, F: FnMut(&T, B) -> B>(&self, init: B, mut f: F) -> B {
        // Collect in-order, then fold from right
        let mut items = Vec::new();
        fn collect<'a, T>(tree: &'a Tree<T>, items: &mut Vec<&'a T>) {
            match tree {
                Tree::Leaf => {}
                Tree::Node(l, v, r) => {
                    collect(l, items);
                    items.push(v);
                    collect(r, items);
                }
            }
        }
        collect(self, &mut items);
        let mut acc = init;
        for x in items.into_iter().rev() {
            acc = f(x, acc);
        }
        acc
    }
}

// Approach 3: Generic functions over any Foldable
fn sum<F: Foldable<Item = i32>>(foldable: &F) -> i32 {
    foldable.fold_left(0, |acc, x| acc + x)
}

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

    fn sample_list() -> MyList<i32> {
        MyList::cons(1, MyList::cons(2, MyList::cons(3, MyList::Nil)))
    }

    fn sample_tree() -> Tree<i32> {
        Tree::node(
            Tree::node(Tree::Leaf, 1, Tree::Leaf),
            2,
            Tree::node(Tree::Leaf, 3, Tree::Leaf),
        )
    }

    #[test]
    fn test_list_fold_left_sum() {
        assert_eq!(sum(&sample_list()), 6);
    }

    #[test]
    fn test_list_length() {
        assert_eq!(sample_list().length(), 3);
    }

    #[test]
    fn test_list_to_vec() {
        assert_eq!(sample_list().to_vec(), vec![1, 2, 3]);
    }

    #[test]
    fn test_tree_fold_left_sum() {
        assert_eq!(sum(&sample_tree()), 6);
    }

    #[test]
    fn test_tree_length() {
        assert_eq!(sample_tree().length(), 3);
    }

    #[test]
    fn test_tree_to_vec() {
        assert_eq!(sample_tree().to_vec(), vec![1, 2, 3]);
    }

    #[test]
    fn test_empty() {
        assert_eq!(sum(&MyList::<i32>::Nil), 0);
        assert_eq!(sum(&Tree::<i32>::Leaf), 0);
    }
}

(* Example 067: Foldable Trait *)
(* Custom fold over tree/list structures *)

module type FOLDABLE = sig
  type 'a t
  val fold_left : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b
  val fold_right : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b
end

(* Approach 1: Foldable for custom list *)
type 'a mylist = Nil | Cons of 'a * 'a mylist

module MyListFoldable : FOLDABLE with type 'a t = 'a mylist = struct
  type 'a t = 'a mylist
  let rec fold_left f acc = function
    | Nil -> acc
    | Cons (x, xs) -> fold_left f (f acc x) xs
  let rec fold_right f lst acc = match lst with
    | Nil -> acc
    | Cons (x, xs) -> f x (fold_right f xs acc)
end

(* Approach 2: Foldable for binary tree *)
type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree

module TreeFoldable : FOLDABLE with type 'a t = 'a tree = struct
  type 'a t = 'a tree
  let rec fold_left f acc = function
    | Leaf -> acc
    | Node (l, v, r) ->
      let acc = fold_left f acc l in
      let acc = f acc v in
      fold_left f acc r
  let rec fold_right f tree acc = match tree with
    | Leaf -> acc
    | Node (l, v, r) ->
      fold_right f l (f v (fold_right f r acc))
end

(* Approach 3: Derived operations from fold *)
let to_list (type a) (module F : FOLDABLE with type 'x t = a) xs =
  F.fold_right (fun x acc -> x :: acc) xs []

let sum (type a) (module F : FOLDABLE with type 'x t = a) xs =
  F.fold_left (fun acc x -> acc + x) 0 xs

let length (type a) (module F : FOLDABLE with type 'x t = a) xs =
  F.fold_left (fun acc _ -> acc + 1) 0 xs

let () =
  let lst = Cons (1, Cons (2, Cons (3, Nil))) in
  assert (MyListFoldable.fold_left (+) 0 lst = 6);
  assert (MyListFoldable.fold_right (fun x acc -> x :: acc) lst [] = [1; 2; 3]);

  let tree = Node (Node (Leaf, 1, Leaf), 2, Node (Leaf, 3, Leaf)) in
  assert (TreeFoldable.fold_left (+) 0 tree = 6);
  assert (TreeFoldable.fold_right (fun x acc -> x :: acc) tree [] = [1; 2; 3]);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    fn sample_list() -> MyList<i32> {
        MyList::cons(1, MyList::cons(2, MyList::cons(3, MyList::Nil)))
    }

    fn sample_tree() -> Tree<i32> {
        Tree::node(
            Tree::node(Tree::Leaf, 1, Tree::Leaf),
            2,
            Tree::node(Tree::Leaf, 3, Tree::Leaf),
        )
    }

    #[test]
    fn test_list_fold_left_sum() {
        assert_eq!(sum(&sample_list()), 6);
    }

    #[test]
    fn test_list_length() {
        assert_eq!(sample_list().length(), 3);
    }

    #[test]
    fn test_list_to_vec() {
        assert_eq!(sample_list().to_vec(), vec![1, 2, 3]);
    }

    #[test]
    fn test_tree_fold_left_sum() {
        assert_eq!(sum(&sample_tree()), 6);
    }

    #[test]
    fn test_tree_length() {
        assert_eq!(sample_tree().length(), 3);
    }

    #[test]
    fn test_tree_to_vec() {
        assert_eq!(sample_tree().to_vec(), vec![1, 2, 3]);
    }

    #[test]
    fn test_empty() {
        assert_eq!(sum(&MyList::<i32>::Nil), 0);
        assert_eq!(sum(&Tree::<i32>::Leaf), 0);
    }
}

Deep Comparison

Comparison: Foldable Trait

Foldable Interface

OCaml:

module type FOLDABLE = sig
  type 'a t
  val fold_left : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b
  val fold_right : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b
end

Rust:

trait Foldable {
    type Item;
    fn fold_left<B, F: FnMut(B, &Self::Item) -> B>(&self, init: B, f: F) -> B;
    fn fold_right<B, F: FnMut(&Self::Item, B) -> B>(&self, init: B, f: F) -> B;
}

Tree Implementation

OCaml:

let rec fold_left f acc = function
  | Leaf -> acc
  | Node (l, v, r) ->
    let acc = fold_left f acc l in
    let acc = f acc v in
    fold_left f acc r

Rust:

fn fold_left<B, F: FnMut(B, &T) -> B>(&self, init: B, mut f: F) -> B {
    match self {
        Tree::Leaf => init,
        Tree::Node(l, v, r) => {
            let acc = l.fold_left(init, &mut f);
            let acc = f(acc, v);
            r.fold_left(acc, f)
        }
    }
}

Generic Sum

OCaml:

let sum (type a) (module F : FOLDABLE with type 'x t = a) xs =
  F.fold_left (fun acc x -> acc + x) 0 xs

Rust:

fn sum<F: Foldable<Item = i32>>(foldable: &F) -> i32 {
    foldable.fold_left(0, |acc, x| acc + x)
}

Exercises

Implement Foldable for a custom binary tree and derive sum, length, max, and in_order_list from the fold.

Implement fold_right for List<T> and verify that fold_right(cons, [], xs) == xs.clone().

Show that to_vec using fold_left and fold_right produce reversed lists — use this to implement reverse.

Implement any and all as early-exit folds using try_fold on Rust's Iterator trait.

Measure the stack depth of fold_right on a list of 100,000 elements and compare with the stack-safe fold_left version.

Open Source Repos

functional-rust

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

Rust