# The Common Lisp Cookbook – Data structures

đź“ą NEW! Learn Lisp in videos and support our contributors with this 40% discount. Recently added: the condition system.

We hope to give here a clear reference of the common data structures. To really learn the language, you should take the time to read other resources. The following resources, which we relied upon, also have many more details:

Donâ€™t miss the appendix and when you need more data structures, have a look at the awesome-cl list and Quickdocs.

## Lists

### Building lists. Cons cells, lists.

A list is also a sequence, so we can use the functions shown below.

The list basic element is the cons cell. We build lists by assembling cons cells.

``````(cons 1 2)
;; => (1 . 2) ;; representation with a point, a dotted pair.
``````

It looks like this:

``````[o|o]--- 2
|
1
``````

If the `cdr` of the first cell is another cons cell, and if the `cdr` of this last one is `nil`, we build a list:

``````(cons 1 (cons 2 nil))
;; => (1 2)
``````

It looks like this:

``````[o|o]---[o|/]
|       |
1       2
``````

(ascii art by draw-cons-tree).

See that the representation is not a dotted pair ? The Lisp printer understands the convention.

Finally we can simply build a literal list with `list`:

``````(list 1 2)
;; => (1 2)
``````

or by calling quote:

``````'(1 2)
;; => (1 2)
``````

which is shorthand notation for the function call `(quote (1 2))`.

### Circular lists

A cons cell car or cdr can refer to other objects, including itself or other cells in the same list. They can therefore be used to define self-referential structures such as circular lists.

Before working with circular lists, tell the printer to recognise them and not try to print the whole list by setting *print-circle* to `T`:

``````(setf *print-circle* t)
``````

A function which modifies a list, so that the last `cdr` points to the start of the list is:

``````(defun circular! (items)
"Modifies the last cdr of list ITEMS, returning a circular list"
(setf (cdr (last items)) items))

(circular! (list 1 2 3))
;; => #1=(1 2 3 . #1#)

(fifth (circular! (list 1 2 3)))
;; => 2
``````

The list-length function recognises circular lists, returning `nil`.

The reader can also create circular lists, using Sharpsign Equal-Sign notation. An object (like a list) can be prefixed with `#n=` where `n` is an unsigned decimal integer (one or more digits). The label `#n#` can be used to refer to the object later in the expression:

``````'#42=(1 2 3 . #42#)
;; => #1=(1 2 3 . #1#)
``````

Note that the label given to the reader (`n=42`) is discarded after reading, and the printer defines a new label (`n=1`).

### car/cdr or first/rest (and secondâ€¦ to tenth)

