Skip to content
LumenaryAcademy
Foundations 55 min

Immutable, persistent data

Vectors, maps, sets and lists that never change, and why that makes programs simpler.

Code tested · 4AI-draftedAwaiting review by a computer scientist
MotivationH

The bug that cannot happen

Imagine a function in an ordinary language that receives a list of exam scores and is supposed to return the average. To find the median as well, its author sorts the list first, in place. The function returns the right numbers. Somewhere else in the program, though, the caller still holds that list and expects it to be in the order the students sat the exam. Now it is sorted. Nothing crashed, no test of the average function failed, and a report three screens away is quietly wrong.

Every experienced programmer has a story like this. The root cause is that two parts of the program shared something mutable: a value that could change underneath one of them. The usual defences are discipline ("never modify arguments"), defensive copying ("copy the list before sorting, just in case") and locks when threads are involved. All three are easy to forget and costly to get right.

Clojure removes the problem at the source. Its collections are immutable: once a vector, map or set exists, it never changes. Functions that look like they modify a collection, such as conj ("add") or assoc ("set a key"), return a new collection and leave the original alone. You can pass a map to any function, store it anywhere, and share it between threads, knowing that it will still be exactly what it was.

The obvious worry is cost. If every change makes a new collection, surely adding one element to a million-element vector copies a million elements? It does not, and this lesson shows why.

DefinitionsH

Values, persistence and structural sharing

Definition— Immutable value

A value that cannot be changed after it is created. Numbers and strings are immutable in most languages; in Clojure the collections are too. A value can be freely shared, compared and used as a map key.

Definition— Persistent data structure

A data structure that preserves its previous version when it is "modified": an update produces a new version, and both versions remain usable, each with the same performance guarantees. ("Persistent" here has nothing to do with saving to disk.)

Definition— Structural sharing

The technique that makes persistence affordable: a new version reuses, by reference, every part of the old version that did not change, and copies only the small part that did.

Clojure's vectors and maps are stored as shallow, wide trees. Each internal node has up to 32 children, so a vector of a million elements is only four levels deep and one of a billion elements about six. To change one element, Clojure copies the nodes on the path from the root down to that element (at most a handful of nodes of 32 slots each) and points the new root at all the other, untouched subtrees.

old versionnew versionleaf 1leaf 2leaf 3leaf 3, changed
Updating one element of a large persistent vector copies only the path from the root to the changed leaf (dashed). Every other node is shared by the old and the new version, which both remain valid.

Because nothing ever changes in place, sharing is completely safe: no version can observe another's changes, because there are none. The trees are variants of Phil Bagwell's hash array mapped trie, and the idea of persistent structures goes back to work by Chris Okasaki and others in the functional-programming community in the 1990s. Clojure's contribution was to make them the default, everyday collections of a practical language.

Clojure has four core collection types, each with a literal syntax:

CollectionLiteralUse it forAdds with conj at
vector[1 2 3]ordered data you index into or append tothe end
map{:k 1}named fields, lookups by key(adds a key-value pair)
set#{1 2}membership, uniqueness(no order)
list'(1 2 3)code, stacks, adding at the frontthe front

In everyday code vectors and maps do most of the work. Lists appear mainly as code (every form you write is one) and when you need a stack.

Worked examplesH

Working with each collection

Vectors

clojure
(def langs ["Lisp" "Scheme" "Java"])
(def more (conj langs "Clojure"))

(prn langs)
(prn more)
(prn (count more) (get more 3) (nth more 0) (more 1))
(prn (assoc langs 2 "JVM"))
(prn (peek more) (pop more))
(prn (get langs 10) (get langs 10 :none))
(prn (subvec more 1 3))
(prn (= langs ["Lisp" "Scheme" "Java"]) (identical? langs more))
text
["Lisp" "Scheme" "Java"]
["Lisp" "Scheme" "Java" "Clojure"]
4 "Clojure" "Lisp" "Scheme"
["Lisp" "Scheme" "JVM"]
"Clojure" ["Lisp" "Scheme" "Java"]
nil :none
["Scheme" "Java"]
true false

The first two lines are the whole lesson in miniature: after conj, langs still has three elements. Other things to notice:

  • There are three ways to read by index: get, nth and calling the vector itself, (more 1). A vector is a function from index to element. get returns nil (or a default you supply) for an index out of range; nth and calling the vector throw an exception instead.
  • assoc on a vector replaces the element at an existing index.
  • peek and pop treat a vector as a stack whose top is the end.
  • subvec takes a slice in constant time; it shares structure with the original.
  • = compares by value: two vectors with the same elements in the same order are equal, wherever they came from. identical? asks whether two references point to the same object, which you will almost never need.

Maps

Maps are the workhorse of Clojure programs. Where another language would define a class with fields, Clojure usually uses a map with keyword keys.

clojure
(def student {:name "Amara" :city "Accra" :scores [88 92]})

