ExamplesBy LevelBy TopicLearning Paths
075 Advanced
← 074075 →

075 — Difference List

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "075 — Difference List" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. A difference list represents a list as a function from "remaining suffix" to "complete list". Key difference from OCaml: 1. **`Box<dyn Fn>` vs plain function**: Rust requires `Box<dyn Fn>` because each closure has a unique type. OCaml's closures have a uniform representation — `'a list

Tutorial

The Problem

A difference list represents a list as a function from "remaining suffix" to "complete list". Appending two difference lists is O(1) — just function composition — instead of O(n). This is important in functional programming where repeated left-fold appends create O(n²) behavior.

Difference lists originate in Prolog (1984) and appear in Haskell's ShowS type for efficient string building. The key insight: [1,2,3] as a difference list is fun suffix -> [1,2,3] ++ suffix. Appending is fun suffix -> dl1(dl2(suffix)). ShowS = String -> String in Haskell is exactly a difference list for strings.

🎯 Learning Outcomes

  • • Understand difference lists as function composition for O(1) append
  • • Implement DList::empty(), singleton(x), from_vec(v), append(self, other), to_vec()
  • • Recognize that append is function composition: (dl1.append(dl2)).run(tail) = dl1.run(dl2.run(tail))
  • • Connect to ShowS (Haskell) and Buffer (OCaml) as practical applications
  • • Understand when difference lists matter: left-associative appends in recursive algorithms

    • Code Example

    #![allow(clippy::all)]
/// # Difference List — O(1) Append
///
/// A difference list represents a list as a function from "rest of list" to "full list".
/// This makes append O(1) — just function composition — instead of O(n).
///
/// In Rust, this pattern is less common because Vec already has O(1) amortized push_back.
/// But it's a great exercise in higher-order functions and closures.

/// A difference list is a function: given a tail, prepend our elements.
/// We use Box<dyn Fn> since closures have unique types.
pub struct DList<T> {
    f: Box<dyn Fn(Vec<T>) -> Vec<T>>,
}

impl<T: 'static + Clone> DList<T> {
    /// Empty difference list — identity function.
    pub fn empty() -> Self {
        DList {
            f: Box::new(|rest| rest),
        }
    }

    /// Singleton — prepends one element.
    pub fn singleton(x: T) -> Self {
        DList {
            f: Box::new(move |mut rest| {
                rest.insert(0, x.clone());
                rest
            }),
        }
    }

    /// From a Vec.
    pub fn from_vec(v: Vec<T>) -> Self {
        DList {
            f: Box::new(move |rest| {
                let mut result = v.clone();
                result.extend(rest);
                result
            }),
        }
    }

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

    /// Convert to Vec — apply the function to an empty list.
    pub fn to_vec(&self) -> Vec<T> {
        (self.f)(vec![])
    }
}

/// Alternative: just use Vec! Rust's Vec already has O(1) amortized push.
/// This shows that the difference list pattern, while elegant in OCaml/Haskell,
/// is often unnecessary in Rust.
pub fn concat_with_vec(lists: &[Vec<i32>]) -> Vec<i32> {
    let total_len: usize = lists.iter().map(|l| l.len()).sum();
    let mut result = Vec::with_capacity(total_len);
    for list in lists {
        result.extend(list);
    }
    result
}

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

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

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

    #[test]
    fn test_from_vec() {
        let dl = DList::from_vec(vec![1, 2, 3]);
        assert_eq!(dl.to_vec(), vec![1, 2, 3]);
    }

    #[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);
        let result = a.append(b).append(c);
        assert_eq!(result.to_vec(), vec![1, 2, 3, 4, 5, 6, 7]);
    }

    #[test]
    fn test_multiple_appends() {
        let dl = DList::from_vec(vec![1])
            .append(DList::from_vec(vec![2]))
            .append(DList::from_vec(vec![3]))
            .append(DList::from_vec(vec![4]));
        assert_eq!(dl.to_vec(), vec![1, 2, 3, 4]);
    }

    #[test]
    fn test_concat_with_vec() {
        let lists = vec![vec![1, 2], vec![3, 4], vec![5, 6]];
        assert_eq!(concat_with_vec(&lists), vec![1, 2, 3, 4, 5, 6]);
    }
}

    Key Differences

  • **Box<dyn Fn> vs plain function**: Rust requires Box<dyn Fn> because each closure has a unique type. OCaml's closures have a uniform representation — 'a list -> 'a list is a first-class type without boxing.
  • **FnOnce vs Fn**: Rust's DList here uses FnOnce — each difference list can only be used once (because append consumes both). A version using Fn requires T: Clone. OCaml's closures can be called multiple times.
  • Practical use in Rust: Rust's String::push_str and Vec::extend are already amortized O(1), so difference lists are less critical than in OCaml with its immutable lists. The concept is pedagogically important.
  • **ShowS in Haskell**: Haskell's type ShowS = String -> String is a difference list for strings. showsPrec uses it to build Show instances efficiently.

    • OCaml Approach

    OCaml's difference list is an elegant application of higher-order functions:

    type 'a dlist = 'a list -> 'a list