``````(car (cons 1 2)) ;; => 1
(cdr (cons 1 2)) ;; => 2
(first (cons 1 2)) ;; => 1
(first '(1 2 3)) ;; => 1
(rest '(1 2 3)) ;; => (2 3)
``````

We can assign any new value with `setf`.

### last, butlast, nbutlast (&optional n)

return the last cons cell in a list (or the nth last cons cells).

``````(last '(1 2 3))
;; => (3)
(car (last '(1 2 3)) ) ;; or (first (last â€¦))
;; => 3
(butlast '(1 2 3))
;; => (1 2)
``````

In Alexandria, `lastcar` is equivalent of `(first (last â€¦))`:

``````(alexandria:lastcar '(1 2 3))
;; => 3
``````

### reverse, nreverse

`reverse` and `nreverse` return a new sequence.

`nreverse` is destructive. The N stands for non-consing, meaning it doesnâ€™t need to allocate any new cons cells. It might (but in practice, does) reuse and modify the original sequence:

``````(defparameter mylist '(1 2 3))
;; => (1 2 3)
(reverse mylist)
;; => (3 2 1)
mylist
;; => (1 2 3)
(nreverse mylist)
;; => (3 2 1)
mylist
;; => (1) in SBCL but implementation dependent.
``````

### append

`append` takes any number of list arguments and returns a new list containing the elements of all its arguments:

``````(append (list 1 2) (list 3 4))
;; => (1 2 3 4)
``````

The new list shares some cons cells with the `(3 4)`:

http://gigamonkeys.com/book/figures/after-append.png

`nconc` is the recycling equivalent.

### push (item, place)

`push` prepends item to the list that is stored in place, stores the resulting list in place, and returns the list.

``````(defparameter mylist '(1 2 3))
(push 0 mylist)
;; => (0 1 2 3)
``````
``````(defparameter x â€™(a (b c) d))
;; => (A (B C) D)
;; => (5 B C)
x
;; => (A (5 B C) D)
``````

`push` is equivalent to `(setf place (cons item place ))` except that the subforms of place are evaluated only once, and item is evaluated before place.

There is no built-in function to add to the end of a list. It is a more costly operation (have to traverse the whole list). So if you need to do this: either consider using another data structure, either just `reverse` your list when needed.

### pop

a destructive operation.

### nthcdr (index, list)

Use this if `first`, `second` and the rest up to `tenth` are not enough.

They make sense when applied to lists containing other lists.

``````(caar (list 1 2 3))                  ==> error
(caar (list (list 1 2) 3))           ==> 1
(cadr (list (list 1 2) (list 3 4)))  ==> (3 4)
(caadr (list (list 1 2) (list 3 4))) ==> 3
``````

### destructuring-bind (parameter*, list)

It binds the parameter values to the list elements. We can destructure trees, plists and even provide defaults.

Simple matching:

``````(destructuring-bind (x y z) (list 1 2 3)
(list :x x :y y :z z))
;; => (:X 1 :Y 2 :Z 3)
``````

Matching inside sublists:

``````(destructuring-bind (x (y1 y2) z) (list 1 (list 2 20) 3)
(list :x x :y1 y1 :y2 y2 :z z))
;; => (:X 1 :Y1 2 :Y2 20 :Z 3)
``````

The parameter list can use the usual `&optional`, `&rest` and `&key` parameters.

``````(destructuring-bind (x (y1 &optional y2) z) (list 1 (list 2) 3)
(list :x x :y1 y1 :y2 y2 :z z))
;; => (:X 1 :Y1 2 :Y2 NIL :Z 3)
``````
``````(destructuring-bind (&key x y z) (list :z 1 :y 2 :x 3)
(list :x x :y y :z z))
;; => (:X 3 :Y 2 :Z 1)
``````

The `&whole` parameter is bound to the whole list. It must be the first one and others can follow.

``````(destructuring-bind (&whole whole-list &key x y z) (list :z 1 :y 2 :x 3)
(list :x x :y y :z z :whole whole-list))
;; => (:X 3 :Y 2 :Z 1 :WHOLE-LIST (:Z 1 :Y 2 :X 3))
``````

Destructuring a plist, giving defaults:

(example from Common Lisp Recipes, by E. Weitz, Apress, 2016)

``````(destructuring-bind (&key a (b :not-found) c
&allow-other-keys)
â€™(:c 23 :d "D" :a #\A :foo :whatever)
(list a b c))
;; => (#\A :NOT-FOUND 23)
``````

If this gives you the will to do pattern matching, see pattern matching.

### Predicates: null, listp

`null` is equivalent to `not`, but considered better style.

`listp` tests whether an object is a cons cell or nil.

and sequencesâ€™ predicates.

### ldiff, tailp, list*, make-list, fill, revappend, nreconc, consp, atom

``````(make-list 3 :initial-element "ta")
;; => ("ta" "ta" "ta")
``````
``````(make-list 3)
;; => (NIL NIL NIL)
(fill * "hello")
;; => ("hello" "hello" "hello")
``````

### member (elt, list)

Returns the tail of `list` beginning with the first element satisfying `eql`ity.

Accepts `:test`, `:test-not`, `:key` (functions or symbols).

``````(member 2 '(1 2 3))
;; (2 3)
``````

### Replacing objects in a tree: subst, sublis

subst and `subst-if` search and replace occurences of an element or subexpression in a tree (when it satisfies the optional `test`):

``````(subst 'one 1 '(1 2 3))
;; => (ONE 2 3)

(subst  '(1 . one) '(1 . 1) '((1 . 1) (2 . 2) (3 . 3)) :test #'equal)
;; ((1 . ONE) (2 . 2) (3 . 3))
``````

sublis allows to replace many objects at once. It substitutes the objects given in `alist` and found in `tree` with their new values given in the alist:

``````(sublis '((x . 10) (y . 20))
'(* x (+ x y) (* y y)))
;; (* 10 (+ 10 20) (* 20 20))
``````

`sublis` accepts the `:test` and `:key` arguments. `:test` is a function that takes two arguments, the key and the subtree.

``````(sublis '((t . "foo"))
'("one" 2 ("three" (4 5)))
:key #'stringp)
;; ("foo" 2 ("foo" (4 5)))
``````

## Sequences

lists and vectors (and thus strings) are sequences.

Many of the sequence functions take keyword arguments. All keyword arguments are optional and, if specified, may appear in any order.

Pay attention to the `:test` argument. It defaults to `eql` (for strings, use `:equal`).

The `:key` argument should be passed either nil, or a function of one argument. This key function is used as a filter through which the elements of the sequence are seen. For instance, this:

``````(find x y :key 'car)
``````

is similar to `(assoc* x y)`: It searches for an element of the list whose car equals x, rather than for an element which equals x itself. If `:key` is omitted or nil, the filter is effectively the identity function.

Example with an alist (see definition below):

``````(defparameter my-alist (list (cons 'foo "foo")
(cons 'bar "bar")))
;; => ((FOO . "foo") (BAR . "bar"))
(find 'bar my-alist)
;; => NIL
(find 'bar my-alist :key 'car)
;; => (BAR . "bar")
``````

For more, use a `lambda` that takes one parameter.

``````(find 'bar my-alist :key (lambda (it) (car it)))
``````
``````(find 'bar my-alist :key ^(car %))
(find 'bar my-alist :key (lm (it) (car it)))
``````

### Predicates: every, some,â€¦

`every, notevery (test, sequence)`: return nil or t, respectively, as soon as one test on any set of the corresponding elements of sequences returns nil.

``````(defparameter foo '(1 2 3))
(every #'evenp foo)
;; => NIL
(some #'evenp foo)
;; => T
``````

with a list of strings:

``````(defparameter str '("foo" "bar" "team"))
(every #'stringp str)
;; => T
(some (lambda (it) (= 3 (length it))) str)
;; => T
``````

`some`, `notany` (test, sequence): return either the value of the test, or nil.

### Functions

See also sequence functions defined in Alexandria: `starts-with`, `ends-with`, `ends-with-subseq`, `length=`, `emptyp`,â€¦

#### elt (sequence, index) - find by index

beware, here the sequence comes first.

#### count (foo sequence)

Return the number of elements in sequence that match foo.

Additional paramaters: `:from-end`, `:start`, `:end`.

See also `count-if`, `count-not` (test-function sequence).

#### subseq (sequence start, [end])

``````(subseq (list 1 2 3) 0)
;; (1 2 3)
(subseq (list 1 2 3) 1 2)
;; (2)
``````

However, watch out if the `end` is larger than the list:

``````(subseq (list 1 2 3) 0 99)
;; => Error: the bounding indices 0 and 99 are bad for a sequence of length 3.
``````

To this end, use `alexandria-2:subseq*`:

``````(alexandria-2:subseq* (list 1 2 3) 0 99)
;; (1 2 3)
``````

`subseq` is â€śsetfâ€ťable, but only works if the new sequence has the same length of the one to replace.

#### sort, stable-sort (sequence, test [, key function])

These sort functions are destructive, so one may prefer to copy the sequence with `copy-seq` before sorting:

``````(sort (copy-seq seq) :test #'string<)
``````

Unlike `sort`, `stable-sort` guarantees to keep the order of the argument. In theory, the result of this:

``````(sort '((1 :a) (1 :b)) #'< :key #'first)
``````

could be either `((1 :A) (1 :B))`, either `((1 :B) (1 :A))`. On my tests, the order is preserved, but the standard does not guarantee it.

#### find, position (foo, sequence) - get index

also `find-if`, `find-if-not`, `position-if`, `position-if-not` (test sequence). See `:key` and `:test` parameters.

``````(find 20 '(10 20 30))
;; 20
(position 20 '(10 20 30))
;; 1
``````

#### search and mismatch (sequence-a, sequence-b)

`search` searches in sequence-b for a subsequence that matches sequence-a. It returns the position in sequence-b, or NIL. It has the `from-end`, `end1`, `end2` and the usual `test` and `key` parameters.

``````(search '(20 30) '(10 20 30 40))
;; 1
(search '("b" "c") '("a" "b" "c"))
;; NIL
(search '("b" "c") '("a" "b" "c") :test #'equal)
;; 1
(search "bc" "abc")
;; 1
``````

`mismatch` returns the position where the two sequences start to differ:

``````(mismatch '(10 20 99) '(10 20 30))
;; 2
(mismatch "hellolisper" "helloworld")
;; 5
(mismatch "same" "same")
;; NIL
(mismatch "foo" "bar")
;; 0
``````

#### substitute, nsubstitute[if,if-not]

Return a sequence of the same kind as `sequence` with the same elements, except that all elements equal to `old` are replaced with `new`.

``````(substitute #\o #\x "hellx") ;; => "hello"
(substitute :a :x '(:a :x :x)) ;; => (:A :A :A)
(substitute "a" "x" '("a" "x" "x") :test #'string=) ;; => ("a" "a" "a")
``````

(see above)

#### replace (sequence-a, sequence-b, &key start1, end1)

Destructively replace elements of sequence-a with elements of sequence-b.

The full signature is:

``````(replace sequence1 sequence2 &rest args &key (start1 0) (end1 nil) (start2 0)
(end2 nil))
``````

Elements are copied to the subseqeuence bounded by START1 and END1, from the subsequence bounded by START2 and END2. If these subsequences are not of the same length, then the shorter length determines how many elements are copied.

``````(replace "xxx" "foo")
"foo"

(replace "xxx" "foo" :start1 1)
"xfo"

(replace "xxx" "foo" :start1 1 :start2 1)
"xoo"

(replace "xxx" "foo" :start1 1 :start2 1 :end2 2)
"xox"
``````

#### remove, delete (foo sequence)

Make a copy of sequence without elements matching foo. Has `:start/end`, `:key` and `:count` parameters.

`delete` is the recycling version of `remove`.

``````(remove "foo" '("foo" "bar" "foo") :test 'equal)
;; => ("bar")
``````

see also `remove-if[-not]` below.

#### remove-duplicates, delete-duplicates (sequence)

remove-duplicates returns a new sequence with uniq elements. `delete-duplicates` may modify the original sequence.

`remove-duplicates` accepts the following, usual arguments: ```from-end test test-not start end key```.

``````(remove-duplicates '(:foo :foo :bar))
(:FOO :BAR)

(remove-duplicates '("foo" "foo" "bar"))
("foo" "foo" "bar")

(remove-duplicates '("foo" "foo" "bar") :test #'string-equal)
("foo" "bar")
``````

### mapping (map, mapcar, remove-if[-not],â€¦)

If youâ€™re used to map and filter in other languages, you probably want `mapcar`. But it only works on lists, so to iterate on vectors (and produce either a vector or a list, use `(map 'list function vector)`.

mapcar also accepts multiple lists with `&rest more-seqs`. The mapping stops as soon as the shortest sequence runs out.

`map` takes the output-type as first argument (`'list`, `'vector` or `'string`):

``````(defparameter foo '(1 2 3))
(map 'list (lambda (it) (* 10 it)) foo)
``````

`reduce` (function, sequence). Special parameter: `:initial-value`.

``````(reduce '- '(1 2 3 4))
;; => -8
(reduce '- '(1 2 3 4) :initial-value 100)
;; => 90
``````

Filter is here called `remove-if-not`.

### Flatten a list (Alexandria)

With Alexandria, we have the `flatten` function.

### Creating lists with variables

Thatâ€™s one use of the `backquote`:

``````(defparameter *var* "bar")
;; First try:
'("foo" *var* "baz") ;; no backquote
;; => ("foo" *VAR* "baz") ;; nope
``````

Second try, with backquote interpolation:

```````("foo" ,*var* "baz")     ;; backquote, comma
;; => ("foo" "bar" "baz") ;; good
``````

The backquote first warns weâ€™ll do interpolation, the comma introduces the value of the variable.

If our variable is a list:

``````(defparameter *var* '("bar" "baz"))
;; First try:
`("foo" ,*var*)
;; => ("foo" ("bar" "baz")) ;; nested list
`("foo" ,@*var*)            ;;Â backquote, comma-@ to
;; => ("foo" "bar" "baz")
``````

E. Weitz warns that â€śobjects generated this way will very likely share structure (see Recipe 2-7)â€ť.

### Comparing lists

We can use sets functions.

## Set

We show below how to use set operations on lists.

A set doesnâ€™t contain twice the same element and is unordered.

Most of these functions have recycling (modifying) counterparts, starting with â€śnâ€ť: `nintersection`,â€¦ They all accept the usual `:key` and `:test` arguments, so use the test `#'string=` or `#'equal` if you are working with strings.

For more, see functions in Alexandria: `setp`, `set-equal`,â€¦ and the FSet library, shown in the next section.

### `intersection` of lists

What elements are both in list-a and list-b ?

``````(defparameter list-a '(0 1 2 3))
(defparameter list-b '(0 2 4))
(intersection list-a list-b)
;; => (2 0)
``````

### Remove the elements of list-b from list-a (`set-difference`)

``````(set-difference list-a list-b)
;; => (3 1)
(set-difference list-b list-a)
;; => (4)
``````

### Join two lists with uniq elements (`union`)

``````(union list-a list-b)
;; => (3 1 0 2 4) ;; order can be different in your lisp
``````

### Remove elements that are in both lists (`set-exclusive-or`)

``````(set-exclusive-or list-a list-b)
;; => (4 3 1)
``````

### Add an element to a set (`adjoin`)

A new set is returned, the original set is not modified.

``````(adjoin 3 list-a)
;; => (0 1 2 3)   ;; <-- nothing was changed, 3 was already there.

;; => (5 0 1 2 3) ;; <-- element added in front.

list-a
;; => (0 1 2 3)  ;; <-- original list unmodified.
``````

### Check if this is a subset (`subsetp`)

``````(subsetp '(1 2 3) list-a)
;; => T

(subsetp '(1 1 1) list-a)
;; => T

(subsetp '(3 2 1) list-a)
;; => T

(subsetp '(0 3) list-a)
;; => T
``````

## Fset - immutable data structure

You may want to have a look at the FSet library (in Quicklisp).

## Arrays and vectors

Arrays have constant-time access characteristics.

They can be fixed or adjustable. A simple array is neither displaced (using `:displaced-to`, to point to another array) nor adjustable (`:adjust-array`), nor does it have a fill pointer (`fill-pointer`, that moves when we add or remove elements).

A vector is an array with rank 1 (of one dimension). It is also a sequence (see above).

A simple vector is a simple array that is also not specialized (it doesnâ€™t use `:element-type` to set the types of the elements).

### Create an array, one or many dimensions

`make-array` (sizes-list :adjustable bool)

`adjust-array` (array, sizes-list, :element-type, :initial-element)

### Access: aref (array i [j â€¦])

`aref` (array i j k â€¦) or `row-major-aref` (array i) equivalent to `(aref i i i â€¦)`.

The result is `setf`able.

``````(defparameter myarray (make-array '(2 2 2) :initial-element 1))
myarray
;; => #3A(((1 1) (1 1)) ((1 1) (1 1)))
(aref myarray 0 0 0)
;; => 1
(setf (aref myarray 0 0 0) 9)
;; => 9
(row-major-aref myarray 0)
;; => 9
``````

### Sizes

`array-total-size` (array): how many elements will fit in the array ?

`array-dimensions` (array): list containing the length of the arrayâ€™s dimensions.

`array-dimension` (array i): length of the ith dimension.

`array-rank` number of dimensions of the array.

``````(defparameter myarray (make-array '(2 2 2)))
;; => MYARRAY
myarray
;; => #3A(((0 0) (0 0)) ((0 0) (0 0)))
(array-rank myarray)
;; => 3
(array-dimensions myarray)
;; => (2 2 2)
(array-dimension myarray 0)
;; => 2
(array-total-size myarray)
;; => 8
``````

### Vectors

Create with `vector` or the reader macro `#()`. It returns a simple vector.

``````(vector 1 2 3)
;; => #(1 2 3)
#(1 2 3)
;; => #(1 2 3)
``````

`vector-push` (foo vector): replace the vector element pointed to by the fill pointer by foo. Can be destructive.

`vector-push-extend` (foo vector [extension-num])t

`vector-pop` (vector): return the element of vector its fill pointer points to.

`fill-pointer` (vector). `setf`able.

### Transforming a vector to a list.

If youâ€™re mapping over it, see the `map` function whose first parameter is the result type.

Or use `(coerce vector 'list)`.

## Hash Table

Hash Tables are a powerful data structure, associating keys with values in a very efficient way. Hash Tables are often preferred over association lists whenever performance is an issue, but they introduce a little overhead that makes assoc lists better if there are only a few key-value pairs to maintain.

Alists can be used sometimes differently though:

• they can be ordered
• we can push cons cells that have the same key, remove the one in front and we have a stack
• they have a human-readable printed representation
• they can be easily (de)serialized
• because of RASSOC, keys and values in alists are essentially interchangeable; whereas in hash tables, keys and values play very different roles (as usual, see CL Recipes for more).

### Creating a Hash Table

Hash Tables are created using the function `make-hash-table`. It has no required argument. Its most used optional keyword argument is `:test`, specifying the function used to test the equality of keys.

Note: see shorter notations in the Serapeum or Rutils libraries. For example, Serapeum has `dict`, and Rutils a `#h` reader macro.

### Adding an Element to a Hash Table

If you want to add an element to a hash table, you can use `gethash`, the function to retrieve elements from the hash table, in conjunction with `setf`.

``````CL-USER> (defparameter *my-hash* (make-hash-table))
*MY-HASH*
CL-USER> (setf (gethash 'one-entry *my-hash*) "one")
"one"
CL-USER> (setf (gethash 'another-entry *my-hash*) 2/4)
1/2
CL-USER> (gethash 'one-entry *my-hash*)
"one"
T
CL-USER> (gethash 'another-entry *my-hash*)
1/2
T
``````

With Serapeumâ€™s `dict`, we can create a hash-table and add elements to it in one go:

``````(defparameter *my-hash* (dict :one-entry "one" :another-entry 2/4))
;; =>
(dict
:ONE-ENTRY "one"
:ANOTHER-ENTRY 1/2
)
``````

### Getting a value from a Hash Table

The function `gethash` takes two required arguments: a key and a hash table. It returns two values: the value corresponding to the key in the hash table (or `nil` if not found), and a boolean indicating whether the key was found in the table. That second value is necessary since `nil` is a valid value in a key-value pair, so getting `nil` as first value from `gethash` does not necessarily mean that the key was not found in the table.

#### Getting a key that does not exist with a default value

`gethash` has an optional third argument:

``````(gethash 'bar *my-hash* "default-bar")
;; => "default-bar"
;;     NIL
``````

#### Getting all keys or all values of a hash table

The Alexandria library (in Quicklisp) has the functions `hash-table-keys` and `hash-table-values` for that.

``````(ql:quickload "alexandria")
;; [â€¦]
(alexandria:hash-table-keys *my-hash*)
;; => (BAR)
``````

### Testing for the Presence of a Key in a Hash Table

The first value returned by `gethash` is the object in the hash table thatâ€™s associated with the key you provided as an argument to `gethash` or `nil` if no value exists for this key. This value can act as a generalized boolean if you want to test for the presence of keys.

``````CL-USER> (defparameter *my-hash* (make-hash-table))
*MY-HASH*
CL-USER> (setf (gethash 'one-entry *my-hash*) "one")
"one"
CL-USER> (if (gethash 'one-entry *my-hash*)
"Key exists"
"Key does not exist")
"Key exists"
CL-USER> (if (gethash 'another-entry *my-hash*)
"Key exists"
"Key does not exist")
"Key does not exist"
``````

But note that this does not work if `nil` is amongst the values that you want to store in the hash.

``````CL-USER> (setf (gethash 'another-entry *my-hash*) nil)
NIL
CL-USER> (if (gethash 'another-entry *my-hash*)
"Key exists"
"Key does not exist")
"Key does not exist"
``````

In this case youâ€™ll have to check the second return value of `gethash` which will always return `nil` if no value is found and T otherwise.

``````CL-USER> (if (nth-value 1 (gethash 'another-entry *my-hash*))
"Key exists"
"Key does not exist")
"Key exists"
CL-USER> (if (nth-value 1 (gethash 'no-entry *my-hash*))
"Key exists"
"Key does not exist")
"Key does not exist"
``````

### Deleting from a Hash Table

Use `remhash` to delete a hash entry. Both the key and its associated value will be removed from the hash table. `remhash` returns T if there was such an entry, `nil` otherwise.

``````CL-USER> (defparameter *my-hash* (make-hash-table))
*MY-HASH*
CL-USER> (setf (gethash 'first-key *my-hash*) 'one)
ONE
CL-USER> (gethash 'first-key *my-hash*)
ONE
T
CL-USER> (remhash 'first-key *my-hash*)
T
CL-USER> (gethash 'first-key *my-hash*)
NIL
NIL
CL-USER> (gethash 'no-entry *my-hash*)
NIL
NIL
CL-USER> (remhash 'no-entry *my-hash*)
NIL
CL-USER> (gethash 'no-entry *my-hash*)
NIL
NIL
``````

### Deleting a Hash Table

Use `clrhash` to delete a hash table. This will remove all of the data from the hash table and return the deleted table.

``````CL-USER> (defparameter *my-hash* (make-hash-table))
*MY-HASH*
CL-USER> (setf (gethash 'first-key *my-hash*) 'one)
ONE
CL-USER> (setf (gethash 'second-key *my-hash*) 'two)
TWO
CL-USER> *my-hash*
#<hash-table :TEST eql :COUNT 2 {10097BF4E3}>
CL-USER> (clrhash *my-hash*)
#<hash-table :TEST eql :COUNT 0 {10097BF4E3}>
CL-USER> (gethash 'first-key *my-hash*)
NIL
NIL
CL-USER> (gethash 'second-key *my-hash*)
NIL
NIL
``````

### Traversing a Hash Table

If you want to perform an action on each entry (i.e., each key-value pair) in a hash table, you have several options:

You can use `maphash` which iterates over all entries in the hash table. Its first argument must be a function which accepts two arguments, the key and the value of each entry. Note that due to the nature of hash tables you canâ€™t control the order in which the entries are provided by `maphash` (or other traversing constructs). `maphash` always returns `nil`.

``````CL-USER> (defparameter *my-hash* (make-hash-table))
*MY-HASH*
CL-USER> (setf (gethash 'first-key *my-hash*) 'one)
ONE
CL-USER> (setf (gethash 'second-key *my-hash*) 'two)
TWO
CL-USER> (setf (gethash 'third-key *my-hash*) nil)
NIL
CL-USER> (setf (gethash nil *my-hash*) 'nil-value)
NIL-VALUE
CL-USER> (defun print-hash-entry (key value)
(format t "The value associated with the key ~S is ~S~%" key value))
PRINT-HASH-ENTRY
CL-USER> (maphash #'print-hash-entry *my-hash*)
The value associated with the key FIRST-KEY is ONE
The value associated with the key SECOND-KEY is TWO
The value associated with the key THIRD-KEY is NIL
The value associated with the key NIL is NIL-VALUE
``````

You can also use `with-hash-table-iterator`, a macro which turns (via `macrolet`) its first argument into an iterator that on each invocation returns three values per hash table entry - a generalized boolean thatâ€™s true if an entry is returned, the key of the entry, and the value of the entry. If there are no more entries, only one value is returned - `nil`.

``````;;; same hash-table as above
CL-USER> (with-hash-table-iterator (my-iterator *my-hash*)
(loop
(multiple-value-bind (entry-p key value)
(my-iterator)
(if entry-p
(print-hash-entry key value)
(return)))))
The value associated with the key FIRST-KEY is ONE
The value associated with the key SECOND-KEY is TWO
The value associated with the key THIRD-KEY is NIL
The value associated with the key NIL is NIL-VALUE
NIL
``````

Note the following caveat from the HyperSpec: â€śIt is unspecified what happens if any of the implicit interior state of an iteration is returned outside the dynamic extent of the `with-hash-table-iterator` form such as by returning some closure over the invocation form.â€ť

And thereâ€™s always `loop`:

``````;;; same hash-table as above
CL-USER> (loop for key being the hash-keys of *my-hash*
do (print key))
FIRST-KEY
SECOND-KEY
THIRD-KEY
NIL
NIL
CL-USER> (loop for key being the hash-keys of *my-hash*
using (hash-value value)
do (format t "The value associated with the key ~S is ~S~%" key value))
The value associated with the key FIRST-KEY is ONE
The value associated with the key SECOND-KEY is TWO
The value associated with the key THIRD-KEY is NIL
The value associated with the key NIL is NIL-VALUE
NIL
CL-USER> (loop for value being the hash-values of *my-hash*
do (print value))
ONE
TWO
NIL
NIL-VALUE
NIL
CL-USER> (loop for value being the hash-values of *my-hash*
using (hash-key key)
do (format t "~&~A -> ~A" key value))
FIRST-KEY -> ONE
SECOND-KEY -> TWO
THIRD-KEY -> NIL
NIL -> NIL-VALUE
NIL
``````

#### Traversing keys or values

To map over keys or values we can again rely on Alexandria with `maphash-keys` and `maphash-values`.

### Counting the Entries in a Hash Table

No need to use your fingers - Common Lisp has a built-in function to do it for you: `hash-table-count`.

``````CL-USER> (defparameter *my-hash* (make-hash-table))
*MY-HASH*
CL-USER> (hash-table-count *my-hash*)
0
CL-USER> (setf (gethash 'first *my-hash*) 1)
1
CL-USER> (setf (gethash 'second *my-hash*) 2)
2
CL-USER> (setf (gethash 'third *my-hash*) 3)
3
CL-USER> (hash-table-count *my-hash*)
3
CL-USER> (setf (gethash 'second *my-hash*) 'two)
TWO
CL-USER> (hash-table-count *my-hash*)
3
CL-USER> (clrhash *my-hash*)
#<EQL hash table, 0 entries {48205F35}>
CL-USER> (hash-table-count *my-hash*)
0
``````

### Printing a Hash Table readably

With print-object (non portable)

It is very tempting to use `print-object`. It works under several implementations, but this method is actually not portable. The standard doesnâ€™t permit to do so, so this is undefined behaviour.

``````(defmethod print-object ((object hash-table) stream)
(format stream "#HASH{~{~{(~a : ~a)~}~^ ~}}"
(loop for key being the hash-keys of object
using (hash-value value)
collect (list key value))))

;; WARNING:
;;   redefining PRINT-OBJECT (#<STRUCTURE-CLASS COMMON-LISP:HASH-TABLE>
;;                            #<SB-PCL:SYSTEM-CLASS COMMON-LISP:T>) in DEFMETHOD
;; #<STANDARD-METHOD COMMON-LISP:PRINT-OBJECT (HASH-TABLE T) {1006A0D063}>
``````

and letâ€™s try it:

``````(let ((ht (make-hash-table)))
(setf (gethash :foo ht) :bar)
ht)
;; #HASH{(FOO : BAR)}
``````

With a custom function (portable way)

Hereâ€™s a portable way.

This snippets prints the keys, values and the test function of a hash-table, and uses `alexandria:alist-hash-table` to read it back in:

``````;; https://github.com/phoe/phoe-toolbox/blob/master/phoe-toolbox.lisp
&optional (stream *standard-output*))
"Prints a hash table readably using ALEXANDRIA:ALIST-HASH-TABLE."
(let ((test (hash-table-test hash-table))
(*print-circle* t)
(format stream "#.(ALEXANDRIA:ALIST-HASH-TABLE '(~%")
(maphash (lambda (k v) (format stream "   (~S . ~S)~%" k v)) hash-table)
(format stream "   ) :TEST '~A)" test)
hash-table))
``````

Example output:

``````#.(ALEXANDRIA:ALIST-HASH-TABLE
'((ONE . 1))
:TEST 'EQL)
#<HASH-TABLE :TEST EQL :COUNT 1 {10046D4863}>
``````

This output can be read back in to create a hash-table:

``````(read-from-string
(with-output-to-string (s)
(alexandria:alist-hash-table
'((a . 1) (b . 2) (c . 3))) s)))
;; #<HASH-TABLE :TEST EQL :COUNT 3 {1009592E23}>
;; 83
``````

The Serapeum library has the `dict` constructor, the function `pretty-print-hash-table` and the `toggle-pretty-print-hash-table` switch, all which do not use `print-object` under the hood.

``````CL-USER> (serapeum:toggle-pretty-print-hash-table)
T
CL-USER> (serapeum:dict :a 1 :b 2 :c 3)
(dict
:A 1
:B 2
:C 3
)
``````

This printed representation can be read back in.

The standard hash-table in Common Lisp is not thread-safe. That means that simple access operations can be interrupted in the middle and return a wrong result.

Implementations offer different solutions.

With SBCL, we can create thread-safe hash tables with the `:synchronized` keyword to `make-hash-table`: http://www.sbcl.org/manual/#Hash-Table-Extensions.

If nil (the default), the hash-table may have multiple concurrent readers, but results are undefined if a thread writes to the hash-table concurrently with another reader or writer. If t, all concurrent accesses are safe, but note that clhs 3.6 (Traversal Rules and Side Effects) remains in force. See also: sb-ext:with-locked-hash-table.

``````(defparameter *my-hash* (make-hash-table :synchronized t))
``````

But, operations that expand to two accesses, like the modify macros (`incf`) or this:

``````(setf (gethash :a *my-hash*) :new-value)
``````

need to be wrapped around `sb-ext:with-locked-hash-table`:

Limits concurrent accesses to HASH-TABLE for the duration of BODY. If HASH-TABLE is synchronized, BODY will execute with exclusive ownership of the table. If HASH-TABLE is not synchronized, BODY will execute with other WITH-LOCKED-HASH-TABLE bodies excluded â€“ exclusion of hash-table accesses not surrounded by WITH-LOCKED-HASH-TABLE is unspecified.

``````(sb-ext:with-locked-hash-table (*my-hash*)
(setf (gethash :a *my-hash*) :new-value))
``````

In LispWorks, hash-tables are thread-safe by default. But likewise, there is no guarantee of atomicity between access operations, so we can use with-hash-table-locked.

Ultimately, you might like what the cl-gserver library proposes. It offers helper functions around hash-tables and its actors/agent system to allow thread-safety. They also maintain the order of updates and reads.

### Performance Issues: The Size of your Hash Table

The `make-hash-table` function has a couple of optional parameters which control the initial size of your hash table and how itâ€™ll grow if it needs to grow. This can be an important performance issue if youâ€™re working with large hash tables. Hereâ€™s an (admittedly not very scientific) example with CMUCL pre-18d on Linux:

``````CL-USER> (defparameter *my-hash* (make-hash-table))
*MY-HASH*
CL-USER> (hash-table-size *my-hash*)
65
CL-USER> (hash-table-rehash-size *my-hash*)
1.5
CL-USER> (time (dotimes (n 100000) (setf (gethash n *my-hash*) n)))
Compiling LAMBDA NIL:
Compiling Top-Level Form:

Evaluation took:
0.27 seconds of real time
0.25 seconds of user run time
0.02 seconds of system run time
0 page faults and
8754768 bytes consed.
NIL
CL-USER> (time (dotimes (n 100000) (setf (gethash n *my-hash*) n)))
Compiling LAMBDA NIL:
Compiling Top-Level Form:

Evaluation took:
0.05 seconds of real time
0.05 seconds of user run time
0.0 seconds of system run time
0 page faults and
0 bytes consed.
NIL
``````

The values for `hash-table-size` and `hash-table-rehash-size` are implementation-dependent. In our case, CMUCL chooses and initial size of 65, and it will increase the size of the hash by 50 percent whenever it needs to grow. Letâ€™s see how often we have to re-size the hash until we reach the final sizeâ€¦

``````CL-USER> (log (/ 100000 65) 1.5)
18.099062
CL-USER> (let ((size 65)) (dotimes (n 20) (print (list n size)) (setq size (* 1.5 size))))
(0 65)
(1 97.5)
(2 146.25)
(3 219.375)
(4 329.0625)
(5 493.59375)
(6 740.3906)
(7 1110.5859)
(8 1665.8789)
(9 2498.8184)
(10 3748.2275)
(11 5622.3413)
(12 8433.512)
(13 12650.268)
(14 18975.402)
(15 28463.104)
(16 42694.656)
(17 64041.984)
(18 96062.98)
(19 144094.47)
NIL
``````

The hash has to be re-sized 19 times until itâ€™s big enough to hold 100,000 entries. That explains why we saw a lot of consing and why it took rather long to fill the hash table. It also explains why the second run was much faster - the hash table already had the correct size.

Hereâ€™s a faster way to do it: If we know in advance how big our hash will be, we can start with the right size:

``````CL-USER> (defparameter *my-hash* (make-hash-table :size 100000))
*MY-HASH*
CL-USER> (hash-table-size *my-hash*)
100000
CL-USER> (time (dotimes (n 100000) (setf (gethash n *my-hash*) n)))
Compiling LAMBDA NIL:
Compiling Top-Level Form:

Evaluation took:
0.04 seconds of real time
0.04 seconds of user run time
0.0 seconds of system run time
0 page faults and
0 bytes consed.
NIL
``````

Thatâ€™s obviously much faster. And there was no consing involved because we didnâ€™t have to re-size at all. If we donâ€™t know the final size in advance but can guess the growth behaviour of our hash table we can also provide this value to `make-hash-table`. We can provide an integer to specify absolute growth or a float to specify relative growth.

``````CL-USER> (defparameter *my-hash* (make-hash-table :rehash-size 100000))
*MY-HASH*
CL-USER> (hash-table-size *my-hash*)
65
CL-USER> (hash-table-rehash-size *my-hash*)
100000
CL-USER> (time (dotimes (n 100000) (setf (gethash n *my-hash*) n)))
Compiling LAMBDA NIL:
Compiling Top-Level Form:

Evaluation took:
0.07 seconds of real time
0.05 seconds of user run time
0.01 seconds of system run time
0 page faults and
2001360 bytes consed.
NIL
``````

Also rather fast (we only needed one re-size) but much more consing because almost the whole hash table (minus 65 initial elements) had to be built during the loop.

Note that you can also specify the `rehash-threshold` while creating a new hash table. One final remark: Your implementation is allowed to completely ignore the values provided for `rehash-size` and `rehash-threshold`â€¦

## Alist

### Definition

An association list is a list of cons cells.

This simple example:

``````(defparameter *my-alist* (list (cons 'foo "foo")
(cons 'bar "bar")))
;; => ((FOO . "foo") (BAR . "bar"))
``````

looks like this:

``````[o|o]---[o|/]
|       |
|      [o|o]---"bar"
|       |
|      BAR
|
[o|o]---"foo"
|
FOO
``````

### Construction

We can construct an alist like its representation:

``````(setf *my-alist* '((:foo . "foo")
(:bar . "bar")))
``````

The constructor `pairlis` associates a list of keys and a list of values:

``````(pairlis '(:foo :bar)
'("foo" "bar"))
;; => ((:BAR . "bar") (:FOO . "foo"))
``````

Alists are just lists, so you can have the same key multiple times in the same alist:

``````(setf *alist-with-duplicate-keys*
'((:a . 1)
(:a . 2)
(:b . 3)
(:a . 4)
(:c . 5)))
``````

### Access

To get a key, we have `assoc` (use `:test 'equal` when your keys are strings, as usual). It returns the whole cons cell, so you may want to use `cdr` or `second` to get the value or even better `assoc-value list key` from `Alexandria`.

``````(alexandria:assoc-value *my-alist* :foo)
;; it actually returns 2 values
;; "foo"
;; (:FOO . "FOO")
``````

There is `assoc-if`, and `rassoc` to get a cons cell by its value.

If the alist has repeating (duplicate) keys, you can use `remove-if-not`, for example, to retrieve all of them.

``````(remove-if-not
(lambda (entry)
(eq :a entry))
*alist-with-duplicate-keys*
:key #'car)
``````

### Insert and remove entries

To add a key, we `push` another cons cell:

``````(push (cons 'team "team") *my-alist*)
;; => ((TEAM . "team") (FOO . "foo") (BAR . "bar"))
``````

We can use `pop` and other functions that operate on lists, like `remove`:

``````(remove :team *my-alist*)
;; => ((:TEAM . "team") (FOO . "foo") (BAR . "bar")) ;; didn't remove anything
(remove :team *my-alist* :key 'car)
;; => ((FOO . "foo") (BAR . "bar")) ;; returns a copy
``````

Remove only one element with `:count`:

``````(push (cons 'bar "bar2") *my-alist*)
;; => ((BAR . "bar2") (TEAM . "team") (FOO . "foo") (BAR . "bar")) ;; twice the 'bar key
(remove 'bar *my-alist* :key 'car :count 1)
;; => ((TEAM . "team") (FOO . "foo") (BAR . "bar"))
;; because otherwise:
(remove 'bar *my-alist* :key 'car)
;; => ((TEAM . "team") (FOO . "foo")) ;; no more 'bar
``````

### Update entries

Replace a value:

``````*my-alist*
;; => '((:FOO . "foo") (:BAR . "bar"))
(assoc :foo *my-alist*)
;; => (:FOO . "foo")
(setf (cdr (assoc :foo *my-alist*)) "new-value")
;; => "new-value"
*my-alist*
;; => '((:foo . "new-value") (:BAR . "bar"))
``````

Replace a key:

``````*my-alist*
;; => '((:FOO . "foo") (:BAR . "bar")))
(setf (car (assoc :bar *my-alist*)) :new-key)
;; => :NEW-KEY
*my-alist*
;; => '((:FOO . "foo") (:NEW-KEY . "bar")))
``````

In the Alexandria library, see more functions like `hash-table-alist`, `alist-plist`,â€¦

## Plist

A property list is simply a list that alternates a key, a value, and so on, where its keys are symbols (we can not set its `:test`). More precisely, it first has a cons cell whose `car` is the key, whose `cdr` points to the following cons cell whose `car` is the value.

For example this plist:

``````(defparameter my-plist (list 'foo "foo" 'bar "bar"))
``````

looks like this:

``````[o|o]---[o|o]---[o|o]---[o|/]
|       |       |       |
FOO     "foo"   BAR     "bar"

``````

We access an element with `getf (list elt)` (it returns the value) (the list comes as first element),

we remove an element with `remf`.

``````(defparameter my-plist (list 'foo "foo" 'bar "bar"))
;; => (FOO "foo" BAR "bar")
(setf (getf my-plist 'foo) "foo!!!")
;; => "foo!!!"
``````

## Structures

Structures offer a way to store data in named slots. They support single inheritance.

Classes provided by the Common Lisp Object System (CLOS) are more flexible however structures may offer better performance (see for example the SBCL manual).

### Creation

Use `defstruct`:

``````(defstruct person
id name age)
``````

At creation slots are optional and default to `nil`.

To set a default value:

``````(defstruct person
id
(name "john doe")
age)
``````

Also specify the type after the default value:

``````(defstruct person
id
(name "john doe" :type string)
age)
``````

We create an instance with the generated constructor `make-` + `<structure-name>`, so `make-person`:

``````(defparameter *me* (make-person))
*me*
#S(PERSON :ID NIL :NAME "john doe" :AGE NIL)
``````

``````(defparameter *bad-name* (make-person :name 123))
``````
``````Invalid initialization argument:
:NAME
in call for class #<STRUCTURE-CLASS PERSON>.
[Condition of type SB-PCL::INITARG-ERROR]
``````

We can set the structureâ€™s constructor so as to create the structure without using keyword arguments, which can be more convenient sometimes. We give it a name and the order of the arguments:

``````(defstruct (person (:constructor create-person (id name age)))
id
name
age)
``````

Our new constructor is `create-person`:

``````(create-person 1 "me" 7)
#S(PERSON :ID 1 :NAME "me" :AGE 7)
``````

However, the default `make-person` does not work any more:

``````(make-person :name "me")
;; debugger:
obsolete structure error for a structure of type PERSON
[Condition of type SB-PCL::OBSOLETE-STRUCTURE]
``````

### Slot access

We access the slots with accessors created by `<name-of-the-struct>-` + `slot-name`:

``````(person-name *me*)
;; "john doe"
``````

we then also have `person-age` and `person-id`.

### Setting

Slots are `setf`-able:

``````(setf (person-name *me*) "Cookbook author")
(person-name *me*)
;; "Cookbook author"
``````

### Predicate

A predicate function is generated:

``````(person-p *me*)
T
``````

### Single inheritance

Use single inheritance with the `:include <struct>` argument:

``````(defstruct (female (:include person))
(gender "female" :type string))
(make-female :name "Lilie")
;; #S(FEMALE :ID NIL :NAME "Lilie" :AGE NIL :GENDER "female")
``````

Note that the CLOS object system is more powerful.

### Limitations

After a change, instances are not updated.

If we try to add a slot (`email` below), we have the choice to lose all instances, or to continue using the new definition of `person`. But the effects of redefining a structure are undefined by the standard, so it is best to re-compile and re-run the changed code.

``````(defstruct person
id
(name "john doe" :type string)
age
email)

attempt to redefine the STRUCTURE-OBJECT class PERSON
incompatibly with the current definition
[Condition of type SIMPLE-ERROR]

Restarts:
0: [CONTINUE] Use the new definition of PERSON, invalidating already-loaded code and instances.
1: [RECKLESSLY-CONTINUE] Use the new definition of PERSON as if it were compatible, allowing old accessors to use new instances and allowing new accessors to use old instances.
2: [CLOBBER-IT] (deprecated synonym for RECKLESSLY-CONTINUE)
3: [RETRY] Retry SLIME REPL evaluation request.
``````

If we choose restart `0`, to use the new definition, we lose access to `*me*`:

``````*me*
obsolete structure error for a structure of type PERSON
[Condition of type SB-PCL::OBSOLETE-STRUCTURE]
``````

There is also very little introspection. Portable Common Lisp does not define ways of finding out defined super/sub-structures nor what slots a structure has.

The Common Lisp Object System (which came after into the language) doesnâ€™t have such limitations. See the CLOS section.

## Tree

`tree-equal`, `copy-tree`. They descend recursively into the car and the cdr of the cons cells they visit.

### Sycamore - purely functional weight-balanced binary trees

https://github.com/ndantam/sycamore

Features:

• Fast, purely functional weight-balanced binary trees.
• Leaf nodes are simple-vectors, greatly reducing tree height.
• Interfaces for tree Sets and Maps (dictionaries).
• Ropes
• Purely functional pairing heaps
• Purely functional amortized queue.

## Controlling how much of data to print (`*print-length*`, `*print-level*`)

Use `*print-length*` and `*print-level*`.

They are both `nil` by default.

If you have a very big list, printing it on the REPL or in a stacktrace can take a long time and bring your editor or even your server down. Use `*print-length*` to choose the maximum of elements of the list to print, and to show there is a rest with a `...` placeholder:

``````(setf *print-length* 2)
(list :A :B :C :D :E)
;; (:A :B ...)
``````

And if you have a very nested data structure, set `*print-level*` to choose the depth to print:

``````(let ((*print-level* 2))
(print '(:a (:b (:c (:d :e))))))
;; (:A (:B #))             <= *print-level* in action
;; (:A (:B (:C (:D :E))))  <= the list is returned, the let binding is not in effect anymore.
``````

`*print-length*` will be applied at each level.

Reference: the HyperSpec.

## Appendix A - generic and nested access of alists, plists, hash-tables and CLOS slots

The solutions presented below might help you getting started, but keep in mind that theyâ€™ll have a performance impact and that error messages will be less explicit.

• the access library (battle tested, used by the Djula templating system) has a generic `(access my-var :elt)` (blog post). It also has `accesses` (plural) to access and set nested values.
• rutils as a generic `generic-elt` or `?`,

## Appendix B - accessing nested data structures

Sometimes we work with nested data structures, and we might want an easier way to access a nested element than intricated â€śgetfâ€ť and â€śassocâ€ť and all. Also, we might want to just be returned a `nil` when an intermediary key doesnâ€™t exist.

The `access` library given above provides this, with `(accesses var key1 key2â€¦)`.

Page source: data-structures.md

T
O
C