1049 Advanced

1049-persistent-map — Persistent HashMap

Functional Programming

Tutorial

The Problem

Persistent data structures return modified versions while keeping old versions intact. They are the foundation of functional programming, git-style versioning, undo/redo, and concurrent data sharing without locks. Haskell's Data.Map, OCaml's Map.Make, and Clojure's hash array mapped trie (HAMT) are all persistent.

Rust's standard HashMap is mutable. This example demonstrates the "clone-based" persistent map — simple but O(n) per operation — and discusses the path to efficient structural sharing via HAMT.

🎯 Learning Outcomes

• Understand what "persistent" means: old versions remain valid after updates

• Implement a persistent map via cloning as a conceptual foundation

• Use Rc<_> sharing to reduce cloning overhead for immutable maps

• Understand the connection to HAMT (hash array mapped tries)

• Know the im crate for production persistent collections in Rust

Code Example

#![allow(clippy::all)]
// 1049: Persistent HashMap — Functional Update
// Simulate persistence in Rust using clone-on-write or cheap cloning

use std::collections::HashMap;
use std::rc::Rc;

/// Simple persistent map via full clone (conceptual — not efficient)
/// Real persistent maps use structural sharing (HAMT, etc.)
#[derive(Clone, Debug)]
struct PersistentMap<K, V> {
    data: HashMap<K, V>,
}

impl<K: std::hash::Hash + Eq + Clone, V: Clone> PersistentMap<K, V> {
    fn new() -> Self {
        PersistentMap {
            data: HashMap::new(),
        }
    }

    /// Insert returns a new version (old version unchanged)
    fn insert(&self, key: K, value: V) -> Self {
        let mut new_data = self.data.clone();
        new_data.insert(key, value);
        PersistentMap { data: new_data }
    }

    /// Remove returns a new version
    fn remove(&self, key: &K) -> Self {
        let mut new_data = self.data.clone();
        new_data.remove(key);
        PersistentMap { data: new_data }
    }

    fn get(&self, key: &K) -> Option<&V> {
        self.data.get(key)
    }