let empty : 'a dlist = fun xs -> xs
let singleton x = fun xs -> x :: xs
let append dl1 dl2 = fun xs -> dl1 (dl2 xs)  (* O(1): function composition *)
let to_list dl = dl []
let from_list lst = fun xs -> lst @ xs

(* append [1;2] [3;4]: build dl1 . dl2, then apply to [] *)
let result = to_list (append (from_list [1;2]) (from_list [3;4]))
(* result = [1; 2; 3; 4] *)

    This is isomorphic to Haskell's ShowS = String -> String and DList a = [a] -> [a].

    Full Source

    #![allow(clippy::all)]
/// # Difference List — O(1) Append
///
/// A difference list represents a list as a function from "rest of list" to "full list".
/// This makes append O(1) — just function composition — instead of O(n).
///
/// In Rust, this pattern is less common because Vec already has O(1) amortized push_back.
/// But it's a great exercise in higher-order functions and closures.

/// A difference list is a function: given a tail, prepend our elements.
/// We use Box<dyn Fn> since closures have unique types.
pub struct DList<T> {
    f: Box<dyn Fn(Vec<T>) -> Vec<T>>,
}

impl<T: 'static + Clone> DList<T> {
    /// Empty difference list — identity function.
    pub fn empty() -> Self {
        DList {
            f: Box::new(|rest| rest),
        }
    }

    /// Singleton — prepends one element.
    pub fn singleton(x: T) -> Self {
        DList {
            f: Box::new(move |mut rest| {
                rest.insert(0, x.clone());
                rest
            }),
        }
    }

    /// From a Vec.
    pub fn from_vec(v: Vec<T>) -> Self {
        DList {
            f: Box::new(move |rest| {
                let mut result = v.clone();
                result.extend(rest);
                result
            }),
        }
    }

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

    /// Convert to Vec — apply the function to an empty list.
    pub fn to_vec(&self) -> Vec<T> {
        (self.f)(vec![])
    }
}

