Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 36 ยท Data Structures

Immutability and Persistent Data Structures

Understand why Clojure data never changes, how persistent vectors, maps and lists share structure so updates stay fast, what transients are, and what identity versus value means.

Every core Clojure collection is immutable: once created, it never changes. If you "add" an element to a vector, you get a new vector and the old one is still there, unchanged. This sounds expensive, but Clojure's collections are persistent data structures, which means a new version shares almost all of its memory with the old one. This lesson explains the idea, shows it in action and describes the escape hatches for when you need raw speed.

Why immutability?

Mutable data has a hidden cost: anything that can change can change at a bad moment. If two parts of a program hold the same list and one modifies it, the other is surprised. Immutable values remove that whole class of problem:

  • Safe sharing. Pass a map to any function or thread; nobody can change it behind your back.
  • Easy reasoning. A function's result depends only on its arguments.
  • Free snapshots. Keeping an old version (for undo, history or debugging) costs almost nothing.
  • Reliable equality and hashing. Collections can be used as map keys or set members because they never change.
  • Simple concurrency. Threads can read the same data without locks.
CLOJURE
(def original [1 2 3])
(def extended (conj original 4))

original    ; [1 2 3]    still unchanged
extended    ; [1 2 3 4]

Persistent: new versions share structure

Copying a million-element vector for every conj would be hopeless. Clojure's vectors are instead implemented as wide trees (a 32-way trie). An update copies only the path from the root to the changed leaf, and reuses every other branch.

Persistent updates

A tree Elements live in small nodes.
Copy the path Only nodes above the change are new.
Share the rest Old and new versions point at the same nodes.
Fast Effectively O(log32 n), nearly constant.

Maps and sets use similar hash tries.

1 / 2
flowchart TD
    subgraph old["Old version"]
      R1["root"] --> A1["node A"]
      R1 --> B1["node B"]
    end
    subgraph new["New version after one update"]
      R2["new root"] --> A2["new node A'"]
      R2 --> B1
    end
    A2 -.-> L["changed leaf copy"]

The new root and the changed branch are new nodes. Node B is shared by both versions.

Because the structure is shared, assoc, conj, dissoc and friends are effectively constant-time for most sizes. Lists share their tail: (conj lst x) creates one new cell pointing at the old list.

A model in JavaScript

The following stand-in implements a tiny persistent vector: a fixed two-level trie with four slots per node. Updating one element copies only two small arrays and reuses the other nodes, which you can confirm with ===. Real Clojure vectors use 32 slots and a growable depth, but the principle is the same.

JS Stand-in: path copying and structural sharing

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Three of the four leaves are the very same objects in both versions. Only one leaf and the root were copied.

Persistent linked lists

A list gets structural sharing for free. Adding to the front just creates a new cell that points to the old list:

JS Stand-in: a persistent list shares its tail

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Both a and b reuse the same base list. There is no copying at all, and neither can break the other.

Identity versus value

Because values never change, Clojure separates two ideas:

  • A value is an immutable thing: [1 2 3], "hello", {:a 1}.
  • An identity is a stable name whose value over time can change: "the current user list", "the game state". You model identities with atoms, refs and agents (see the state chapter).

You change the world by giving an identity a new value, not by mutating a value. This one idea explains most of Clojure's concurrency design.

CLOJURE
(def users (atom ["Ada"]))
(swap! users conj "Grace")    ; the identity now refers to a new vector
@users                        ; ["Ada" "Grace"]

Transients: controlled mutation for speed

Sometimes you build a large collection in a tight loop and the allocation of every intermediate version matters. A transient is a temporary, mutable-looking version of a vector, map or set. You convert, update repeatedly and convert back:

CLOJURE
(defn range-vec [n]
  (loop [i 0
         v (transient [])]
    (if (< i n)
      (recur (inc i) (conj! v i))
      (persistent! v))))

Rules: use the return value of conj!, assoc! and dissoc! (not the original reference); never use a transient after calling persistent!; and keep a transient inside one thread. into already uses transients internally, so (into [] (range 100000)) is fast without any extra work. Measure before you reach for transients.

Equality is by value

Immutable values are compared by content, so equal collections are interchangeable:

CLOJURE
(= {:a [1 2]} {:a [1 2]})   ; true
(hash [1 2 3])              ; the same each time for equal vectors
(def seen #{[1 2] [3 4]})
(contains? seen [1 2])      ; true

Using a vector as a set member or map key is perfectly safe in Clojure, which makes things like grid coordinates ([x y]) natural keys.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What happens to v after (conj v 4) when v is [1 2 3]?

    Collections are immutable; conj returns a new collection.
  2. 2. How do persistent data structures stay efficient?

    Only the path to the changed element is copied; the rest is shared.
  3. 3. What is a transient for?

    A transient speeds up bulk building; call persistent! to get an immutable collection back.
  4. 4. Why can a vector like [1 2] safely be a map key in Clojure?

    Immutable values have stable hashes and equality, so they are safe as keys.

Summary

  • Clojure's core collections are immutable; every update returns a new value.
  • Persistent data structures share structure, so updates are nearly constant time.
  • Values do not change; identities (atoms, refs, agents) point at new values over time.
  • Transients provide fast local mutation that ends with persistent!.
  • Equal collections are equal by value, which makes them safe as keys and set members.

Next: Working with Nested Data