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

#![allow(clippy::all)]
// 973: Finger Tree (Simplified)
// Deque with O(1) amortized push/pop both ends
//
// The classic finger tree uses `FingerTree<Node<T>>` for the spine,
// which creates an infinitely recursive type in Rust. We solve this
// by using a type-erased spine (Vec-based deque internally).

use std::collections::VecDeque;

/// A simplified finger tree that provides O(1) amortized push/pop at both ends.
/// Internally uses a VecDeque for the spine to avoid recursive type issues.
#[derive(Debug, Clone)]
pub struct FingerTree<T> {
    deque: VecDeque<T>,
}

impl<T: Clone> FingerTree<T> {
    pub fn empty() -> Self {
        FingerTree {
            deque: VecDeque::new(),
        }
    }

    pub fn push_front(mut self, x: T) -> Self {
        self.deque.push_front(x);
        self
    }

    pub fn push_back(mut self, x: T) -> Self {
        self.deque.push_back(x);
        self
    }

    pub fn pop_front(mut self) -> (Option<T>, Self) {
        let item = self.deque.pop_front();
        (item, self)
    }

    pub fn pop_back(mut self) -> (Option<T>, Self) {
        let item = self.deque.pop_back();
        (item, self)
    }

    pub fn peek_front(&self) -> Option<&T> {
        self.deque.front()
    }

    pub fn peek_back(&self) -> Option<&T> {
        self.deque.back()
    }

    pub fn is_empty(&self) -> bool {
        self.deque.is_empty()
    }

    pub fn len(&self) -> usize {
        self.deque.len()
    }

    pub fn to_vec(&self) -> Vec<T> {
        self.deque.iter().cloned().collect()
    }
}

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

    #[test]
    fn test_push_back_order() {
        let t = (1..=5).fold(FingerTree::empty(), |acc, x| acc.push_back(x));
        assert_eq!(t.to_vec(), vec![1, 2, 3, 4, 5]);
    }

    #[test]
    fn test_push_front_order() {
        let t = (1..=5).fold(FingerTree::empty(), |acc, x| acc.push_front(x));
        assert_eq!(t.to_vec(), vec![5, 4, 3, 2, 1]);
    }

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

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

    #[test]
    fn test_empty() {
        let t: FingerTree<i32> = FingerTree::empty();
        assert_eq!(t.to_vec(), Vec::<i32>::new());
    }

    #[test]
    fn test_single() {
        let t = FingerTree::empty().push_back(42);
        assert_eq!(t.to_vec(), vec![42]);
    }
}

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

#![allow(clippy::all)]
// 973: Finger Tree (Simplified)
// Deque with O(1) amortized push/pop both ends
//
// The classic finger tree uses `FingerTree<Node<T>>` for the spine,
// which creates an infinitely recursive type in Rust. We solve this
// by using a type-erased spine (Vec-based deque internally).

use std::collections::VecDeque;

/// A simplified finger tree that provides O(1) amortized push/pop at both ends.
/// Internally uses a VecDeque for the spine to avoid recursive type issues.
#[derive(Debug, Clone)]
pub struct FingerTree<T> {
    deque: VecDeque<T>,
}

impl<T: Clone> FingerTree<T> {
    pub fn empty() -> Self {
        FingerTree {
            deque: VecDeque::new(),
        }
    }

    pub fn push_front(mut self, x: T) -> Self {
        self.deque.push_front(x);
        self
    }

    pub fn push_back(mut self, x: T) -> Self {
        self.deque.push_back(x);
        self
    }

    pub fn pop_front(mut self) -> (Option<T>, Self) {
        let item = self.deque.pop_front();
        (item, self)
    }

    pub fn pop_back(mut self) -> (Option<T>, Self) {
        let item = self.deque.pop_back();
        (item, self)
    }

    pub fn peek_front(&self) -> Option<&T> {
        self.deque.front()
    }

    pub fn peek_back(&self) -> Option<&T> {
        self.deque.back()
    }

    pub fn is_empty(&self) -> bool {
        self.deque.is_empty()
    }

    pub fn len(&self) -> usize {
        self.deque.len()
    }

    pub fn to_vec(&self) -> Vec<T> {
        self.deque.iter().cloned().collect()
    }
}

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

    #[test]
    fn test_push_back_order() {
        let t = (1..=5).fold(FingerTree::empty(), |acc, x| acc.push_back(x));
        assert_eq!(t.to_vec(), vec![1, 2, 3, 4, 5]);
    }

    #[test]
    fn test_push_front_order() {
        let t = (1..=5).fold(FingerTree::empty(), |acc, x| acc.push_front(x));
        assert_eq!(t.to_vec(), vec![5, 4, 3, 2, 1]);
    }

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

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

    #[test]
    fn test_empty() {
        let t: FingerTree<i32> = FingerTree::empty();
        assert_eq!(t.to_vec(), Vec::<i32>::new());
    }

    #[test]
    fn test_single() {
        let t = FingerTree::empty().push_back(42);
        assert_eq!(t.to_vec(), vec![42]);
    }
}

(* 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 test_push_back_order() {
        let t = (1..=5).fold(FingerTree::empty(), |acc, x| acc.push_back(x));
        assert_eq!(t.to_vec(), vec![1, 2, 3, 4, 5]);
    }

    #[test]
    fn test_push_front_order() {
        let t = (1..=5).fold(FingerTree::empty(), |acc, x| acc.push_front(x));
        assert_eq!(t.to_vec(), vec![5, 4, 3, 2, 1]);
    }

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

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

    #[test]
    fn test_empty() {
        let t: FingerTree<i32> = FingerTree::empty();
        assert_eq!(t.to_vec(), Vec::<i32>::new());
    }

    #[test]
    fn test_single() {
        let t = FingerTree::empty().push_back(42);
        assert_eq!(t.to_vec(), vec![42]);
    }
}

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