081 Advanced

081 — Difference List

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "081 — Difference List" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. Implement a difference list data structure that provides O(1) append by representing a list as a function `Vec<T> -> Vec<T>`. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Implement a difference list data structure that provides O(1) append by representing a list as a function Vec<T> -> Vec<T>. Compare with OCaml's natural 'a list -> 'a list function type, and also show a practical VecBuilder alternative that amortizes allocation across many append operations.

🎯 Learning Outcomes

• Understand difference lists as function composition rather than data concatenation

• Use Box<dyn FnOnce(Vec<T>) -> Vec<T>) to store an owned, one-shot closure

• Recognise why T: 'static is required when boxing a closure that captures T

• See that append is just function composition: |v| f(g(v))

• Compare with VecBuilder which trades theoretical elegance for practical clarity

• Map Rust's heap-boxed closure to OCaml's native first-class 'a list -> 'a list

Code Example

#![allow(clippy::all)]
/// Difference List — O(1) Append
///
/// Ownership insight: A difference list is a function Vec<T> -> Vec<T>.
/// In Rust, we use Box<dyn FnOnce> since each function is consumed on use.

/// A difference list wraps a function that prepends elements to a tail
pub struct DList<T> {
    f: Box<dyn FnOnce(Vec<T>) -> Vec<T>>,
}

impl<T: 'static> DList<T> {
    pub fn empty() -> Self {
        DList { f: Box::new(|v| v) }
    }

    pub fn singleton(x: T) -> Self {
        DList {
            f: Box::new(move |mut v| {
                v.insert(0, x);
                v
            }),
        }
    }

    pub fn from_vec(mut items: Vec<T>) -> Self {
        DList {
            f: Box::new(move |mut v| {
                items.append(&mut v);
                items
            }),
        }
    }

    /// O(1) append — just composes two functions
    pub fn append(self, other: DList<T>) -> Self {
        DList {
            f: Box::new(move |v| (self.f)((other.f)(v))),
        }
    }

    /// Materialize the difference list into a Vec
    pub fn to_vec(self) -> Vec<T> {
        (self.f)(Vec::new())
    }
}

/// Version 2: Simple vec-based builder (practical alternative)
pub struct VecBuilder<T> {
    chunks: Vec<Vec<T>>,
}

impl<T> VecBuilder<T> {
    pub fn new() -> Self {
        VecBuilder { chunks: vec![] }
    }

    pub fn push_vec(&mut self, v: Vec<T>) {
        self.chunks.push(v);
    }

    pub fn build(self) -> Vec<T> {
        let total: usize = self.chunks.iter().map(|c| c.len()).sum();
        let mut result = Vec::with_capacity(total);
        for mut chunk in self.chunks {
            result.append(&mut chunk);
        }
        result
    }
}

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

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

    #[test]
    fn test_singleton() {
        assert_eq!(DList::singleton(42).to_vec(), vec![42]);
    }

    #[test]
    fn test_append() {
        let a = DList::from_vec(vec![1, 2, 3]);
        let b = DList::from_vec(vec![4, 5, 6]);
        let c = DList::singleton(7);
        assert_eq!(a.append(b).append(c).to_vec(), vec![1, 2, 3, 4, 5, 6, 7]);
    }

    #[test]
    fn test_vec_builder() {
        let mut b = VecBuilder::new();
        b.push_vec(vec![1, 2]);
        b.push_vec(vec![3, 4]);
        assert_eq!(b.build(), vec![1, 2, 3, 4]);
    }

    #[test]
    fn test_many_appends() {
        let mut dl = DList::empty();
        for i in 0..100 {
            dl = dl.append(DList::singleton(i));
        }
        let v = dl.to_vec();
        assert_eq!(v.len(), 100);
        assert_eq!(v[0], 0);
        assert_eq!(v[99], 99);
    }
}

(* Difference List — O(1) Append *)

(* A difference list is a function from list to list *)
type 'a dlist = 'a list -> 'a list

