Data structures
Here are examples of various data structures available in Lisp.
How to select an appropriate data structure
- Lists are useful for small amounts of data of any kind, and allow
to add and remove items easily. They are often used as a first quick and
dirt approach since they are easy to use, and, if needed, replaced later
with some more efficient data structure.
- Association lists are used to represented pieces of information that
are associated. They can also be used for modeling stacks,
even though for stacks it is better to use directly push and pop.
- Property lists are used when there is only one occurrance of each
indicator.
- Structures are used whenever objects with a number of slots are
convenient. When a structure is defined, Lisp creates automatically
selectors, mutators, and predicates for it. This encourages clean
data abstractions, and is the main reasons why structures should be
used to construct data structures. The aspect of structures that makes
them confusing for beginners, in particular when reading programs writen
by others, is the fact that the selectors, mutators, and predicates are
used without being defined (since they are constructed automatically
without having to define them!)
- Arrays and vectors are used whenever there is an obvious way of indexing
data with an integer. They are very efficient.
- Strings are the most convenient way of dealing with characters.
- Hash-tables are used when data need to be accessed via a symbol
or string but the amount of data is too much for association lists.
;;;; Many of the examples are taken from "A programmer's Guide to
;;;; Common Lisp", by D. Tatar, Digital Press, 1987
;;;; -------------------------------------------------------
;;;; LISTS
;;;; -------------------------------------------------------
;;; constructors cons, list
;;; selectors car, cdr
;;; modifiers setf (car..)/setf (cdr ..)
;; let's define global variables for states for the farmer/wolf/cabbage/goat
;; problem. A state is a list
(defvar *goal* '(west west west west))
(defvar *start* '(east east east east))
;; selectors
(defun farmer (state) (car state))
(defun wolf (state) (cadr state))
(defun goat (state) (caddr state))
(defun cabbage (state) (cadddr state))
;; modifiers
(defun set_farmer (state value) (setf (car state) value) state)
;;;; -------------------------------------------------------
;;;; ASSOCIATION LISTS
;;;; -------------------------------------------------------
>(defvar *employees*
'((john . "62 Walnut St") (rick . "1066 Umbrella St")))
*EMPLOYEES*
;; assoc returns the first pair, using (by default) eql for the equality test.
> (assoc 'rick *employees*)
(RICK . "1066 Umbrella St")
;; acons attaches a new pair to an association list (does not reset its value)
>(acons 'greg "5 Yesterday Lane" *employees*)
((GREG . "5 Yesterday Lane") (JOHN . "62 Walnut St")
(RICK . "1066 Umbrella St"))
;; as we can see here
>*employees*
((JOHN . "62 Walnut St") (RICK . "1066 Umbrella St"))
;; we need to reset it explicitely
>(setf *employees* (acons 'greg "5 Yesterday Lane" *employees*))
((GREG . "5 Yesterday Lane") (JOHN . "62 Walnut St")
(RICK . "1066 Umbrella St"))
;; remove
>(remove (assoc 'john *employees*) *employees*)
((GREG . "5 Yesterday Lane") (RICK . "1066 Umbrella St"))
>(setf *employees* (acons 'rick "666 Abbey St" *employees*))
((RICK . "666 Abbey St") (GREG . "5 Yesterday Lane")
(JOHN . "62 Walnut St") (RICK . "1066 Umbrella St"))
>(assoc 'john *employees*)
(JOHN . "62 Walnut St")
;; reverse assoc takes a value and returns the pair indicator value
>(rassoc "666 Abbey St" *employees* :test #'equalp)
(RICK . "666 Abbey St")
;;;; -------------------------------------------------------
;;;; PROPERTY LISTS
;;;; -------------------------------------------------------
;;; we distinguish between general property lists (which are very like
;;; association lists but operate on a flat list) and property lists
;;; attached to atoms
;;; General property list
>(defvar *phone-list* '(patrick "555-4904" marc "415-555-9989" leigh
"555-0205"))
*PHONE-LIST*
;; getf returns the value associated with marc not the pair (as assoc)
>(getf *phone-list* 'marc)
"415-555-9989"
>(setf (getf *phone-list* 'marc) "555-4483")
"555-4483"
>(remf *phone-list* 'marc)
T
>*phone-list*
(PATRICK "555-4904" LEIGH "555-0205")
;;; Property list for atom
>(setf (get '*my-list* 'marlene) "555-5834")
"555-5834"
>(get '*my-list* 'marlene)
"555-5834"
>(setf (get '*my-list* 'john) "867-8989")
"867-8989"
>(symbol-plist '*my-list*)
(JOHN "867-8989" MARLENE "555-5834")
>(getf (symbol-plist '*my-list*) 'marlene)
"555-5834"
>(remprop '*my-list* 'marlene)
T
>(symbol-plist '*my-list*)
(JOHN "867-8989")
;;;; -----------------------------------------------------
;;;; STRUCTURES
;;;; -----------------------------------------------------
;;; This first example defines a state in the farmer/wolf/goat/cabbage
;;; problem using a structure (instead than using a list)
;;; This defines a structure called state, with 5 slots
;;; Notice the use of the :print-function keyword to print the state
(defstruct (state (:print-function state-print))
;; these are the slots
farmer
wolf
goat
cabbage
;; this is the parent of the state
parent)
STATE
;;; this is the print function to be used when printing a state
;;; print functions for defstruct take 3 args, the structure,
;;; the output stream, the third arg is usually ignored.
>(defun state-print (state stream depth)
(format stream
"farmer is ~A wolf is ~A goat is ~A cabbage is ~A"
(state-farmer state)
(state-wolf state)
(state-goat state)
(state-cabbage state)))
STATE-PRINT
;;; create an instance of it
>(defvar *start*
(make-state :farmer 'east :wolf 'east :goat 'east :cabbage 'east))
*START*
;;; selectors
>(state-farmer *start*)
EAST
;;; type predicate
>(state-p *start*)
T
;;; uses the user defined print function. If no print function is given
;;; it uses default
>*start*
farmer is EAST wolf is EAST goat is EAST cabbage is EAST
;;; to change the value of a slot we use setf
> (setf (state-farmer *start*) 'west)
WEST
>(state-farmer *start*)
WEST
;;; --------------------------------------------------------------
;;; This example is taken from Ansi Common Lisp, Figure 4.5
;;; This shows how to define a structure to represent a binary search
;;; tree, to find an element in it, etc...
;;; this is from Figure 4.5
(defstruct (node (:print-function
(lambda (n s d)
(format s "#<~A>" (node-elt n)))))
elt
(l nil) ; nil is the default value for the slot l
(r nil))
(defun bst-insert (obj bst <)
(if (null bst)
(make-node :elt obj)
(let ((elt (node-elt bst)))
(if (eql obj elt)
bst
(if (funcall < obj elt)
(make-node
:elt elt
:l (bst-insert obj (node-l bst) <)
:r (node-r bst))
(make-node
:elt elt
:r (bst-insert obj (node-r bst) <)
:l (node-l bst)))))))
(defun bst-find (obj bst <)
(if (null bst)
nil
(let ((elt (node-elt bst)))
(if (eql obj elt)
bst
(if (funcall < obj elt)
(bst-find obj (node-l bst) <)
(bst-find obj (node-r bst) <))))))
;;; this is Figure 4.8
(defun bst-traverse (fn bst)
(when bst
(bst-traverse fn (node-l bst))
(funcall fn (node-elt bst))
(bst-traverse fn (node-r bst))))
;;;; -------------------------------------------------------
;;;; ARRAYS AND VECTORS
;;;; -------------------------------------------------------
;;; create a 3 row - 2 column array
>(setf my-array
(make-array '(3 2)
:initial-contents '((a b) (c d) (e f))))
#2A((A B) (C D) (E F))
>(array-dimensions my-array)
(3 2)
;;; access an element (elements are indexed from 0)
>(aref my-array 1 1)
D
;;; modify an element
>(setf (aref my-array 1 1) 'z)
Z
>my-array
#2A((A B) (C Z) (E F))
;;; create a vector and initialize all elements to 0
>(setf my-vect (make-array 5 :initial-element 0)
#(0 0 0 0 0)
;;; access an element (elements are indexed from 0)
(svref my-vect 0)
;; or directly
>(setf my-vect (vector 0 0 0 0 0))
#(0 0 0 0 0)
;;;; -----------------------------------------------------
;;;; STRINGS
;;;; -----------------------------------------------------
;;; a string is a vector of characters (origin at 0)
;;; to access a character use char or schar or aref
>(char "abra" 2)
#\r
>(aref "abra" 2)
#\r
;;; to convert a sequence of characters to a string use format
>(format nil "~a ~a" #\a #\b)
"ab"
>(format nil "~a ~a" #\a 'b)
"a B"
;;; coerce will also work
>(coerce '(#\a #\b) 'string)
"ab"
;;; to concatenate strings use format
>(format nil "~a ~a" "foo" "1")
"foo1"
;;; concatenate will also work
>(concatenate 'string "length" (princ-to-string 1))
"length1"
;;;; -----------------------------------------------------
;;;; HASH TABLES
;;;; -----------------------------------------------------
;;; create a hash-table
>(defvar *phones* (make-hash-table))
*PHONES*
;;; insert something in the hash table
>(setf (gethash 'john *phones*) "555-8798")
"555-8798"
;;; and retrieve it
>(gethash 'john *phones*)
"555-8798"
T