973 Advanced

973 Finger Tree

Functional Programming

Tutorial

The Problem

Explore the finger tree — a purely functional deque with O(1) amortized push/pop at both ends and O(log n) split/concat. The classic recursive type creates an infinitely-nested FingerTree<Node<T>> that Rust's type system cannot express directly. This implementation uses a VecDeque-backed simplified finger tree to demonstrate the interface while explaining the structural challenge.

🎯 Learning Outcomes

• Understand the finger tree structure: two "fingers" (small buffers at each end) + a lazy spine

• Recognize the recursive type problem: FingerTree<Node<T>> is not a finite type in Rust without boxing

• Implement a simplified finger tree API using VecDeque with consuming push/pop methods

• Apply consuming (value-taking) methods: push_front(self, x) -> Self returns a new tree

• Understand when VecDeque is sufficient vs when a true finger tree adds value

Code Example

//! 973: Finger Tree (Simplified)
//!
//! A persistent 2-3 finger tree providing a deque with O(1) amortized
//! `push_front` and `push_back` at both ends. This is a teaching-oriented
//! implementation that mirrors the classic 3-layer structure: two `Digit`
//! spines holding 1-4 elements each and a recursive inner tree of `Node`s.
//!
//! The spine is `Box<FingerTree<Node<T>>>`, so each level nests values one
//! type deeper than its parent; `Box` breaks what would otherwise be an
//! infinitely sized Rust type.

/// A digit holds 1 to 4 elements at one end of a `Deep` tree.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Digit<T> {
    /// A single element.
    One(T),
    /// Two elements.
    Two(T, T),
    /// Three elements.
    Three(T, T, T),
    /// Four elements (maximum before overflow).
    Four(T, T, T, T),
}

/// A node stored in the recursive spine; 2 or 3 elements.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Node<T> {
    /// A 2-element node.
    Node2(T, T),
    /// A 3-element node.
    Node3(T, T, T),
}

/// A persistent 2-3 finger tree.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum FingerTree<T> {
    /// An empty tree.
    Empty,
    /// A tree with a single element.
    Single(T),
    /// A tree with a left digit, recursive spine, and right digit.
    Deep(Digit<T>, Box<FingerTree<Node<T>>>, Digit<T>),
}

impl<T> Default for FingerTree<T> {
    fn default() -> Self {
        FingerTree::Empty
    }
}

impl<T> FingerTree<T> {
    /// Returns a new empty tree.
    pub fn new() -> Self {
        FingerTree::Empty
    }

    /// Returns `true` if the tree has no elements.
    pub fn is_empty(&self) -> bool {
        matches!(self, FingerTree::Empty)
    }

    /// Pushes `x` onto the front of the tree.
    pub fn push_front(self, x: T) -> Self {
        match self {
            FingerTree::Empty => FingerTree::Single(x),
            FingerTree::Single(y) => {
                FingerTree::Deep(Digit::One(x), Box::new(FingerTree::Empty), Digit::One(y))
            }
            FingerTree::Deep(left, spine, right) => match left {
                Digit::One(a) => FingerTree::Deep(Digit::Two(x, a), spine, right),
                Digit::Two(a, b) => FingerTree::Deep(Digit::Three(x, a, b), spine, right),
                Digit::Three(a, b, c) => FingerTree::Deep(Digit::Four(x, a, b, c), spine, right),
                Digit::Four(a, b, c, d) => {
                    let overflow = Node::Node3(b, c, d);
                    let spine = Box::new(spine.push_front(overflow));
                    FingerTree::Deep(Digit::Two(x, a), spine, right)
                }
            },
        }
    }

    /// Pushes `x` onto the back of the tree.
    pub fn push_back(self, x: T) -> Self {
        match self {
            FingerTree::Empty => FingerTree::Single(x),
            FingerTree::Single(y) => {
                FingerTree::Deep(Digit::One(y), Box::new(FingerTree::Empty), Digit::One(x))
            }
            FingerTree::Deep(left, spine, right) => match right {
                Digit::One(a) => FingerTree::Deep(left, spine, Digit::Two(a, x)),
                Digit::Two(a, b) => FingerTree::Deep(left, spine, Digit::Three(a, b, x)),
                Digit::Three(a, b, c) => FingerTree::Deep(left, spine, Digit::Four(a, b, c, x)),
                Digit::Four(a, b, c, d) => {
                    let overflow = Node::Node3(a, b, c);
                    let spine = Box::new(spine.push_back(overflow));
                    FingerTree::Deep(left, spine, Digit::Two(d, x))
                }
            },
        }
    }