    fn contains_key(&self, key: &K) -> bool {
        self.data.contains_key(key)
    }

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

fn persistence_demo() {
    let v1 = PersistentMap::new()
        .insert("a", 1)
        .insert("b", 2)
        .insert("c", 3);

    let v2 = v1.insert("d", 4); // v2 has a,b,c,d
    let v3 = v1.insert("b", 99); // v3 updates b in v1

    // All versions coexist
    assert_eq!(v1.get(&"b"), Some(&2));
    assert_eq!(v3.get(&"b"), Some(&99));
    assert_eq!(v2.len(), 4);
    assert_eq!(v1.len(), 3);
    assert!(!v1.contains_key(&"d"));
}

/// Version history using Rc for cheap sharing
fn version_history() {
    let mut versions: Vec<Rc<PersistentMap<&str, i32>>> = vec![Rc::new(PersistentMap::new())];

    fn update(
        versions: &mut Vec<Rc<PersistentMap<&'static str, i32>>>,
        f: fn(&PersistentMap<&'static str, i32>) -> PersistentMap<&'static str, i32>,
    ) {
        let current = versions.last().unwrap().clone();
        versions.push(Rc::new(f(&current)));
    }

    update(&mut versions, |m| m.insert("x", 10));
    update(&mut versions, |m| m.insert("y", 20));
    update(&mut versions, |m| m.insert("z", 30));
    update(&mut versions, |m| m.remove(&"y"));

    // Current state
    let current = versions.last().unwrap();
    assert_eq!(current.get(&"x"), Some(&10));
    assert!(!current.contains_key(&"y"));
    assert_eq!(current.get(&"z"), Some(&30));

    // Access past version (after adding y)
    let v2 = &versions[2];
    assert!(v2.contains_key(&"y"));
    assert_eq!(v2.get(&"y"), Some(&20));
}

/// Undo/redo with persistent maps
struct UndoState<K, V> {
    current: PersistentMap<K, V>,
    undo_stack: Vec<PersistentMap<K, V>>,
    redo_stack: Vec<PersistentMap<K, V>>,
}

impl<K: std::hash::Hash + Eq + Clone, V: Clone> UndoState<K, V> {
    fn new() -> Self {
        UndoState {
            current: PersistentMap::new(),
            undo_stack: Vec::new(),
            redo_stack: Vec::new(),
        }
    }

    fn apply<F: FnOnce(&PersistentMap<K, V>) -> PersistentMap<K, V>>(&mut self, f: F) {
        let old = self.current.clone();
        self.current = f(&self.current);
        self.undo_stack.push(old);
        self.redo_stack.clear();
    }

    fn undo(&mut self) -> bool {
        if let Some(prev) = self.undo_stack.pop() {
            let current = std::mem::replace(&mut self.current, prev);
            self.redo_stack.push(current);
            true
        } else {
            false
        }
    }

    fn redo(&mut self) -> bool {
        if let Some(next) = self.redo_stack.pop() {
            let current = std::mem::replace(&mut self.current, next);
            self.undo_stack.push(current);
            true
        } else {
            false
        }
    }
}

fn undo_redo_test() {
    let mut state: UndoState<&str, &str> = UndoState::new();
    state.apply(|m| m.insert("name", "Alice"));
    state.apply(|m| m.insert("age", "30"));

    assert_eq!(state.current.get(&"name"), Some(&"Alice"));
    assert_eq!(state.current.get(&"age"), Some(&"30"));

    state.undo();
    assert!(!state.current.contains_key(&"age"));
    assert_eq!(state.current.get(&"name"), Some(&"Alice"));

    state.redo();
    assert_eq!(state.current.get(&"age"), Some(&"30"));
}

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

    #[test]
    fn test_persistence() {
        persistence_demo();
    }

    #[test]
    fn test_versions() {
        version_history();
    }

    #[test]
    fn test_undo_redo() {
        undo_redo_test();
    }

    #[test]
    fn test_empty_undo() {
        let mut state: UndoState<&str, i32> = UndoState::new();
        assert!(!state.undo()); // Nothing to undo
        assert!(!state.redo()); // Nothing to redo
    }
}

(* 1049: Persistent HashMap — Functional Update *)
(* OCaml's Map IS persistent — every operation returns a new map
   while sharing structure with the old one *)

module StringMap = Map.Make(String)

(* Approach 1: Persistence via structural sharing *)
let persistence_demo () =
  let v1 = StringMap.empty
    |> StringMap.add "a" 1
    |> StringMap.add "b" 2
    |> StringMap.add "c" 3
  in
  (* v2 is a "new version" sharing structure with v1 *)
  let v2 = StringMap.add "d" 4 v1 in
  let v3 = StringMap.add "b" 99 v1 in  (* update in v1, not v2 *)
  (* All versions coexist *)
  assert (StringMap.find "b" v1 = 2);
  assert (StringMap.find "b" v3 = 99);
  assert (StringMap.cardinal v2 = 4);
  assert (StringMap.cardinal v1 = 3);
  (* v1 is completely unaffected *)
  assert (not (StringMap.mem "d" v1))

(* Approach 2: Version history *)
let version_history () =
  let versions = ref [StringMap.empty] in
  let current () = List.hd !versions in
  let update f =
    versions := f (current ()) :: !versions
  in
  update (StringMap.add "x" 10);
  update (StringMap.add "y" 20);
  update (StringMap.add "z" 30);
  update (StringMap.remove "y");
  (* Current state *)
  assert (StringMap.find "x" (current ()) = 10);
  assert (not (StringMap.mem "y" (current ())));
  assert (StringMap.find "z" (current ()) = 30);
  (* Can access any past version *)
  let v2 = List.nth !versions 2 in  (* after adding y *)
  assert (StringMap.mem "y" v2);
  assert (StringMap.find "y" v2 = 20)

(* Approach 3: Undo/redo with persistent maps *)
type 'a state = {
  data: 'a StringMap.t;
  undo_stack: 'a StringMap.t list;
  redo_stack: 'a StringMap.t list;
}

let empty_state = { data = StringMap.empty; undo_stack = []; redo_stack = [] }

let apply f state =
  { data = f state.data;
    undo_stack = state.data :: state.undo_stack;
    redo_stack = [] }

