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.
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.
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:
| Collection | Literal | Use it for | Adds with conj at |
|---|---|---|---|
| vector | [1 2 3] | ordered data you index into or append to | the 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 front | the 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.
Working with each collection
Vectors
(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))["Lisp" "Scheme" "Java"]
["Lisp" "Scheme" "Java" "Clojure"]
4 "Clojure" "Lisp" "Scheme"
["Lisp" "Scheme" "JVM"]
"Clojure" ["Lisp" "Scheme" "Java"]
nil :none
["Scheme" "Java"]
true falseThe 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,nthand calling the vector itself,(more 1). A vector is a function from index to element.getreturnsnil(or a default you supply) for an index out of range;nthand calling the vector throw an exception instead. assocon a vector replaces the element at an existing index.peekandpoptreat a vector as a stack whose top is the end.subvectakes 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.
(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]))"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 toget. assocadds or replaces any number of key-value pairs;dissocremoves keys.updatetakes 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.mergecombines 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:
(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"])))"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")
trueget-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
(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]))#{: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
nilif not, which makes sets convenient predicates. - The
clojure.setnamespace, loaded withrequire, has the set algebra. Sets print in an order that depends on hashing; yours may differ. conjadds 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. intopours 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.
What each operation costs
Persistent collections are not free, but their costs are predictable. In the table, is the size of the collection; "" is at most about 6 for any collection that fits in memory, so in practice it behaves like a small constant.
| Operation | Vector | Map / set | List |
|---|---|---|---|
count | |||
conj | amortised, at the end | , at the front | |
lookup (get, nth, contains?) | |||
assoc / dissoc | not supported | ||
first, rest |
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.
(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 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.
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
1. Immutable, persistent data
Warm-upComputationalWhat does this program print?
(prn (conj '(:b :c) :a) (conj [:b :c] :a))
2. Immutable, persistent data
Warm-upComputationalWhat does this program print?
(def a [1 2 3])
(def b (assoc a 0 99))
(prn a b)
3. Immutable, persistent data
CoreComputationalWhat does (contains? [10 20 30] 20) return, and why?
4. Immutable, persistent data
Warm-upComputationalWhat does (count (into #{} [3 1 3 2 1])) return?
5. Immutable, persistent data
CoreComputationalWhat does this print?
(prn (update-in {:stock {:apples 5}} [:stock :apples] + 10))
6. Immutable, persistent data
CoreComputationalWhich 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}}])
7. Immutable, persistent data
StretchComputationalWhat does this print?
(prn (get {:a nil} :a :missing) (get {} :a :missing))
8. Immutable, persistent data
CoreHumanA voting app must answer, thousands of times a second, "has this user id already voted?" Which collection fits best?
Further reading and resources
- Data structuresThe official reference for Clojure's collections and their interfaces.
- EqualityThe official guide to how = treats numbers, collections and Java objects.
- Values and change, Clojure's approach to identity and stateRich Hickey's essay on why values should not change.
- Clojure cheatsheetThe collection functions grouped by kind.