    /// Flattens the tree into a `Vec` in left-to-right order.
    pub fn into_vec(self) -> Vec<T> {
        match self {
            FingerTree::Empty => Vec::new(),
            FingerTree::Single(x) => vec![x],
            FingerTree::Deep(left, spine, right) => {
                let mut out = left.into_vec();
                for node in spine.into_vec() {
                    out.extend(node.into_vec());
                }
                out.extend(right.into_vec());
                out
            }
        }
    }
}

impl<T> Digit<T> {
    /// Consumes the digit and returns its elements in left-to-right order.
    pub fn into_vec(self) -> Vec<T> {
        match self {
            Digit::One(a) => vec![a],
            Digit::Two(a, b) => vec![a, b],
            Digit::Three(a, b, c) => vec![a, b, c],
            Digit::Four(a, b, c, d) => vec![a, b, c, d],
        }
    }
}

impl<T> Node<T> {
    /// Consumes the node and returns its elements in left-to-right order.
    pub fn into_vec(self) -> Vec<T> {
        match self {
            Node::Node2(a, b) => vec![a, b],
            Node::Node3(a, b, c) => vec![a, b, c],
        }
    }
}

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

    #[test]
    fn empty_tree_flattens_to_empty_vec() {
        let t: FingerTree<i32> = FingerTree::new();
        assert!(t.is_empty());
        assert_eq!(t.into_vec(), Vec::<i32>::new());
    }

    #[test]
    fn single_tree_has_one_element() {
        let t = FingerTree::new().push_back(42);
        assert_eq!(t, FingerTree::Single(42));
    }

    #[test]
    fn mixed_pushes_preserve_order() {
        let t = FingerTree::new()
            .push_back(1)
            .push_back(2)
            .push_back(3)
            .push_front(0)
            .push_back(4)
            .push_front(-1);
        assert_eq!(t.into_vec(), vec![-1, 0, 1, 2, 3, 4]);
    }

    #[test]
    fn push_back_many_preserves_order() {
        let t = (1..=10).fold(FingerTree::new(), |acc, x| acc.push_back(x));
        assert_eq!(t.into_vec(), (1..=10).collect::<Vec<_>>());
    }

    #[test]
    fn push_front_many_reverses_insertion() {
        let t = (1..=10).fold(FingerTree::new(), |acc, x| acc.push_front(x));
        assert_eq!(t.into_vec(), (1..=10).rev().collect::<Vec<_>>());
    }

    #[test]
    fn long_sequence_forces_spine_growth() {
        let n = 100;
        let t = (0..n).fold(FingerTree::new(), |acc, x| acc.push_back(x));
        assert_eq!(t.into_vec(), (0..n).collect::<Vec<_>>());
    }

    #[test]
    fn interleaved_pushes_match_vecdeque() {
        use std::collections::VecDeque;

        let mut t = FingerTree::new();
        let mut expected: VecDeque<i32> = VecDeque::new();
        for i in 0..50 {
            if i % 2 == 0 {
                t = t.push_back(i);
                expected.push_back(i);
            } else {
                t = t.push_front(i);
                expected.push_front(i);
            }
        }
        assert_eq!(t.into_vec(), Vec::from(expected));
    }

    #[test]
    fn digit_into_vec_returns_elements_in_order() {
        assert_eq!(Digit::One(1).into_vec(), vec![1]);
        assert_eq!(Digit::Two(1, 2).into_vec(), vec![1, 2]);
        assert_eq!(Digit::Three(1, 2, 3).into_vec(), vec![1, 2, 3]);
        assert_eq!(Digit::Four(1, 2, 3, 4).into_vec(), vec![1, 2, 3, 4]);
    }

    #[test]
    fn node_into_vec_returns_elements_in_order() {
        assert_eq!(Node::Node2(1, 2).into_vec(), vec![1, 2]);
        assert_eq!(Node::Node3(1, 2, 3).into_vec(), vec![1, 2, 3]);
    }
}

