971 Advanced

971 Persistent List

Functional Programming

Tutorial

The Problem

Implement a persistent linked list where push creates a new version sharing the tail with the original. Rust requires Rc<T> for shared ownership since the borrow checker prohibits multiple owners. Each version of the list points to its tail via Rc::clone — a reference count increment costing O(1) with no data copying.

🎯 Learning Outcomes

• Implement enum PList<T> { Nil, Cons(T, Rc<PList<T>>) } with Rc for shared tails

• Implement push(x, tail) -> Rc<PList<T>> using Rc::clone to share the existing tail — O(1)

• Implement pop(list) -> Option<(&T, Rc<PList<T>>)> that returns a reference to the head and a clone of the tail

• Understand that Rc<T> enables shared immutable ownership (like OCaml's GC) but without thread safety (use Arc<T> for Send + Sync)

• Recognize structural sharing: two lists pointing to the same tail consume only O(1) extra memory

Code Example

#![allow(clippy::all)]
// 971: Persistent/Immutable Linked List with Structural Sharing
// OCaml lists are GC-managed with implicit sharing
// Rust needs Rc<T> to share nodes between multiple list versions

use std::rc::Rc;

// Approach 1: Persistent stack using Rc for structural sharing
#[derive(Debug)]
pub enum PList<T> {
    Nil,
    Cons(T, Rc<PList<T>>),
}

impl<T: Clone + PartialEq + std::fmt::Debug> PList<T> {
    pub fn nil() -> Rc<PList<T>> {
        Rc::new(PList::Nil)
    }

    pub fn push(x: T, tail: &Rc<PList<T>>) -> Rc<PList<T>> {
        Rc::new(PList::Cons(x, Rc::clone(tail))) // O(1), shares tail
    }

    pub fn pop(list: &Rc<PList<T>>) -> Option<(&T, Rc<PList<T>>)> {
        match list.as_ref() {
            PList::Nil => None,
            PList::Cons(x, rest) => Some((x, Rc::clone(rest))),
        }
    }

    pub fn peek(list: &Rc<PList<T>>) -> Option<&T> {
        match list.as_ref() {
            PList::Nil => None,
            PList::Cons(x, _) => Some(x),
        }
    }

    pub fn length(list: &Rc<PList<T>>) -> usize {
        match list.as_ref() {
            PList::Nil => 0,
            PList::Cons(_, rest) => 1 + Self::length(rest),
        }
    }

    pub fn to_vec(list: &Rc<PList<T>>) -> Vec<T> {
        let mut result = vec![];
        let mut current = Rc::clone(list);
        loop {
            match current.as_ref() {
                PList::Nil => break,
                PList::Cons(x, rest) => {
                    result.push(x.clone());
                    current = Rc::clone(rest);
                }
            }
        }
        result
    }
}

// Approach 2: Using standard Rc<Option<(T, Rc<...>)>> pattern (type alias)
// Simpler variant: functional list as enum with Rc sharing
#[derive(Debug, Clone, PartialEq)]
pub enum FList<T> {
    Nil,
    Cons(T, Rc<FList<T>>),
}

impl<T: Clone + PartialEq> FList<T> {
    pub fn empty() -> Self {
        FList::Nil
    }

    pub fn cons(head: T, tail: FList<T>) -> Self {
        FList::Cons(head, Rc::new(tail))
    }

    pub fn head(&self) -> Option<&T> {
        match self {
            FList::Nil => None,
            FList::Cons(x, _) => Some(x),
        }
    }

    pub fn tail(&self) -> Option<FList<T>> {
        match self {
            FList::Nil => None,
            FList::Cons(_, rest) => Some((**rest).clone()),
        }
    }

    pub fn len(&self) -> usize {
        match self {
            FList::Nil => 0,
            FList::Cons(_, rest) => 1 + rest.len(),
        }
    }

    pub fn to_vec(&self) -> Vec<T> {
        let mut v = vec![];
        let mut curr = self.clone();
        while let FList::Cons(x, rest) = curr {
            v.push(x);
            curr = (*rest).clone();
        }
        v
    }
}

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

    #[test]
    fn test_persistent_push() {
        let s0 = PList::<i32>::nil();
        let s1 = PList::push(1, &s0);
        let s2 = PList::push(2, &s1);
        let s3 = PList::push(3, &s2);

        assert_eq!(PList::length(&s0), 0);
        assert_eq!(PList::length(&s1), 1);
        assert_eq!(PList::length(&s2), 2);
        assert_eq!(PList::length(&s3), 3);
    }

    #[test]
    fn test_old_versions_unchanged() {
        let s0 = PList::<i32>::nil();
        let s1 = PList::push(1, &s0);
        let s2 = PList::push(2, &s1);
        let _s3 = PList::push(3, &s2);

        // s2 is unchanged after creating s3
        assert_eq!(PList::peek(&s2), Some(&2));
        assert_eq!(PList::length(&s2), 2);
    }

    #[test]
    fn test_pop_returns_old_tail() {
        let s0 = PList::<i32>::nil();
        let s1 = PList::push(1, &s0);
        let s2 = PList::push(2, &s1);
        let s3 = PList::push(3, &s2);

        let (v, s2_prime) = PList::pop(&s3).unwrap();
        assert_eq!(*v, 3);
        assert_eq!(PList::peek(&s2_prime), Some(&2));
        assert_eq!(PList::length(&s2_prime), 2);
    }

    #[test]
    fn test_to_vec() {
        let s0 = PList::<i32>::nil();
        let s1 = PList::push(1, &s0);
        let s2 = PList::push(2, &s1);
        let s3 = PList::push(3, &s2);
        assert_eq!(PList::to_vec(&s3), vec![3, 2, 1]);
    }

    #[test]
    fn test_flist_persistence() {
        let l1 = FList::cons(1, FList::empty());
        let l2 = FList::cons(2, l1.clone());
        let l3 = FList::cons(3, l2.clone());
        assert_eq!(l3.to_vec(), vec![3, 2, 1]);
        assert_eq!(l2.to_vec(), vec![2, 1]); // unchanged
        assert_eq!(l1.to_vec(), vec![1]); // unchanged
    }
}