let undo state =
  match state.undo_stack with
  | [] -> state
  | prev :: rest ->
    { data = prev; undo_stack = rest;
      redo_stack = state.data :: state.redo_stack }

let redo state =
  match state.redo_stack with
  | [] -> state
  | next :: rest ->
    { data = next; undo_stack = state.data :: state.undo_stack;
      redo_stack = rest }

let undo_redo_test () =
  let s = empty_state in
  let s = apply (StringMap.add "name" "Alice") s in
  let s = apply (StringMap.add "age" "30") s in
  assert (StringMap.find "name" s.data = "Alice");
  assert (StringMap.find "age" s.data = "30");
  let s = undo s in
  assert (not (StringMap.mem "age" s.data));
  assert (StringMap.find "name" s.data = "Alice");
  let s = redo s in
  assert (StringMap.find "age" s.data = "30")

let () =
  persistence_demo ();
  version_history ();
  undo_redo_test ();
  Printf.printf "✓ All tests passed\n"

Key Differences

Persistence by default: OCaml's Map is always persistent; Rust requires explicit design to achieve persistence.

Structural sharing: OCaml's Map shares unchanged subtrees (O(log n) allocation per update); Rust's clone approach copies the entire map (O(n)).

**im crate**: The im crate provides HAMT-based persistent collections matching OCaml's Map in asymptotic complexity.

Memory management: OCaml's GC manages shared nodes automatically; Rust's Rc<_>-based approaches need careful cycle avoidance.

OCaml Approach

OCaml's Map.Make is persistent by default — every operation returns a new map sharing unchanged structure with the original:

module IntMap = Map.Make(Int)

let m0 = IntMap.empty
let m1 = IntMap.add 1 "one" m0
let m2 = IntMap.add 2 "two" m1
(* m1 is unchanged; m0, m1, m2 all exist simultaneously *)

This structural sharing is automatic — no explicit cloning required. The GC manages the shared nodes.

Full Source

#![allow(clippy::all)]
// 1049: Persistent HashMap — Functional Update
// Simulate persistence in Rust using clone-on-write or cheap cloning

use std::collections::HashMap;
use std::rc::Rc;

/// Simple persistent map via full clone (conceptual — not efficient)
/// Real persistent maps use structural sharing (HAMT, etc.)
#[derive(Clone, Debug)]
struct PersistentMap<K, V> {
    data: HashMap<K, V>,
}

impl<K: std::hash::Hash + Eq + Clone, V: Clone> PersistentMap<K, V> {
    fn new() -> Self {
        PersistentMap {
            data: HashMap::new(),
        }
    }

    /// Insert returns a new version (old version unchanged)
    fn insert(&self, key: K, value: V) -> Self {
        let mut new_data = self.data.clone();
        new_data.insert(key, value);
        PersistentMap { data: new_data }
    }

    /// Remove returns a new version
    fn remove(&self, key: &K) -> Self {
        let mut new_data = self.data.clone();
        new_data.remove(key);
        PersistentMap { data: new_data }
    }

    fn get(&self, key: &K) -> Option<&V> {
        self.data.get(key)
    }