(* 973: Finger Tree (Simplified) *)
(* Deque with O(1) amortized push/pop at both ends *)
(* Simplified: 2-3 finger tree with digit spines *)

(* Simplified finger tree as a 3-layer structure *)
(* Digit: 1-4 elements at each end *)
(* For teaching: we model a simplified version *)

type 'a digit =
  | One of 'a
  | Two of 'a * 'a
  | Three of 'a * 'a * 'a
  | Four of 'a * 'a * 'a * 'a

type 'a node =
  | Node2 of 'a * 'a
  | Node3 of 'a * 'a * 'a

type 'a finger_tree =
  | Empty
  | Single of 'a
  | Deep of 'a digit * 'a node finger_tree * 'a digit

(* Push to front *)
let push_front x = function
  | Empty -> Single x
  | Single y -> Deep (One x, Empty, One y)
  | Deep (One a, spine, r) -> Deep (Two (x, a), spine, r)
  | Deep (Two (a, b), spine, r) -> Deep (Three (x, a, b), spine, r)
  | Deep (Three (a, b, c), spine, r) -> Deep (Four (x, a, b, c), spine, r)
  | Deep (Four (a, b, c, d), spine, r) ->
    Deep (Two (x, a), push_front (Node3 (b, c, d)) spine, r)

(* Push to back *)
let push_back x = function
  | Empty -> Single x
  | Single y -> Deep (One y, Empty, One x)
  | Deep (l, spine, One a) -> Deep (l, spine, Two (a, x))
  | Deep (l, spine, Two (a, b)) -> Deep (l, spine, Three (a, b, x))
  | Deep (l, spine, Three (a, b, c)) -> Deep (l, spine, Four (a, b, c, x))
  | Deep (l, spine, Four (a, b, c, d)) ->
    Deep (l, push_back (Node3 (b, c, d)) spine, Two (a, x))

(* Convert to list (for testing) *)
let digit_to_list = function
  | One a -> [a]
  | Two (a, b) -> [a; b]
  | Three (a, b, c) -> [a; b; c]
  | Four (a, b, c, d) -> [a; b; c; d]

let node_to_list = function
  | Node2 (a, b) -> [a; b]
  | Node3 (a, b, c) -> [a; b; c]

let rec to_list = function
  | Empty -> []
  | Single x -> [x]
  | Deep (l, spine, r) ->
    digit_to_list l @
    List.concat_map node_to_list (to_list spine) @
    digit_to_list r

let () =
  let t = Empty in
  let t = push_back 1 t in
  let t = push_back 2 t in
  let t = push_back 3 t in
  let t = push_front 0 t in
  let t = push_back 4 t in
  let t = push_front (-1) t in

  let lst = to_list t in
  assert (lst = [-1; 0; 1; 2; 3; 4]);

  (* Build a longer sequence *)
  let t2 = List.fold_left (fun acc x -> push_back x acc) Empty [1;2;3;4;5;6;7;8;9;10] in
  assert (to_list t2 = [1;2;3;4;5;6;7;8;9;10]);

  Printf.printf "✓ All tests passed\n"

Key Differences

Aspect	Rust	OCaml
Recursive type	Cannot express `FingerTree<Node<T>>` without boxing	Natural recursive type in Haskell/OCaml
Consuming API	`fn push(self) -> Self`	Persistent `{ t with ... }`
Practical deque	`VecDeque` — O(1) amortized	Two-list or stdlib `Queue`
True finger tree	Requires `Box<...>` indirection	`Data.Sequence` (Haskell), `BatDeque` (OCaml)

Finger trees generalize to sequences supporting any measured monoid (e.g., size, priority, index) with O(log n) split/concat. They are the theoretical foundation of functional sequence libraries.

OCaml Approach

(* Simplified finger tree as two-list deque *)
type 'a finger_tree = {
  front: 'a list;
  back:  'a list;
}