(* 971: Persistent/Immutable Linked List *)
(* OCaml lists are already persistent with structural sharing *)
(* Each cons cell is shared between versions *)

(* Approach 1: OCaml's built-in list IS persistent *)

let () =
  let list1 = [1; 2; 3] in
  let list2 = 0 :: list1 in  (* O(1), shares tail with list1 *)
  let list3 = (-1) :: list2 in

  (* All three lists exist simultaneously *)
  assert (list1 = [1; 2; 3]);
  assert (list2 = [0; 1; 2; 3]);
  assert (list3 = [-1; 0; 1; 2; 3]);

  (* Structural sharing: list2 and list1 share the [1;2;3] tail *)
  (* This is automatic — no explicit copy *)
  ()

(* Approach 2: Explicit persistent stack *)

type 'a pstack =
  | Empty
  | Cons of 'a * 'a pstack

let empty = Empty

let push x s = Cons (x, s)

let pop = function
  | Empty -> None
  | Cons (x, rest) -> Some (x, rest)

let peek = function
  | Empty -> None
  | Cons (x, _) -> Some x

let rec length = function
  | Empty -> 0
  | Cons (_, rest) -> 1 + length rest

let rec to_list = function
  | Empty -> []
  | Cons (x, rest) -> x :: to_list rest

(* Approach 3: Persistent operations *)

let rec append s1 s2 =
  match s1 with
  | Empty -> s2
  | Cons (x, rest) -> Cons (x, append rest s2)

let () =
  let s0 = empty in
  let s1 = push 1 s0 in
  let s2 = push 2 s1 in
  let s3 = push 3 s2 in

  assert (length s0 = 0);
  assert (length s1 = 1);
  assert (length s2 = 2);
  assert (length s3 = 3);

  assert (peek s3 = Some 3);

  (* s2 unchanged after creating s3 *)
  assert (peek s2 = Some 2);

  let (v, s2') = Option.get (pop s3) in
  assert (v = 3);
  assert (peek s2' = Some 2);
  assert (s2' = s2);  (* structurally equal *)

  assert (to_list s3 = [3; 2; 1]);

  let combined = append s3 s1 in
  assert (to_list combined = [3; 2; 1; 1]);

  Printf.printf "✓ All tests passed\n"

Key Differences

Aspect	Rust	OCaml
Shared ownership	`Rc<T>` — explicit reference counting	GC — automatic
Push	`Rc::new(Cons(x, Rc::clone(tail)))`	`x :: xs` or `Cons (x, tail)`
Thread safety	`Rc` not `Send`; use `Arc` for threads	GC handles all cases
Memory freedom	Reference count drops to 0	GC collects when unreachable

Persistent data structures enable "time travel" — holding Rc<PList<T>> from before a push gives access to the previous version. This is how functional programs implement undo, versioned state, and persistent queues.

OCaml Approach

(* OCaml lists are persistent by default — no explicit Rc needed *)
type 'a plist = Nil | Cons of 'a * 'a plist

let push x tail = Cons (x, tail)      (* O(1), GC shares tail *)
let pop = function
  | Nil -> None
  | Cons (x, rest) -> Some (x, rest)

(* Using standard OCaml list — identical behavior *)
let push_std x xs = x :: xs          (* O(1) *)
let pop_std = function [] -> None | x :: rest -> Some (x, rest)

In OCaml, all list values are persistent by default — x :: xs shares xs without copying. The GC tracks references automatically. There is no need to wrap in Rc because OCaml's garbage collector manages sharing transparently.

Full Source

#![allow(clippy::all)]
// 971: Persistent/Immutable Linked List with Structural Sharing
// OCaml lists are GC-managed with implicit sharing
// Rust needs Rc<T> to share nodes between multiple list versions

use std::rc::Rc;

// Approach 1: Persistent stack using Rc for structural sharing
#[derive(Debug)]
pub enum PList<T> {
    Nil,
    Cons(T, Rc<PList<T>>),
}

impl<T: Clone + PartialEq + std::fmt::Debug> PList<T> {
    pub fn nil() -> Rc<PList<T>> {
        Rc::new(PList::Nil)
    }

    pub fn push(x: T, tail: &Rc<PList<T>>) -> Rc<PList<T>> {
        Rc::new(PList::Cons(x, Rc::clone(tail))) // O(1), shares tail
    }

    pub fn pop(list: &Rc<PList<T>>) -> Option<(&T, Rc<PList<T>>)> {
        match list.as_ref() {
            PList::Nil => None,
            PList::Cons(x, rest) => Some((x, Rc::clone(rest))),
        }
    }

    pub fn peek(list: &Rc<PList<T>>) -> Option<&T> {
        match list.as_ref() {
            PList::Nil => None,
            PList::Cons(x, _) => Some(x),
        }
    }

    pub fn length(list: &Rc<PList<T>>) -> usize {
        match list.as_ref() {
            PList::Nil => 0,
            PList::Cons(_, rest) => 1 + Self::length(rest),
        }
    }

    pub fn to_vec(list: &Rc<PList<T>>) -> Vec<T> {
        let mut result = vec![];
        let mut current = Rc::clone(list);
        loop {
            match current.as_ref() {
                PList::Nil => break,
                PList::Cons(x, rest) => {
                    result.push(x.clone());
                    current = Rc::clone(rest);
                }
            }
        }
        result
    }
}

// Approach 2: Using standard Rc<Option<(T, Rc<...>)>> pattern (type alias)
// Simpler variant: functional list as enum with Rc sharing
#[derive(Debug, Clone, PartialEq)]
pub enum FList<T> {
    Nil,
    Cons(T, Rc<FList<T>>),
}

impl<T: Clone + PartialEq> FList<T> {
    pub fn empty() -> Self {
        FList::Nil
    }

    pub fn cons(head: T, tail: FList<T>) -> Self {
        FList::Cons(head, Rc::new(tail))
    }

    pub fn head(&self) -> Option<&T> {
        match self {
            FList::Nil => None,
            FList::Cons(x, _) => Some(x),
        }
    }

    pub fn tail(&self) -> Option<FList<T>> {
        match self {
            FList::Nil => None,
            FList::Cons(_, rest) => Some((**rest).clone()),
        }
    }

    pub fn len(&self) -> usize {
        match self {
            FList::Nil => 0,
            FList::Cons(_, rest) => 1 + rest.len(),
        }
    }

    pub fn to_vec(&self) -> Vec<T> {
        let mut v = vec![];
        let mut curr = self.clone();
        while let FList::Cons(x, rest) = curr {
            v.push(x);
            curr = (*rest).clone();
        }
        v
    }
}

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

    #[test]
    fn test_persistent_push() {
        let s0 = PList::<i32>::nil();
        let s1 = PList::push(1, &s0);
        let s2 = PList::push(2, &s1);
        let s3 = PList::push(3, &s2);

        assert_eq!(PList::length(&s0), 0);
        assert_eq!(PList::length(&s1), 1);
        assert_eq!(PList::length(&s2), 2);
        assert_eq!(PList::length(&s3), 3);
    }

    #[test]
    fn test_old_versions_unchanged() {
        let s0 = PList::<i32>::nil();
        let s1 = PList::push(1, &s0);
        let s2 = PList::push(2, &s1);
        let _s3 = PList::push(3, &s2);

        // s2 is unchanged after creating s3
        assert_eq!(PList::peek(&s2), Some(&2));
        assert_eq!(PList::length(&s2), 2);
    }

    #[test]
    fn test_pop_returns_old_tail() {
        let s0 = PList::<i32>::nil();
        let s1 = PList::push(1, &s0);
        let s2 = PList::push(2, &s1);
        let s3 = PList::push(3, &s2);

        let (v, s2_prime) = PList::pop(&s3).unwrap();
        assert_eq!(*v, 3);
        assert_eq!(PList::peek(&s2_prime), Some(&2));
        assert_eq!(PList::length(&s2_prime), 2);
    }

    #[test]
    fn test_to_vec() {
        let s0 = PList::<i32>::nil();
        let s1 = PList::push(1, &s0);
        let s2 = PList::push(2, &s1);
        let s3 = PList::push(3, &s2);
        assert_eq!(PList::to_vec(&s3), vec![3, 2, 1]);
    }

    #[test]
    fn test_flist_persistence() {
        let l1 = FList::cons(1, FList::empty());
        let l2 = FList::cons(2, l1.clone());
        let l3 = FList::cons(3, l2.clone());
        assert_eq!(l3.to_vec(), vec![3, 2, 1]);
        assert_eq!(l2.to_vec(), vec![2, 1]); // unchanged
        assert_eq!(l1.to_vec(), vec![1]); // unchanged
    }
}

(* 971: Persistent/Immutable Linked List *)
(* OCaml lists are already persistent with structural sharing *)
(* Each cons cell is shared between versions *)

(* Approach 1: OCaml's built-in list IS persistent *)

let () =
  let list1 = [1; 2; 3] in
  let list2 = 0 :: list1 in  (* O(1), shares tail with list1 *)
  let list3 = (-1) :: list2 in

  (* All three lists exist simultaneously *)
  assert (list1 = [1; 2; 3]);
  assert (list2 = [0; 1; 2; 3]);
  assert (list3 = [-1; 0; 1; 2; 3]);

  (* Structural sharing: list2 and list1 share the [1;2;3] tail *)
  (* This is automatic — no explicit copy *)
  ()

(* Approach 2: Explicit persistent stack *)

type 'a pstack =
  | Empty
  | Cons of 'a * 'a pstack

let empty = Empty

let push x s = Cons (x, s)

let pop = function
  | Empty -> None
  | Cons (x, rest) -> Some (x, rest)

let peek = function
  | Empty -> None
  | Cons (x, _) -> Some x

let rec length = function
  | Empty -> 0
  | Cons (_, rest) -> 1 + length rest

let rec to_list = function
  | Empty -> []
  | Cons (x, rest) -> x :: to_list rest

(* Approach 3: Persistent operations *)

let rec append s1 s2 =
  match s1 with
  | Empty -> s2
  | Cons (x, rest) -> Cons (x, append rest s2)

let () =
  let s0 = empty in
  let s1 = push 1 s0 in
  let s2 = push 2 s1 in
  let s3 = push 3 s2 in

  assert (length s0 = 0);
  assert (length s1 = 1);
  assert (length s2 = 2);
  assert (length s3 = 3);

  assert (peek s3 = Some 3);

  (* s2 unchanged after creating s3 *)
  assert (peek s2 = Some 2);

  let (v, s2') = Option.get (pop s3) in
  assert (v = 3);
  assert (peek s2' = Some 2);
  assert (s2' = s2);  (* structurally equal *)

  assert (to_list s3 = [3; 2; 1]);

  let combined = append s3 s1 in
  assert (to_list combined = [3; 2; 1; 1]);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_persistent_push() {
        let s0 = PList::<i32>::nil();
        let s1 = PList::push(1, &s0);
        let s2 = PList::push(2, &s1);
        let s3 = PList::push(3, &s2);

        assert_eq!(PList::length(&s0), 0);
        assert_eq!(PList::length(&s1), 1);
        assert_eq!(PList::length(&s2), 2);
        assert_eq!(PList::length(&s3), 3);
    }

    #[test]
    fn test_old_versions_unchanged() {
        let s0 = PList::<i32>::nil();
        let s1 = PList::push(1, &s0);
        let s2 = PList::push(2, &s1);
        let _s3 = PList::push(3, &s2);

        // s2 is unchanged after creating s3
        assert_eq!(PList::peek(&s2), Some(&2));
        assert_eq!(PList::length(&s2), 2);
    }

    #[test]
    fn test_pop_returns_old_tail() {
        let s0 = PList::<i32>::nil();
        let s1 = PList::push(1, &s0);
        let s2 = PList::push(2, &s1);
        let s3 = PList::push(3, &s2);

        let (v, s2_prime) = PList::pop(&s3).unwrap();
        assert_eq!(*v, 3);
        assert_eq!(PList::peek(&s2_prime), Some(&2));
        assert_eq!(PList::length(&s2_prime), 2);
    }

    #[test]
    fn test_to_vec() {
        let s0 = PList::<i32>::nil();
        let s1 = PList::push(1, &s0);
        let s2 = PList::push(2, &s1);
        let s3 = PList::push(3, &s2);
        assert_eq!(PList::to_vec(&s3), vec![3, 2, 1]);
    }

    #[test]
    fn test_flist_persistence() {
        let l1 = FList::cons(1, FList::empty());
        let l2 = FList::cons(2, l1.clone());
        let l3 = FList::cons(3, l2.clone());
        assert_eq!(l3.to_vec(), vec![3, 2, 1]);
        assert_eq!(l2.to_vec(), vec![2, 1]); // unchanged
        assert_eq!(l1.to_vec(), vec![1]); // unchanged
    }
}

Deep Comparison

Persistent List — Comparison

Core Insight

A persistent data structure preserves old versions when modified. OCaml lists are inherently persistent: x :: list creates a new cons cell pointing to the existing list — zero copying, GC manages memory. Rust requires Rc<T> (reference-counted shared ownership) to allow multiple bindings to own the same tail, since Rust's ownership model forbids multiple owners without Rc/Arc.

OCaml Approach

• type 'a pstack = Empty | Cons of 'a * 'a pstack — recursive type

• 0 :: list — O(1) cons, GC handles sharing automatically

• Old versions remain accessible because GC won't collect shared nodes

• let list2 = x :: list1 creates new head, shares list1's storage

• Pattern matching for pop: Cons (x, rest) -> Some (x, rest)

• Built-in list type IS a persistent list — no extra work

Rust Approach

• enum PList<T> { Nil, Cons(T, Rc<PList<T>>) } — needs Rc for sharing

• Rc::new(PList::Cons(x, Rc::clone(tail))) — clone the Rc (increments count, O(1))

• Rc::clone does NOT copy the list node — it copies the pointer + bumps ref count

• When last Rc pointing to a node is dropped, the node is freed

• Thread safety: use Arc<T> instead of Rc<T> for shared across threads

• Pattern matching same as OCaml, but requires list.as_ref() to match

Comparison Table

Aspect	OCaml	Rust
Sharing mechanism	GC (automatic)	`Rc<T>` (reference counting)
Cons operation	`x :: list`	`Rc::new(Cons(x, Rc::clone(tail)))`
Old versions	Kept alive by GC	Kept alive by Rc count > 0
Memory reclaim	GC cycle	Drop when last Rc gone
Deref to match	`match list with Cons ...`	`match list.as_ref() { Cons ...`
Thread safety	GC handles	Need `Arc<T>` instead of `Rc<T>`
Clone pointer	n/a (GC)	`Rc::clone()` — O(1) pointer copy

Exercises

Implement length(list: &Rc<PList<T>>) -> usize — count elements iteratively to avoid stack overflow.

Implement append(a: &Rc<PList<T>>, b: &Rc<PList<T>>) -> Rc<PList<T>> — creates copies of a's elements pointing to shared b.

Implement to_vec(list: &Rc<PList<T>>) -> Vec<T> where T: Clone — collect all elements.

Convert Rc to Arc and verify the list is Send + Sync for multi-threaded access.

Implement a persistent stack with push, pop, and peek methods, demonstrating that old versions remain accessible after push.

Open Source Repos

functional-rust

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

Rust