What the heck are alists and plists exactly, how do we manipulate data structures ? It seems tedious sometimes, are there helpers ?

Best read in the Cookbook.

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 ones, which we relied upon, have many more details:

Table of Contents

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)).

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)) )
;; => 3
(butlast '(1 2 3))
;; => (1 2)

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 dependant.

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

Note: cl21’s append is generic (for strings, lists, vectors and its abstract-sequence).

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)
(push 5 (cadr x))
;; => (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.

car/cdr and composites (cadr, caadr…) - accessing lists inside lists

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 wether 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")

Sequences

lists and vectors (and thus strings) are sequences.

Note: see also the strings page.

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)))

Note: and cl21 has short lambdas:

(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 ^(= 3 (length %)) str) ;; in CL21
;; => T

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

mismatch (sequence-a, sequence-b): Return position in sequence-a where sequence-a and sequence-b begin to mismatch. Return NIL if they match entirely. Other parameters: :from-end bool, :start1, :start2 and their :end[1,2].

Functions

See also sequence functions defined in Alexandria: starts-with, ends-with, ends-with-subseq, length=, emptyp,…

length (sequence)

member (elt, sequence)

elt (sequence, 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])

It 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])

find, position (foo, sequence)

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

search (sequence-a, sequence-b)

Search sequence-b for a subsequence matching sequence-a. Return position in sequence-b, or NIL. Has the from-end, end1/2 and others parameters.

substitute, nsubstitute[if,if-not]

sort, stable-sort, merge

replace (sequence-a, sequence-b)

Replace elements of sequence-a with elements of sequence-b.

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.

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.

Note: cl21’s map is a generic mapcar for lists and vectors.

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

intersection

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)

set-difference

Remove the elements of list-b from list-a:

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

union

join the two lists:

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

set-exclusive-or

Remove the elements that are in both lists:

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

and their recycling “n” counterpart (nintersection,…).

See also functions in Alexandria: setp, set-equal,…

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 setfable.

(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 *i*th 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). setfable.

and see also the sequence functions.

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.

If we are using the cl21 extension library, we can create a hash table and add elements in the same time with the new #H reader syntax:

(defparameter *my-hash* #H(:name "Eitaro Fukamachi"))

then we access an element with

(getf *my-hash* :name)

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)

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

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

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

Last, we also have cl21’s (doeach ((key val) *hash*) …).

Traversign 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

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

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

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

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

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. There is assoc-if, and rassoc to get a cons cell by its value.

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

In the Alexandria library, see some functions like remove-from-plist, 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!!!"

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.

See more in other resources !