let empty = { front = []; back = [] }

let push_front x t = { t with front = x :: t.front }
let push_back  x t = { t with back  = x :: t.back  }

let pop_front t = match t.front with
  | [] -> (match List.rev t.back with
    | [] -> None, t
    | x :: rest -> Some x, { front = rest; back = [] })
  | x :: rest -> Some x, { t with front = rest }

(* True finger tree: see Jane Street's Core.Deque or Batteries' Deque *)

OCaml's with record update syntax makes persistent push O(1). The two-list variant is the practical OCaml equivalent. For a true finger tree, Haskell's Data.Sequence or OCaml's BatDeque provides the full implementation.

Full Source

//! 973: Finger Tree (Simplified)
//!
//! A persistent 2-3 finger tree providing a deque with O(1) amortized
//! `push_front` and `push_back` at both ends. This is a teaching-oriented
//! implementation that mirrors the classic 3-layer structure: two `Digit`
//! spines holding 1-4 elements each and a recursive inner tree of `Node`s.
//!
//! The spine is `Box<FingerTree<Node<T>>>`, so each level nests values one
//! type deeper than its parent; `Box` breaks what would otherwise be an
//! infinitely sized Rust type.

/// A digit holds 1 to 4 elements at one end of a `Deep` tree.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Digit<T> {
    /// A single element.
    One(T),
    /// Two elements.
    Two(T, T),
    /// Three elements.
    Three(T, T, T),
    /// Four elements (maximum before overflow).
    Four(T, T, T, T),
}

/// A node stored in the recursive spine; 2 or 3 elements.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Node<T> {
    /// A 2-element node.
    Node2(T, T),
    /// A 3-element node.
    Node3(T, T, T),
}

/// A persistent 2-3 finger tree.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum FingerTree<T> {
    /// An empty tree.
    Empty,
    /// A tree with a single element.
    Single(T),
    /// A tree with a left digit, recursive spine, and right digit.
    Deep(Digit<T>, Box<FingerTree<Node<T>>>, Digit<T>),
}

impl<T> Default for FingerTree<T> {
    fn default() -> Self {
        FingerTree::Empty
    }
}

impl<T> FingerTree<T> {
    /// Returns a new empty tree.
    pub fn new() -> Self {
        FingerTree::Empty
    }

    /// Returns `true` if the tree has no elements.
    pub fn is_empty(&self) -> bool {
        matches!(self, FingerTree::Empty)
    }

    /// Pushes `x` onto the front of the tree.
    pub fn push_front(self, x: T) -> Self {
        match self {
            FingerTree::Empty => FingerTree::Single(x),
            FingerTree::Single(y) => {
                FingerTree::Deep(Digit::One(x), Box::new(FingerTree::Empty), Digit::One(y))
            }
            FingerTree::Deep(left, spine, right) => match left {
                Digit::One(a) => FingerTree::Deep(Digit::Two(x, a), spine, right),
                Digit::Two(a, b) => FingerTree::Deep(Digit::Three(x, a, b), spine, right),
                Digit::Three(a, b, c) => FingerTree::Deep(Digit::Four(x, a, b, c), spine, right),
                Digit::Four(a, b, c, d) => {
                    let overflow = Node::Node3(b, c, d);
                    let spine = Box::new(spine.push_front(overflow));
                    FingerTree::Deep(Digit::Two(x, a), spine, right)
                }
            },
        }
    }

    /// Pushes `x` onto the back of the tree.
    pub fn push_back(self, x: T) -> Self {
        match self {
            FingerTree::Empty => FingerTree::Single(x),
            FingerTree::Single(y) => {
                FingerTree::Deep(Digit::One(y), Box::new(FingerTree::Empty), Digit::One(x))
            }
            FingerTree::Deep(left, spine, right) => match right {
                Digit::One(a) => FingerTree::Deep(left, spine, Digit::Two(a, x)),
                Digit::Two(a, b) => FingerTree::Deep(left, spine, Digit::Three(a, b, x)),
                Digit::Three(a, b, c) => FingerTree::Deep(left, spine, Digit::Four(a, b, c, x)),
                Digit::Four(a, b, c, d) => {
                    let overflow = Node::Node3(a, b, c);
                    let spine = Box::new(spine.push_back(overflow));
                    FingerTree::Deep(left, spine, Digit::Two(d, x))
                }
            },
        }
    }