(prn (:name student) (get student :city) (student :scores))
(prn (get student :email) (get student :email "no email"))

(def moved (assoc student :city "Kumasi" :year 2))
(prn moved)
(prn student)
(prn (dissoc moved :scores))
(prn (update student :scores conj 75))
(prn (contains? student :city) (keys student) (vals student))
(prn (merge {:lang "en" :theme "light"} {:theme "dark"}))
(prn (select-keys student [:name :city]))
text
"Amara" "Accra" [88 92]
nil "no email"
{:name "Amara", :city "Kumasi", :scores [88 92], :year 2}
{:name "Amara", :city "Accra", :scores [88 92]}
{:name "Amara", :city "Kumasi", :year 2}
{:name "Amara", :city "Accra", :scores [88 92 75]}
true (:name :city :scores) ("Amara" "Accra" [88 92])
{:lang "en", :theme "dark"}
{:name "Amara", :city "Accra"}
  • Keywords are functions that look themselves up in a map: (:name student) is the idiomatic way to read a field. Maps are functions too, (student :scores), which is handy when the key is not a keyword.
  • A missing key gives nil, or the default you pass to get.
  • assoc adds or replaces any number of key-value pairs; dissoc removes keys.
  • update takes a key and a function and applies the function to the current value. (update student :scores conj 75) calls (conj [88 92] 75) and stores the result. Extra arguments after the function are passed along to it.
  • merge combines maps, with later maps winning on conflicts, a common way to apply defaults.

Printed maps put a comma between entries; remember that commas are whitespace. Small maps (up to eight entries) happen to keep insertion order, but larger ones do not, and no program should depend on map order.

Nested data

Real data nests. A path of keys reaches inside:

clojure
(def library
  {:name "Riverside"
   :books {"978-1" {:title "Kindred" :copies 2}
           "978-2" {:title "Things Fall Apart" :copies 1}}})

(prn (get-in library [:books "978-2" :title]))

(def after-loan (update-in library [:books "978-2" :copies] dec))
(prn (get-in after-loan [:books "978-2"]))
(prn (get-in library [:books "978-2"]))

(def bigger (assoc-in library [:books "978-3"] {:title "Pedro Paramo" :copies 3}))
(prn (keys (:books bigger)))
(prn (keys (:books library)))
(prn (identical? (get-in library [:books "978-1"])
                 (get-in bigger [:books "978-1"])))
text
"Things Fall Apart"
{:title "Things Fall Apart", :copies 0}
{:title "Things Fall Apart", :copies 1}
("978-1" "978-2" "978-3")
("978-1" "978-2")
true

get-in, assoc-in and update-in are the nested versions of get, assoc and update. Lending a book produced a new library in which one count went down, while library still describes the world before the loan. The last line shows structural sharing directly: the record for "Kindred" in bigger is not a copy but the same object as in library, because nothing about it changed.

Sets, lists and moving between collections