    fn contains_key(&self, key: &K) -> bool {
        self.data.contains_key(key)
    }

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

fn persistence_demo() {
    let v1 = PersistentMap::new()
        .insert("a", 1)
        .insert("b", 2)
        .insert("c", 3);

    let v2 = v1.insert("d", 4); // v2 has a,b,c,d
    let v3 = v1.insert("b", 99); // v3 updates b in v1

    // All versions coexist
    assert_eq!(v1.get(&"b"), Some(&2));
    assert_eq!(v3.get(&"b"), Some(&99));
    assert_eq!(v2.len(), 4);
    assert_eq!(v1.len(), 3);
    assert!(!v1.contains_key(&"d"));
}

/// Version history using Rc for cheap sharing
fn version_history() {
    let mut versions: Vec<Rc<PersistentMap<&str, i32>>> = vec![Rc::new(PersistentMap::new())];

    fn update(
        versions: &mut Vec<Rc<PersistentMap<&'static str, i32>>>,
        f: fn(&PersistentMap<&'static str, i32>) -> PersistentMap<&'static str, i32>,
    ) {
        let current = versions.last().unwrap().clone();
        versions.push(Rc::new(f(&current)));
    }

    update(&mut versions, |m| m.insert("x", 10));
    update(&mut versions, |m| m.insert("y", 20));
    update(&mut versions, |m| m.insert("z", 30));
    update(&mut versions, |m| m.remove(&"y"));

    // Current state
    let current = versions.last().unwrap();
    assert_eq!(current.get(&"x"), Some(&10));
    assert!(!current.contains_key(&"y"));
    assert_eq!(current.get(&"z"), Some(&30));

    // Access past version (after adding y)
    let v2 = &versions[2];
    assert!(v2.contains_key(&"y"));
    assert_eq!(v2.get(&"y"), Some(&20));
}

/// Undo/redo with persistent maps
struct UndoState<K, V> {
    current: PersistentMap<K, V>,
    undo_stack: Vec<PersistentMap<K, V>>,
    redo_stack: Vec<PersistentMap<K, V>>,
}

impl<K: std::hash::Hash + Eq + Clone, V: Clone> UndoState<K, V> {
    fn new() -> Self {
        UndoState {
            current: PersistentMap::new(),
            undo_stack: Vec::new(),
            redo_stack: Vec::new(),
        }
    }

    fn apply<F: FnOnce(&PersistentMap<K, V>) -> PersistentMap<K, V>>(&mut self, f: F) {
        let old = self.current.clone();
        self.current = f(&self.current);
        self.undo_stack.push(old);
        self.redo_stack.clear();
    }

    fn undo(&mut self) -> bool {
        if let Some(prev) = self.undo_stack.pop() {
            let current = std::mem::replace(&mut self.current, prev);
            self.redo_stack.push(current);
            true
        } else {
            false
        }
    }

    fn redo(&mut self) -> bool {
        if let Some(next) = self.redo_stack.pop() {
            let current = std::mem::replace(&mut self.current, next);
            self.undo_stack.push(current);
            true
        } else {
            false
        }
    }
}

fn undo_redo_test() {
    let mut state: UndoState<&str, &str> = UndoState::new();
    state.apply(|m| m.insert("name", "Alice"));
    state.apply(|m| m.insert("age", "30"));

    assert_eq!(state.current.get(&"name"), Some(&"Alice"));
    assert_eq!(state.current.get(&"age"), Some(&"30"));

    state.undo();
    assert!(!state.current.contains_key(&"age"));
    assert_eq!(state.current.get(&"name"), Some(&"Alice"));

    state.redo();
    assert_eq!(state.current.get(&"age"), Some(&"30"));
}

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

    #[test]
    fn test_persistence() {
        persistence_demo();
    }

    #[test]
    fn test_versions() {
        version_history();
    }

    #[test]
    fn test_undo_redo() {
        undo_redo_test();
    }

    #[test]
    fn test_empty_undo() {
        let mut state: UndoState<&str, i32> = UndoState::new();
        assert!(!state.undo()); // Nothing to undo
        assert!(!state.redo()); // Nothing to redo
    }
}

(* 1049: Persistent HashMap — Functional Update *)
(* OCaml's Map IS persistent — every operation returns a new map
   while sharing structure with the old one *)

module StringMap = Map.Make(String)

(* Approach 1: Persistence via structural sharing *)
let persistence_demo () =
  let v1 = StringMap.empty
    |> StringMap.add "a" 1
    |> StringMap.add "b" 2
    |> StringMap.add "c" 3
  in
  (* v2 is a "new version" sharing structure with v1 *)
  let v2 = StringMap.add "d" 4 v1 in
  let v3 = StringMap.add "b" 99 v1 in  (* update in v1, not v2 *)
  (* All versions coexist *)
  assert (StringMap.find "b" v1 = 2);
  assert (StringMap.find "b" v3 = 99);
  assert (StringMap.cardinal v2 = 4);
  assert (StringMap.cardinal v1 = 3);
  (* v1 is completely unaffected *)
  assert (not (StringMap.mem "d" v1))

(* Approach 2: Version history *)
let version_history () =
  let versions = ref [StringMap.empty] in
  let current () = List.hd !versions in
  let update f =
    versions := f (current ()) :: !versions
  in
  update (StringMap.add "x" 10);
  update (StringMap.add "y" 20);
  update (StringMap.add "z" 30);
  update (StringMap.remove "y");
  (* Current state *)
  assert (StringMap.find "x" (current ()) = 10);
  assert (not (StringMap.mem "y" (current ())));
  assert (StringMap.find "z" (current ()) = 30);
  (* Can access any past version *)
  let v2 = List.nth !versions 2 in  (* after adding y *)
  assert (StringMap.mem "y" v2);
  assert (StringMap.find "y" v2 = 20)

(* Approach 3: Undo/redo with persistent maps *)
type 'a state = {
  data: 'a StringMap.t;
  undo_stack: 'a StringMap.t list;
  redo_stack: 'a StringMap.t list;
}