    /// Flattens the tree into a `Vec` in left-to-right order.
    pub fn into_vec(self) -> Vec<T> {
        match self {
            FingerTree::Empty => Vec::new(),
            FingerTree::Single(x) => vec![x],
            FingerTree::Deep(left, spine, right) => {
                let mut out = left.into_vec();
                for node in spine.into_vec() {
                    out.extend(node.into_vec());
                }
                out.extend(right.into_vec());
                out
            }
        }
    }
}

impl<T> Digit<T> {
    /// Consumes the digit and returns its elements in left-to-right order.
    pub fn into_vec(self) -> Vec<T> {
        match self {
            Digit::One(a) => vec![a],
            Digit::Two(a, b) => vec![a, b],
            Digit::Three(a, b, c) => vec![a, b, c],
            Digit::Four(a, b, c, d) => vec![a, b, c, d],
        }
    }
}

impl<T> Node<T> {
    /// Consumes the node and returns its elements in left-to-right order.
    pub fn into_vec(self) -> Vec<T> {
        match self {
            Node::Node2(a, b) => vec![a, b],
            Node::Node3(a, b, c) => vec![a, b, c],
        }
    }
}

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

    #[test]
    fn empty_tree_flattens_to_empty_vec() {
        let t: FingerTree<i32> = FingerTree::new();
        assert!(t.is_empty());
        assert_eq!(t.into_vec(), Vec::<i32>::new());
    }

    #[test]
    fn single_tree_has_one_element() {
        let t = FingerTree::new().push_back(42);
        assert_eq!(t, FingerTree::Single(42));
    }

    #[test]
    fn mixed_pushes_preserve_order() {
        let t = FingerTree::new()
            .push_back(1)
            .push_back(2)
            .push_back(3)
            .push_front(0)
            .push_back(4)
            .push_front(-1);
        assert_eq!(t.into_vec(), vec![-1, 0, 1, 2, 3, 4]);
    }

    #[test]
    fn push_back_many_preserves_order() {
        let t = (1..=10).fold(FingerTree::new(), |acc, x| acc.push_back(x));
        assert_eq!(t.into_vec(), (1..=10).collect::<Vec<_>>());
    }

    #[test]
    fn push_front_many_reverses_insertion() {
        let t = (1..=10).fold(FingerTree::new(), |acc, x| acc.push_front(x));
        assert_eq!(t.into_vec(), (1..=10).rev().collect::<Vec<_>>());
    }

    #[test]
    fn long_sequence_forces_spine_growth() {
        let n = 100;
        let t = (0..n).fold(FingerTree::new(), |acc, x| acc.push_back(x));
        assert_eq!(t.into_vec(), (0..n).collect::<Vec<_>>());
    }

    #[test]
    fn interleaved_pushes_match_vecdeque() {
        use std::collections::VecDeque;

        let mut t = FingerTree::new();
        let mut expected: VecDeque<i32> = VecDeque::new();
        for i in 0..50 {
            if i % 2 == 0 {
                t = t.push_back(i);
                expected.push_back(i);
            } else {
                t = t.push_front(i);
                expected.push_front(i);
            }
        }
        assert_eq!(t.into_vec(), Vec::from(expected));
    }

    #[test]
    fn digit_into_vec_returns_elements_in_order() {
        assert_eq!(Digit::One(1).into_vec(), vec![1]);
        assert_eq!(Digit::Two(1, 2).into_vec(), vec![1, 2]);
        assert_eq!(Digit::Three(1, 2, 3).into_vec(), vec![1, 2, 3]);
        assert_eq!(Digit::Four(1, 2, 3, 4).into_vec(), vec![1, 2, 3, 4]);
    }

    #[test]
    fn node_into_vec_returns_elements_in_order() {
        assert_eq!(Node::Node2(1, 2).into_vec(), vec![1, 2]);
        assert_eq!(Node::Node3(1, 2, 3).into_vec(), vec![1, 2, 3]);
    }
}