let empty : 'a dlist = Fun.id
let singleton x : 'a dlist = fun rest -> x :: rest
let append (a : 'a dlist) (b : 'a dlist) : 'a dlist = fun rest -> a (b rest)
let of_list lst : 'a dlist = fun rest -> lst @ rest
let to_list (dl : 'a dlist) = dl []

let () =
  let a = of_list [1;2;3] in
  let b = of_list [4;5;6] in
  let c = singleton 7 in
  let result = append (append a b) c |> to_list in
  assert (result = [1;2;3;4;5;6;7])

Key Differences

Aspect	Rust	OCaml
Type	`Box<dyn FnOnce(Vec<T>) -> Vec<T>>`	`'a list -> 'a list`
Lifetime	`T: 'static` required	No annotation needed
`append`	Nested closure in `Box::new`	`fun rest -> a (b rest)`
Reuse	One-shot (`FnOnce`)	Multi-use (function values)
Practical alt	`VecBuilder`	`Buffer` module
Code length	~50 lines	~8 lines

The FnOnce constraint is the key difference: Rust closures that capture owned values can only be called once. OCaml closures capture by reference and can be called multiple times. For a difference list used only to materialize once, FnOnce is correct; for a reusable combinator, Fn (requiring Clone) would be needed.

OCaml Approach

OCaml represents a difference list as a plain type alias type 'a dlist = 'a list -> 'a list. empty is Fun.id; singleton x is fun rest -> x :: rest; append a b is fun rest -> a (b rest). No boxing or lifetime annotation needed — functions are first-class values with reference-counted closures. The OCaml version is trivially three lines. Both representations are semantically identical: a difference list is a partially applied list-building function.

Full Source

#![allow(clippy::all)]
/// Difference List — O(1) Append
///
/// Ownership insight: A difference list is a function Vec<T> -> Vec<T>.
/// In Rust, we use Box<dyn FnOnce> since each function is consumed on use.

/// A difference list wraps a function that prepends elements to a tail
pub struct DList<T> {
    f: Box<dyn FnOnce(Vec<T>) -> Vec<T>>,
}

impl<T: 'static> DList<T> {
    pub fn empty() -> Self {
        DList { f: Box::new(|v| v) }
    }

    pub fn singleton(x: T) -> Self {
        DList {
            f: Box::new(move |mut v| {
                v.insert(0, x);
                v
            }),
        }
    }

    pub fn from_vec(mut items: Vec<T>) -> Self {
        DList {
            f: Box::new(move |mut v| {
                items.append(&mut v);
                items
            }),
        }
    }

    /// O(1) append — just composes two functions
    pub fn append(self, other: DList<T>) -> Self {
        DList {
            f: Box::new(move |v| (self.f)((other.f)(v))),
        }
    }

    /// Materialize the difference list into a Vec
    pub fn to_vec(self) -> Vec<T> {
        (self.f)(Vec::new())
    }
}

/// Version 2: Simple vec-based builder (practical alternative)
pub struct VecBuilder<T> {
    chunks: Vec<Vec<T>>,
}

impl<T> VecBuilder<T> {
    pub fn new() -> Self {
        VecBuilder { chunks: vec![] }
    }

    pub fn push_vec(&mut self, v: Vec<T>) {
        self.chunks.push(v);
    }

    pub fn build(self) -> Vec<T> {
        let total: usize = self.chunks.iter().map(|c| c.len()).sum();
        let mut result = Vec::with_capacity(total);
        for mut chunk in self.chunks {
            result.append(&mut chunk);
        }
        result
    }
}

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

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

    #[test]
    fn test_singleton() {
        assert_eq!(DList::singleton(42).to_vec(), vec![42]);
    }

    #[test]
    fn test_append() {
        let a = DList::from_vec(vec![1, 2, 3]);
        let b = DList::from_vec(vec![4, 5, 6]);
        let c = DList::singleton(7);
        assert_eq!(a.append(b).append(c).to_vec(), vec![1, 2, 3, 4, 5, 6, 7]);
    }

    #[test]
    fn test_vec_builder() {
        let mut b = VecBuilder::new();
        b.push_vec(vec![1, 2]);
        b.push_vec(vec![3, 4]);
        assert_eq!(b.build(), vec![1, 2, 3, 4]);
    }

    #[test]
    fn test_many_appends() {
        let mut dl = DList::empty();
        for i in 0..100 {
            dl = dl.append(DList::singleton(i));
        }
        let v = dl.to_vec();
        assert_eq!(v.len(), 100);
        assert_eq!(v[0], 0);
        assert_eq!(v[99], 99);
    }
}

