Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 38 ยท Lists and Data Structures

Association Lists and Property Lists

Store key-value data in plain Lisp lists with association lists and property lists: assoc, acons, getf, setf getf, remf, and when to switch to hash tables.

Before you reach for a hash table, Lisp offers two lightweight ways to store key-value pairs using nothing but lists: the association list (alist) and the property list (plist). They are perfect for small collections, configuration, options, and anything you want to print and read back. This lesson shows both, their pitfalls, and how to choose.

Association lists (alists)

An alist is a list of dotted pairs (key . value):

LISP
(defparameter *ages*
  '((alice . 30)
    (bob   . 25)
    (carol . 41)))

Looking things up

assoc finds the first pair whose key matches (using eql by default) and returns the whole pair:

LISP
(assoc 'bob *ages*)          ; => (BOB . 25)
(cdr (assoc 'bob *ages*))    ; => 25
(assoc 'zed *ages*)          ; => NIL
(cdr (assoc 'zed *ages*))    ; => NIL     (cdr of NIL is NIL: safe)
(rassoc 41 *ages*)           ; => (CAROL . 41)   look up by VALUE

Returning the pair (not just the value) lets you tell "key missing" (NIL) from "key present with value NIL" ((KEY)).

String keys need a different test, because eql does not match two equal strings:

LISP
(defparameter *capitals* '(("France" . "Paris") ("Peru" . "Lima")))
(assoc "Peru" *capitals*)                    ; => NIL  (eql fails!)
(assoc "Peru" *capitals* :test #'string=)    ; => ("Peru" . "Lima")
(assoc "Peru" *capitals* :test #'equal)      ; => ("Peru" . "Lima")

Adding, updating, removing

The classic way to add is to push a new pair on the front. The new pair shadows any older pair with the same key, and the old one stays behind it:

LISP
(push (cons 'dave 19) *ages*)
(acons 'erin 33 *ages*)             ; => new list with (ERIN . 33) in front; *ages* unchanged
(setf *ages* (acons 'erin 33 *ages*))   ; keep it

To update an existing entry in place, change the cdr of the pair you found:

LISP
(let ((pair (assoc 'bob *ages*)))
  (when pair
    (setf (cdr pair) 26)))

Never do this to a quoted literal (it is a constant). Build the alist with list/cons/acons, or copy it with copy-alist.

To remove an entry:

LISP
(remove 'bob *ages* :key #'car)   ; => alist without bob

pairlis and other helpers

LISP
(pairlis '(a b c) '(1 2 3))       ; => ((C . 3) (B . 2) (A . 1)) order unspecified
(copy-alist *ages*)               ; copies the pairs too, so setf cdr is safe
(mapcar #'car *ages*)             ; => all keys
(mapcar #'cdr *ages*)             ; => all values

Notice the shadowing property: because assoc returns the first match, pushing a new pair is an O(1) update that can be undone by popping it. This is useful for "environments" in interpreters.

Property lists (plists)

A plist is a flat list that alternates keys and values. Keys are usually keywords:

LISP
(defparameter *config* (list :host "localhost" :port 8080 :debug t))

(getf *config* :port)            ; => 8080
(getf *config* :missing)         ; => NIL
(getf *config* :missing 0)       ; => 0    third argument is a default

getf uses eq to compare keys, so use symbols or keywords as keys (never strings or large numbers). You can also store defaults, and plists print beautifully:

LISP
(setf (getf *config* :port) 9090)   ; update in place
(setf (getf *config* :tls) t)       ; add a new key
(remf *config* :debug)              ; remove a key, returns T if it existed

setf getf works only on a place (a variable or other settable form), not on a quoted literal. Create the plist with list when you plan to modify it:

LISP
(defparameter *opts* (list :a 1 :b 2))   ; modifiable

Plists as keyword arguments

The same shape powers &key arguments. You can pass a plist straight to a function with apply:

LISP
(defun make-point (&key (x 0) (y 0)) (list x y))
(apply #'make-point '(:x 3 :y 4))   ; => (3 4)

Functions such as getf and destructuring-bind make it easy to process options:

LISP
(destructuring-bind (&key host port &allow-other-keys) *config*
  (format nil "~a:~a" host port))     ; => "localhost:9090"

Symbol property lists

Every symbol has its own plist, accessed with get:

LISP
(setf (get 'apple 'colour) 'red)
(get 'apple 'colour)               ; => RED
(symbol-plist 'apple)              ; => (COLOUR RED)

It is an old feature: handy for attaching metadata to symbols, but a hash table or a struct is clearer in new code.

Stand-in: assoc and getf in JavaScript

The functions are tiny. This JavaScript stand-in (not Lisp) implements them on arrays so you can see shadowing, :test, defaults and plist traversal in action.

JS Stand-in: assoc, acons, getf

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

No output.

Choosing between alist, plist and hash table

Alist Plist Hash table
Shape List of pairs Flat key/value list Opaque object
Key comparison :test option (default eql) eq only eq, eql, equal, equalp
Lookup cost O(n) O(n) O(1) average
Prints readably Yes Yes No
Good for Small maps, environments, shadowing Options, config, keyword args Large or hot lookup tables
Ordered Yes (insertion/push order) Yes No guaranteed order

Rules of thumb: under a few dozen entries, either list form is fine and easy to debug. For hundreds or more, use a hash table. For records with fixed fields, a structure or class (later chapters) is clearer.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does (assoc 'b '((a . 1) (b . 2))) return?

    assoc returns the whole pair; use cdr to get the value.
  2. 2. Why does (assoc "x" '(("x" . 1))) return NIL?

    Pass :test #'string= or #'equal to match strings.
  3. 3. Which function reads a value from (:a 1 :b 2)?

    getf reads a key from a property list; assoc reads from an association list.
  4. 4. What happens when you push a pair with an existing key onto an alist?

    assoc finds the first match, which is the newest pair.
  5. 5. When is a hash table a better choice than an alist?

    Hash tables give average O(1) lookup instead of O(n).

Summary

  • An alist is a list of (key . value) pairs; assoc returns the first matching pair, acons/push adds in front, :test handles non-eql keys.
  • A plist alternates keys and values; getf, (setf getf) and remf read, write and delete; keys compare with eq.
  • Do not modify quoted literals; build them with list or copy-alist.
  • Lists are great for small maps and options; hash tables win when data grows.

Next: Vectors and Sequences