(* 973: Finger Tree (Simplified) *)
(* Deque with O(1) amortized push/pop at both ends *)
(* Simplified: 2-3 finger tree with digit spines *)

(* Simplified finger tree as a 3-layer structure *)
(* Digit: 1-4 elements at each end *)
(* For teaching: we model a simplified version *)

type 'a digit =
  | One of 'a
  | Two of 'a * 'a
  | Three of 'a * 'a * 'a
  | Four of 'a * 'a * 'a * 'a

type 'a node =
  | Node2 of 'a * 'a
  | Node3 of 'a * 'a * 'a

type 'a finger_tree =
  | Empty
  | Single of 'a
  | Deep of 'a digit * 'a node finger_tree * 'a digit

(* Push to front *)
let push_front x = function
  | Empty -> Single x
  | Single y -> Deep (One x, Empty, One y)
  | Deep (One a, spine, r) -> Deep (Two (x, a), spine, r)
  | Deep (Two (a, b), spine, r) -> Deep (Three (x, a, b), spine, r)
  | Deep (Three (a, b, c), spine, r) -> Deep (Four (x, a, b, c), spine, r)
  | Deep (Four (a, b, c, d), spine, r) ->
    Deep (Two (x, a), push_front (Node3 (b, c, d)) spine, r)

(* Push to back *)
let push_back x = function
  | Empty -> Single x
  | Single y -> Deep (One y, Empty, One x)
  | Deep (l, spine, One a) -> Deep (l, spine, Two (a, x))
  | Deep (l, spine, Two (a, b)) -> Deep (l, spine, Three (a, b, x))
  | Deep (l, spine, Three (a, b, c)) -> Deep (l, spine, Four (a, b, c, x))
  | Deep (l, spine, Four (a, b, c, d)) ->
    Deep (l, push_back (Node3 (b, c, d)) spine, Two (a, x))

(* Convert to list (for testing) *)
let digit_to_list = function
  | One a -> [a]
  | Two (a, b) -> [a; b]
  | Three (a, b, c) -> [a; b; c]
  | Four (a, b, c, d) -> [a; b; c; d]

let node_to_list = function
  | Node2 (a, b) -> [a; b]
  | Node3 (a, b, c) -> [a; b; c]

let rec to_list = function
  | Empty -> []
  | Single x -> [x]
  | Deep (l, spine, r) ->
    digit_to_list l @
    List.concat_map node_to_list (to_list spine) @
    digit_to_list r