/// Alternative: just use Vec! Rust's Vec already has O(1) amortized push.
/// This shows that the difference list pattern, while elegant in OCaml/Haskell,
/// is often unnecessary in Rust.
pub fn concat_with_vec(lists: &[Vec<i32>]) -> Vec<i32> {
    let total_len: usize = lists.iter().map(|l| l.len()).sum();
    let mut result = Vec::with_capacity(total_len);
    for list in lists {
        result.extend(list);
    }
    result
}

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

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

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

    #[test]
    fn test_from_vec() {
        let dl = DList::from_vec(vec![1, 2, 3]);
        assert_eq!(dl.to_vec(), vec![1, 2, 3]);
    }

    #[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);
        let result = a.append(b).append(c);
        assert_eq!(result.to_vec(), vec![1, 2, 3, 4, 5, 6, 7]);
    }

    #[test]
    fn test_multiple_appends() {
        let dl = DList::from_vec(vec![1])
            .append(DList::from_vec(vec![2]))
            .append(DList::from_vec(vec![3]))
            .append(DList::from_vec(vec![4]));
        assert_eq!(dl.to_vec(), vec![1, 2, 3, 4]);
    }

    #[test]
    fn test_concat_with_vec() {
        let lists = vec![vec![1, 2], vec![3, 4], vec![5, 6]];
        assert_eq!(concat_with_vec(&lists), vec![1, 2, 3, 4, 5, 6]);
    }
}
    ✓ 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![]);
    }

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

    #[test]
    fn test_from_vec() {
        let dl = DList::from_vec(vec![1, 2, 3]);
        assert_eq!(dl.to_vec(), vec![1, 2, 3]);
    }

    #[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);
        let result = a.append(b).append(c);
        assert_eq!(result.to_vec(), vec![1, 2, 3, 4, 5, 6, 7]);
    }

    #[test]
    fn test_multiple_appends() {
        let dl = DList::from_vec(vec![1])
            .append(DList::from_vec(vec![2]))
            .append(DList::from_vec(vec![3]))
            .append(DList::from_vec(vec![4]));
        assert_eq!(dl.to_vec(), vec![1, 2, 3, 4]);
    }

    #[test]
    fn test_concat_with_vec() {
        let lists = vec![vec![1, 2], vec![3, 4], vec![5, 6]];
        assert_eq!(concat_with_vec(&lists), vec![1, 2, 3, 4, 5, 6]);
    }
}

    Deep Comparison

    Difference List — OCaml vs Rust Comparison

    Core Insight

    Difference lists solve a problem that's acute in functional languages: list append (@ / ++) is O(n) because linked lists can only be traversed from the head. By representing a list as a function rest → our_elements ++ rest, append becomes function composition — O(1). In Rust, Vec::extend() is already O(m) (where m is the appended portion), making this pattern more educational than practical.

    OCaml Approach

    Brilliantly minimal. A difference list is just 'a list -> 'a list — a type alias for a function. empty = Fun.id, singleton x = fun rest -> x :: rest, append a b = fun rest -> a (b rest). Pure function composition, no data structure at all. This is where OCaml's first-class functions shine.

    Rust Approach

    Requires Box<dyn Fn(Vec<T>) -> Vec<T>> for the stored function, since closures have unique types. Each operation allocates a new boxed closure. The T: Clone bound is needed because closures may be called multiple times. In practice, Rust programmers would just use Vec with extend() — it's simpler and faster.

    Comparison Table

    AspectOCamlRust
    MemoryClosures (GC'd)Box<dyn Fn> (heap allocated)
    Null safetyN/AN/A
    ErrorsN/AN/A
    IterationFunction applicationFunction application + Vec ops
    NecessitySolves O(n) append problemUnnecessary — Vec already O(1) push

    Things Rust Learners Should Notice

  • The problem doesn't exist in Rust — Vec has O(1) amortized push; no need for difference lists
  • **Box<dyn Fn> overhead** — each closure allocation costs more than Vec operations
  • **T: 'static + Clone** — required for closures to own and reproduce values
  • Function composition — |rest| f(g(rest)) is the core trick, same in both languages
  • Know when NOT to port — some FP patterns don't translate because Rust's data structures already solve the problem

    • Further Reading

  • • [Difference list (Wikipedia)](https://en.wikipedia.org/wiki/Difference_list)
  • • [Vec::extend](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.extend)
  • • [When to use FP patterns in Rust](https://doc.rust-lang.org/book/ch13-00-functional-features.html)

    • Exercises

  • String difference list: Define type Dstr = Box<dyn FnOnce(String) -> String> and implement dstr_singleton(c: char), dstr_append, and dstr_to_string. Compare with repeated String::push for deep append trees.
  • Performance test: Build a list [1..n] using left-associative appends with both Vec and DList. Measure the time difference for n=100,000. Explain the O(n²) vs O(n) complexity.
  • From DList to iterator: Instead of to_vec(), implement DList::into_iter(self) -> impl Iterator<Item=T> that yields elements lazily without materializing the full Vec.

    • Open Source Repos

    functional-rust

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

    Rust