Lists

June 8, 2008 | Filed Under Common Lisp - Touretzky 

———————————————————
Chapter 2
———————————————————

Each element of a LIST is a CONS cell, linked to the next one and terminated with NIL

LENGTH returns the number of elements in a LIST
(LENGTH ‘(1 2 3 4)) -> 4
(LENGTH ‘(1 (2 3) 4) -> 3

(FIRST ‘(1 2 3)) -> 1
(SECOND ‘(1 2 3)) -> 2
(THIRD ‘(1 2 3)) -> 3
(REST ‘(1 2 3)) -> (2 3)

(CAR ‘(1 2 3)) -> 1
(CDR ‘(1 2 3)) -> (2 3)
(CDR (1)) -> NIL

(CADR ‘(1 2 3)) ->2
(CDAR ‘((1 2) (3 4)) -> (2)
(CADDR ‘(1 2 3 4)) -> 3

work backwards from the end - CADDR equals a CDR, followed by another CDR followed by a CAR

CAR and CDR of NIL -> NIL
(THIRD ‘(1 2)) -> NIL

(CONS ‘a ‘(b c)) -> (a b c)
****(CONS ‘a NIL) -> (a)
(CONS NIL NIL) -> (NIL)
(CONS ‘(a) ‘(b c)) -> ((a) b c)

x = (CONS (CAR x) (CDR x))

(LIST ‘a ‘b ‘c) -> (a b c)
(LIST ‘a) -> (a)
(LIST ‘(a)) -> ((a))
(LIST ‘a NIL) -> (a NIL)
(LIST ‘a ‘(b c)) -> (a (b c))

(LISTP ‘a) -> NIL
(LISTP ‘(a)) -> T
(LISTP NIL) -> T
(CONSP ‘a) -> NIL
(CONSP ‘(a)) -> T
(CONSP NIL) -> NIL
(ATOM ‘a) -> T
(ATOM ‘(a)) -> NIL
(ATOM NIL) -> T

NULL returns T for a NIL input, and NIL for a non-NIL input. Use to test for NIL, not to change NIL to T - use NOT in this instance.

Properly formed lists end with NIL. Otherwise they are a dotted list (a b c . d).

CONS will return a dotted list if the last input is an atom and not a cons cell (i.e. a list - which terminates in NIL) or NIL itself:

(CONS ‘a ‘b) -> (a . b)
(CONS ‘a (b)) -> (a b)
(CONS ‘a NIL) -> (a)

LIST always returns a properly formatted list with a NIL terminator, even if the inputs are all atoms.

LENGTH returns the number of CONS cells in a list:

(LENGTH ‘(a b c . d)) -> 3

Comments