let () =
  let t = Empty in
  let t = push_back 1 t in
  let t = push_back 2 t in
  let t = push_back 3 t in
  let t = push_front 0 t in
  let t = push_back 4 t in
  let t = push_front (-1) t in

  let lst = to_list t in
  assert (lst = [-1; 0; 1; 2; 3; 4]);

  (* Build a longer sequence *)
  let t2 = List.fold_left (fun acc x -> push_back x acc) Empty [1;2;3;4;5;6;7;8;9;10] in
  assert (to_list t2 = [1;2;3;4;5;6;7;8;9;10]);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn empty_tree_flattens_to_empty_vec() {
        let t: FingerTree<i32> = FingerTree::new();
        assert!(t.is_empty());
        assert_eq!(t.into_vec(), Vec::<i32>::new());
    }

    #[test]
    fn single_tree_has_one_element() {
        let t = FingerTree::new().push_back(42);
        assert_eq!(t, FingerTree::Single(42));
    }

    #[test]
    fn mixed_pushes_preserve_order() {
        let t = FingerTree::new()
            .push_back(1)
            .push_back(2)
            .push_back(3)
            .push_front(0)
            .push_back(4)
            .push_front(-1);
        assert_eq!(t.into_vec(), vec![-1, 0, 1, 2, 3, 4]);
    }

    #[test]
    fn push_back_many_preserves_order() {
        let t = (1..=10).fold(FingerTree::new(), |acc, x| acc.push_back(x));
        assert_eq!(t.into_vec(), (1..=10).collect::<Vec<_>>());
    }

    #[test]
    fn push_front_many_reverses_insertion() {
        let t = (1..=10).fold(FingerTree::new(), |acc, x| acc.push_front(x));
        assert_eq!(t.into_vec(), (1..=10).rev().collect::<Vec<_>>());
    }

    #[test]
    fn long_sequence_forces_spine_growth() {
        let n = 100;
        let t = (0..n).fold(FingerTree::new(), |acc, x| acc.push_back(x));
        assert_eq!(t.into_vec(), (0..n).collect::<Vec<_>>());
    }

    #[test]
    fn interleaved_pushes_match_vecdeque() {
        use std::collections::VecDeque;

        let mut t = FingerTree::new();
        let mut expected: VecDeque<i32> = VecDeque::new();
        for i in 0..50 {
            if i % 2 == 0 {
                t = t.push_back(i);
                expected.push_back(i);
            } else {
                t = t.push_front(i);
                expected.push_front(i);
            }
        }
        assert_eq!(t.into_vec(), Vec::from(expected));
    }

    #[test]
    fn digit_into_vec_returns_elements_in_order() {
        assert_eq!(Digit::One(1).into_vec(), vec![1]);
        assert_eq!(Digit::Two(1, 2).into_vec(), vec![1, 2]);
        assert_eq!(Digit::Three(1, 2, 3).into_vec(), vec![1, 2, 3]);
        assert_eq!(Digit::Four(1, 2, 3, 4).into_vec(), vec![1, 2, 3, 4]);
    }

    #[test]
    fn node_into_vec_returns_elements_in_order() {
        assert_eq!(Node::Node2(1, 2).into_vec(), vec![1, 2]);
        assert_eq!(Node::Node3(1, 2, 3).into_vec(), vec![1, 2, 3]);
    }
}

Deep Comparison

Finger Tree — Comparison

Core Insight

A finger tree stores digits (1-4 elements) at each end and a spine of Node elements. When digits overflow (4 items), they're packed into Node3 and pushed into the spine — which is itself a FingerTree<Node<T>>. This nesting (FingerTree<Node<FingerTree<Node<...>>>>) is the key insight. OCaml handles this type-level recursion implicitly; Rust requires Box at each recursive level to bound the size.

OCaml Approach

• type 'a finger_tree = Empty | Single of 'a | Deep of 'a digit * 'a node finger_tree * 'a digit

• The spine 'a node finger_tree is a finger_tree parameterized with node

• No explicit boxing — OCaml values are pointer-sized by default

• Pattern matching with function sugar

• push_front (Node3 (b,c,d)) spine — recurse into spine with packed nodes

Rust Approach

• FingerTree<T> with Box<FingerTree<Node<T>>> for spine

• Box required to give the recursive type a known size

• Each method call on spine is typed as FingerTree<Node<T>> — different type parameter

• match *l — deref Box to match inner Digit

• Consuming self in push_front/push_back (value semantics, functional style)

Comparison Table

Aspect	OCaml	Rust
Recursive type param	`'a node finger_tree`	`Box<FingerTree<Node<T>>>`
Boxing	Implicit (GC)	Explicit `Box`
Spine type	`'a node finger_tree`	`FingerTree<Node<T>>`
Pattern match Box	n/a	`match *l { Digit::One(a) => ... }`
Push into spine	`push_front (Node3 (b,c,d)) spine`	`spine.push_front(Node::Node3(b,c,d))`
Value vs reference	Return new value	Consume `self`, return new value
to_list	`digit_to_list @ node_to_list @ ...`	`Vec` + extend

Exercises

Implement a true two-finger tree: struct TwoFinger<T> { front: Vec<T>, spine: VecDeque<T>, back: Vec<T> } — O(1) push/pop at both ends when fingers are small.

Implement split_at(self, idx: usize) -> (Self, Self) for the simplified version.

Implement append_all(self, items: impl IntoIterator<Item=T>) -> Self efficiently.

Show how a finger tree with a Size monoid supports O(log n) random access by index.

Implement a map method: map<U: Clone, F: Fn(T) -> U>(self, f: F) -> FingerTree<U>.

Open Source Repos

functional-rust

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

Rust