List Data Structures

June 8, 2008 | Filed Under Common Lisp - Touretzky 

———————————————————
Chapter 6
———————————————————

(APPEND ‘(1 2 3) ‘(4 5 6)) -> (1 2 3 4 5 6)
(APPEND NIL ‘(1 2 3)) -> (1 2 3)
(APPEND ‘(1 2 3) NIL) -> (1 2 3)
(APPEND NIL NIL) -> NIL
(APPEND ‘((1 2) (3 4)) ‘((5 6) (7 8))) -> ((1 2) (3 4) (5 6) (7 8))

APPEND is non-destructive - it copies the first list and makes the final cons cell point to the second list:

(SETF who ‘(only the good))
(APPEND who ‘(die young)) -> (only the good die young)
who -> (only the good)

(APPEND ‘a ‘(b c)) -> ERROR ; ‘a is not NIL terminated (i.e. APPEND cannot place a pointer here
to the CAR of (b c)
(APPEND ‘(a b) ‘c) -> (a b . c)
(APPEND ‘(a b) ‘(c)) -> (a b c)

Comparing CONS, LIST & APPEND:

(CONS ‘rice ‘(and beans)) -> (rice and beans)
(LIST ‘rice ‘(and beans)) -> (rice (and beans))
(APPEND ‘rice (and beans)) -> ERROR

(CONS ‘(here tdy) ‘(gone tmr)) -> ((here tdy) gone tmr)
(LIST ‘(here tdy) ‘(gone tmr)) -> ((here tdy) (gone tmr))
(APPEND ‘(here tdy) ‘(gone tmr)) -> (here tdy gone tmr)

(CONS ‘(eat at) ‘joes) -> ((eat at) . joes)
(LIST ‘(eat at) ‘joes) -> ((eat at) joes)
(APPEND ‘(eat at) ‘joes) -> (eat at . joes)

CONS adds a pointer to the end of the first CONS cell which points to the CAR of the second param.
LIST simply makes a new list using the params given.
APPEND removes the final NIL from each param list and CONses the result.

(REVERSE ‘(1 2 3 4)) -> (4 3 2 1)
(REVERSE ‘(1 2) ‘(3 4)) -> ((3 4) (1 2))

(NTHCDR 0 ‘(1 2 3)) -> (1 2 3)
(NTHCDR 2 ‘(1 2 3)) -> (3)
(NTHCDR 3 ‘(1 2 3)) -> NIL
(NTHCDR 8 ‘(1 2 3)) -> NIL

(DEFUN NTH (x y)
“returns zero-based nth CAR”
(CAR (NTHCDR x y))) ;returns atom??

(LAST ‘(a b c)) -> (c)
(LAST NIL) -> NIL
(LAST ‘(a b c . d)) -> (c . d) ;returns last CONS cell, not the last ATOM

(REMOVE ‘a ‘(b a n a n a)) ->(b n n)
REMOVE is non-destructive:
(SETF my-banana ‘(b a n a n a))
(REMOVE ‘a my-banana) -> (b n n)
my-banana -> (b a n a n a)

Lists as sets:

MEMBER returns the subset of the list following a match, or NIL for none:

(MEMBER ‘b ‘(a b c)) -> (b c)

INTERSECTION returns the overlap of two lists:
(INTERSECTION ‘(a b c) ‘(a d e)) -> (a)
It is the overlap with the first list that is counted:
(INTERSECTION ‘(a a b c) ‘(a b d)) -> (a a b)
(INTERSECTION ‘(a b c) ‘(a a b d)) -> (a b)

UNION returns the union of the two sets, with each item represented once:
(UNION ‘(a b c d) ‘(f g h b)) -> (a b c d f g h)

SET-DIFFERENCE returns what’s left of the first set when the second set has been subtracted:
(SET-DIFFERENCE ‘(a b c) ‘(a b d)) -> (c)

SUBSETP returns T if set 1 is a subset of set2:
(SUBSETP ‘(a b) ‘(a b c)) -> T

Association lists:
(SETF tbl
‘( (one un)
(two deux)
(three trois)))

(ASSOC ‘three tbl) -> (three trois)

(SETF tbl
‘( (one . un)
(two . deux)
(three . trois)))

(RASSOC ‘un tbl) -> (one . un);only works on dotted pairs

(REMOVE-DUPLICATES ‘(a a b b c c)) -> (a b c)

(SET-EXCLUSIVE-OR ‘(a b c) ‘(a d b)) -> (c d)

(SUBST ‘b ‘a ‘(b a n a n a)) -> (b b n b n b)
(SUBST ‘b ‘a ‘((a b) (p a n d a))) -> ((b b) (p b n d b))

SUBLIS does the same as SUBST, but can make many substitutions based on a dotted pairs list:

(SUBLIS ‘((a . b) (c . d)) ‘(a b c d)) -> (b b d d)

EQUAL returns T for two lists whose elements evaluate to the same value:

(SETF x1 ‘(a b c))
(SETF x2 ‘(a b c))
(EQUAL x1 x2) -> T

EQ compares based on actual symbols created:
(EQ x1 x2) -> NIL
(SETF x2 x1)
(EQ x1 x2) -> T

NB. EQ is faster than EQUAL, as it does not need to evaluate.

EQL???

= compares two numbers, irrespective of type:
(= 3 3.0) -> T
(= ‘foo ‘foo) -> ERROR, NOT A NUMBER

EQUALP is case insensitive:
(EQUALP ‘(foo bar) ‘(FOO BAR)) -> T

Keyword Args
(REMOVE ‘a ‘(b a n a n a) :COUNT 2) -> (b n n a)
(REMOVE ‘a ‘(b a n a n a) :COUNT 2 :FROM-END T) -> (b a n n)

(KEYWORDP :COUNT) -> T
(KEYWORDP ‘COUNT) -> NIL

MEMBER tests using EQL - so fine for a list containing symbols and numbers, but not for a list of lists:

(MEMBER ‘a ‘(a b c)) -> (a b c)
(MEMBER ‘(a b) ‘((a b) (c d))) -> NIL

Use the :TEST keyword to change the basis of the test:

(MEMBER ‘(a b) ‘((a b) (c d)) :TEST #’EQUAL)
-> ((a b) (c d))

also works with UNION,INTERSECTION, SET-DIFFERENCE, ASSOC, RASSOC, SUBST.

Comments