let empty_state = { data = StringMap.empty; undo_stack = []; redo_stack = [] }

let apply f state =
  { data = f state.data;
    undo_stack = state.data :: state.undo_stack;
    redo_stack = [] }

let undo state =
  match state.undo_stack with
  | [] -> state
  | prev :: rest ->
    { data = prev; undo_stack = rest;
      redo_stack = state.data :: state.redo_stack }

let redo state =
  match state.redo_stack with
  | [] -> state
  | next :: rest ->
    { data = next; undo_stack = state.data :: state.undo_stack;
      redo_stack = rest }

let undo_redo_test () =
  let s = empty_state in
  let s = apply (StringMap.add "name" "Alice") s in
  let s = apply (StringMap.add "age" "30") s in
  assert (StringMap.find "name" s.data = "Alice");
  assert (StringMap.find "age" s.data = "30");
  let s = undo s in
  assert (not (StringMap.mem "age" s.data));
  assert (StringMap.find "name" s.data = "Alice");
  let s = redo s in
  assert (StringMap.find "age" s.data = "30")

let () =
  persistence_demo ();
  version_history ();
  undo_redo_test ();
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_persistence() {
        persistence_demo();
    }

    #[test]
    fn test_versions() {
        version_history();
    }

    #[test]
    fn test_undo_redo() {
        undo_redo_test();
    }

    #[test]
    fn test_empty_undo() {
        let mut state: UndoState<&str, i32> = UndoState::new();
        assert!(!state.undo()); // Nothing to undo
        assert!(!state.redo()); // Nothing to redo
    }
}

Deep Comparison

Persistent HashMap — Comparison

Core Insight

Persistent data structures allow "time travel" — old versions remain valid after updates. OCaml's Map achieves this natively through structural sharing (balanced trees share unchanged subtrees). Rust must clone or use specialized crates.

OCaml Approach

• Map IS persistent — add returns new map, old map unchanged

• Structural sharing: O(log n) nodes copied per update, rest shared

• Version history: just keep references to old maps

• Undo/redo: stack of map values (cheap — they share structure)

• GC handles cleanup of unreachable versions

Rust Approach

• HashMap is mutable — no built-in persistence

• clone() simulates persistence but is O(n) per update

• Version history via Vec<Rc<Map>> for cheap reference sharing

• Undo/redo: std::mem::replace for efficient state swapping

• Real persistence: im crate provides HAMT (Hash Array Mapped Trie)

Comparison Table

Feature	OCaml (`Map`)	Rust (clone-based)
Persistence	Native	Simulated via clone
Update cost	O(log n) shared	O(n) full clone
Structural sharing	Yes (tree)	No (full copy)
Version access	Free	Stored explicitly
Undo cost	O(1) (keep ref)	O(1) (swap) but O(n) creation
Real persistent	stdlib	`im` crate (HAMT)
Memory per version	O(log n) delta	O(n) full copy

Exercises

Add a version_history field to PersistentMap that stores all previous versions as a Vec<PersistentMap<K, V>> and implement undo().

Use the im crate's HashMap (which uses HAMT) to implement the same API and compare performance with the clone-based version.

Implement a simple key-value store with transactions: begin, commit, and rollback operations using persistent maps.

Open Source Repos

functional-rust

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

Rust