clojure
(require '[clojure.set :as set])

(def warm #{:red :orange :yellow})
(def flag #{:red :white :green})

(println (conj warm :red) (count (conj warm :red)))
(println (disj warm :orange))
(println (warm :red) (warm :blue) (contains? flag :white))
(println (set/union warm flag))
(println (set/intersection warm flag) (set/difference warm flag))

(println (conj '(2 3) 1) (conj [2 3] 1))
(println (= [1 2 3] '(1 2 3)) (= [1 2 3] #{1 2 3}) (= {:a 1 :b 2} {:b 2 :a 1}))
(println (into [] '(3 1 2)) (into #{} [1 1 2 2]) (into {} [[:a 1] [:b 2]]))
(println (get {[0 0] :origin [1 0] :east} [1 0]))
text
#{:orange :yellow :red} 3
#{:yellow :red}
:red nil true
#{:orange :white :yellow :green :red}
#{:red} #{:orange :yellow}
(1 2 3) [2 3 1]
true false true
[3 1 2] #{1 2} {:a 1, :b 2}
:east
  • Adding an element a set already has changes nothing. A set called as a function returns the element if present and nil if not, which makes sets convenient predicates.
  • The clojure.set namespace, loaded with require, has the set algebra. Sets print in an order that depends on hashing; yours may differ.
  • conj adds where it is cheapest for each collection: at the front of a list and the end of a vector. This catches everyone once.
  • Equality is about contents: a vector and a list with the same elements in order are = (both are sequential), but a vector is never equal to a set, and maps are equal when they hold the same pairs, in any order.
  • into pours the elements of one collection into another and is the standard way to convert.
  • Because collections are immutable values with stable hashes, they make perfect map keys: here a coordinate pair [1 0] looks up a direction.
ComputationC

What each operation costs

Persistent collections are not free, but their costs are predictable. In the table, nn is the size of the collection; "log⁡32n\log_{32} n" is at most about 6 for any collection that fits in memory, so in practice it behaves like a small constant.

OperationVectorMap / setList
countO(1)O(1)O(1)O(1)O(1)O(1)
conjO(1)O(1) amortised, at the endO(log⁡32n)O(\log_{32} n)O(1)O(1), at the front
lookup (get, nth, contains?)O(log⁡32n)O(\log_{32} n)O(log⁡32n)O(\log_{32} n)O(n)O(n)
assoc / dissocO(log⁡32n)O(\log_{32} n)O(log⁡32n)O(\log_{32} n)not supported
first, restO(1)O(1)O(1)O(1)O(1)O(1)

Compared with a mutable Java ArrayList or HashMap, a persistent update typically does a few more memory allocations, so tight loops that build large collections are somewhat slower. When profiling shows that this matters, Clojure offers transients: a temporary mutable version of a collection, used inside one function and then frozen again.

clojure
(defn squares [n]
  (persistent!                          ; freeze the result: O(1)
    (reduce (fn [v i] (conj! v (* i i)))
            (transient [])              ; a mutable scratch vector: O(1)
            (range n))))

The function as a whole is still pure: nobody outside it ever sees the mutable version. Many core functions, including into, already use transients internally, so reach for them only when measurement says so.

Common misconceptionsH

Common mistakes

Misconception

Calling assoc and ignoring the result. (assoc student :city "Kumasi") on a line of its own does nothing useful: it builds a new map and throws it away. In Clojure you always use the return value, by passing it on, binding it with let, or returning it.

Misconception

Using contains? to search a vector. contains? asks whether a key is present. For a vector, the keys are indexes, so (contains? [10 20 30] 20) is false (there is no index 20) and (contains? [10 20 30] 2) is true. To ask whether a value is present, use a set, or (some #{20} [10 20 30]), which you will understand after lesson 3.

Misconception

Expecting conj to append to a list. It adds at the front of lists and seqs and at the end of vectors. If order matters and you are appending, you want a vector.

Misconception

Thinking immutability means copying everything. Structural sharing means an update copies a few small nodes, not the collection. Treat updates as cheap and copy-free, and measure before reaching for transients or Java collections.

ExplanationH

How professionals model data

Clojure teams lean heavily on a few habits that follow from immutable data.

Plain maps over custom types. A customer, an order or an HTTP request is just a map with keyword keys. Every function in the core library (assoc, update, select-keys, merge, get-in) then works on every entity in your system, and data printed with prn can be pasted straight back into the REPL as a test case. Lesson 5 develops this into a whole design style.

Snapshots for free. Because old versions stay valid, keeping a history of states (an undo stack, an audit trail, the "before" and "after" of a transaction) costs only a list of references. Several Clojure tools and databases are built around this property.

Collections as keys and as functions. Sets of allowed values double as predicates ((#{:admin :editor} role)), and keywords double as accessors, which keeps code short without special syntax.

Prefer the narrowest collection. Use a set when only membership matters, a vector when order and indexing matter, and a map when items have names. Code that picks the right collection tends to need no explanation.

Optional Christian reflection · Things that do not change

A reflection from the Christian tradition that inspires Lumenary Academy. It is not part of the mathematics and you are welcome to skip it.

Rich Hickey likes to point out that the past does not change: once something has happened, it is a fact, and a good information system should treat it as one rather than overwriting it. Many traditions treat faithfulness the same way, valuing a promise kept and a record left true. There is something restful in a data structure that will be tomorrow exactly what it is today, and in a program whose parts can trust one another because nothing is quietly altered behind their backs.

Exercises

Exercises

1. Immutable, persistent data

Warm-upComputational

What does this program print?

(prn (conj '(:b :c) :a) (conj [:b :c] :a))

2. Immutable, persistent data

Warm-upComputational

What does this program print?

(def a [1 2 3])
(def b (assoc a 0 99))
(prn a b)

3. Immutable, persistent data

CoreComputational

What does (contains? [10 20 30] 20) return, and why?

Choose one

4. Immutable, persistent data

Warm-upComputational

What does (count (into #{} [3 1 3 2 1])) return?

5. Immutable, persistent data

CoreComputational

What does this print?

(prn (update-in {:stock {:apples 5}} [:stock :apples] + 10))

6. Immutable, persistent data

CoreComputational

Which of these are true? List their letters.

  • A: (= [1 2] '(1 2))
  • B: (= [1 2] [2 1])
  • C: (= #{1 2} #{2 1})
  • D: (= {:a 1} {:a 1.0})
  • E: (= [[1] {:x #{2}}] [[1] {:x #{2}}])

Write elements separated by commas. Order and repeats don’t matter — just like in a set!

7. Immutable, persistent data

StretchComputational

What does this print?

(prn (get {:a nil} :a :missing) (get {} :a :missing))

8. Immutable, persistent data

CoreHuman

A voting app must answer, thousands of times a second, "has this user id already voted?" Which collection fits best?

Choose one

Further reading and resources