(* Difference List — O(1) Append *)

(* A difference list is a function from list to list *)
type 'a dlist = 'a list -> 'a list

let empty : 'a dlist = Fun.id
let singleton x : 'a dlist = fun rest -> x :: rest
let append (a : 'a dlist) (b : 'a dlist) : 'a dlist = fun rest -> a (b rest)
let of_list lst : 'a dlist = fun rest -> lst @ rest
let to_list (dl : 'a dlist) = dl []

let () =
  let a = of_list [1;2;3] in
  let b = of_list [4;5;6] in
  let c = singleton 7 in
  let result = append (append a b) c |> to_list in
  assert (result = [1;2;3;4;5;6;7])

✓ Tests Rust test suite

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

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

    #[test]
    fn test_singleton() {
        assert_eq!(DList::singleton(42).to_vec(), vec![42]);
    }

    #[test]
    fn test_append() {
        let a = DList::from_vec(vec![1, 2, 3]);
        let b = DList::from_vec(vec![4, 5, 6]);
        let c = DList::singleton(7);
        assert_eq!(a.append(b).append(c).to_vec(), vec![1, 2, 3, 4, 5, 6, 7]);
    }

    #[test]
    fn test_vec_builder() {
        let mut b = VecBuilder::new();
        b.push_vec(vec![1, 2]);
        b.push_vec(vec![3, 4]);
        assert_eq!(b.build(), vec![1, 2, 3, 4]);
    }

    #[test]
    fn test_many_appends() {
        let mut dl = DList::empty();
        for i in 0..100 {
            dl = dl.append(DList::singleton(i));
        }
        let v = dl.to_vec();
        assert_eq!(v.len(), 100);
        assert_eq!(v[0], 0);
        assert_eq!(v[99], 99);
    }
}

Deep Comparison

Difference List — Comparison

Core Insight

A difference list represents a list as a function, enabling O(1) append via function composition. In OCaml, functions are first-class and GC-managed. In Rust, closures must be boxed (Box<dyn FnOnce>) and are consumed on use.

OCaml Approach

• type 'a dlist = 'a list -> 'a list — just a type alias for a function

• let append a b = fun rest -> a (b rest) — composition is trivial

• Fun.id for empty list

• Functions are freely copyable/shareable via GC

Rust Approach

• Box<dyn FnOnce(Vec<T>) -> Vec<T>> — heap-allocated, consumed on call

• Each DList can only be used once (FnOnce, not Fn)

• move closures capture ownership of data

• Alternative: VecBuilder collects chunks for later assembly

Comparison Table

Aspect	OCaml	Rust
Type	`'a list -> 'a list`	`Box<dyn FnOnce(Vec<T>) -> Vec<T>>`
Append	Function composition	Box composition (heap alloc)
Reuse	Freely reusable	Single-use (FnOnce)
Empty	`Fun.id`	`Box::new(identity)`
Overhead	GC for closures	Box allocation per compose

Learner Notes

• Difference lists are more natural in GC languages where functions are cheap

• In Rust, VecBuilder (collecting chunks) is often more practical

• FnOnce means each DList is consumed when converted to Vec

• The 'static bound on T is needed because closures must own their data

Exercises

Change DList to use Fn instead of FnOnce by requiring T: Clone. Verify that the same DList can be materialized multiple times.

Implement concat: Vec<DList<T>> -> DList<T> that folds a vector of difference lists using append.

Benchmark DList::append + to_vec vs direct Vec::extend for appending 10,000 lists of 100 elements each.

Implement a map<U, F: Fn(T) -> U>(self, f: F) -> DList<U> on DList<T>.

In OCaml, implement a difference list for strings and use it to build a comma-separated string of 10,000 items, measuring time against String.concat.

Open Source Repos

functional-rust

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

Rust