The Pitmanual: List Structure


Cons	Concept	`A Pair`

A cons is a primitive data structure capable of holding exactly two things. There are two parts to a cons: the car (left half) and the cdr (right half). Conses are also referred to as dotted pairs because the input notation “(x . y)” describes a cons. The function CONS constructs conses, and the functions CAR and CDR access the two objects stored in the cons.

Example:

(cons 'a 'b)	=> (a . b)


List	Concept	`Abstract Datastructure`

The most common use of a cons in Lisp is to create a structure called a list. The symbol NIL is defined to denote the empty list. All other lists are conses whose car is any object and whose cdr is a list. The car is sometimes called the “head” or “first” of the list. The cdr is sometimes called the “tail” or “rest” of the list. For convenience, Lisp employs a shorthand notation for lists: Any dotted pair whose cdr is a list will display without the dot and without the parens around the cdr. So

The form... Is displayed by PRINT as...
(A . (B C D)) (A B C D)
(A . (B C)) (A B C)
(A . (B)) (A B)
(A . NIL) (A)

The last example makes sense if you remember NIL can also be written as (). So the list

((X Y Z) W (L M . N) Q)

Is really the same as

((X . (Y . (Z . NIL))) . (W . ((L . (M . N)) . (Q . NIL))))

Both denote a list whose car is the list (X Y Z) and whose cdr is the list (W (L M . N) Q). Each of those things is in turn a list. This datastructure lends itself nicely to recursive descriptions of algorithms.

Lists like (L M . N) which have no trailing NIL are sometimes called “dotted lists.” They are not what is called a “proper list.” Like all conses, however, they are of type LIST and the LISTP predicate will return true for them.

Conses


`CONS`	Function	`(CONS q₁ q₂)`

This is a primitive function to construct a new dotted pair whose car is the first argument to CONS, and whose cdr is the second argument to CONS.

(cons 'a 'b)
=> (A . B)

(setq x (cons 'a (cons 'b (cons 'c '()))))
=> (A B C)

(cons x nil)
=> ((A B C))	

(setq y (cons 'a '(b c d e f)))
=> (A B C D E F)

(setq z (cons x y))
=> ((A B C) A B C D E F)

(eq (car z) x)
=> T

(eq (cdr z) y)
=> T


`NCONS`	Function	`(NCONS q)`

Functionally equivalent to (LIST q) or (CONS q NIL), but prefered by some in certain circumstances for stylistic reasons.

Example:

(NCONS 'A)	=>	(A)


`XCONS`	Function	`(XCONS q₁ q₂)`

XCONS (“Exchange CONS”) is like CONS except that the order of its arguments is reversed.

Definition:

(DEFUN XCONS (X Y) (CONS Y X))

Example:

(XCONS 'A 'B)	=>	(B . A)


`CAR`	Function	`(CAR l)`

Returns the left half of a CONS. For hunks, returns the cxr-1 (not defined on one-length hunks). CAR of an atomic symbol (see documentation of the variable CAR) is not defined. The car of NIL is guaranteed to be NIL.

Examples:

(CAR NIL)		=>	NIL

(CAR '(A B))		=>	A

(CAR '(1 . 2))		=>	1

(CAR '((A B) (C D)))	=>	(A B)

(CAR '(A . B . C .))	=>	A	;A hunk example


`CDR`	Function	`(CDR l)`

Returns the right half of a CONS. For hunks, returns the cxr-0. The CDR of an atomic symbol (see documentation of the variable CDR) is its property list; the PLIST function should be used to access this pointer in “modern” code. The cdr of NIL is guaranteed to be NIL.

Examples:

(CDR NIL)		=>	NIL

(CDR '(A B))		=>	(B)

(CDR '(1 . 2))		=>	2

(CDR '((A B) (C D)))	=>	((C D))

(CDR '(A . B . C .))	=>	C	;A hunk example


`C...R`	Function	`(C...R l)`

Short names for CAR/CDR compositions are provided in Maclisp up to four levels. e.g., (CAAR l) is like (CAR (CAR l)) and (CADAAR l) is like (CAR (CDR (CAR (CAR l)))). If any of these functions receive an argument of NIL or prematurely encounter NIL while CAR/CDRing through their argument, they are still guaranteed to return NIL.

Examples:

(CAR    '(LAMBDA (X) (+ X 5)))	=> LAMBDA	;Header

(CADR   '(LAMBDA (X) (+ X 5)))	=> (X)		;BVL

(CDDR   '(LAMBDA (X) (+ X 5)))	=> ((+ X 5))	;Body

(CDDDR  '(LAMBDA (X) (+ X 5)))	=> NIL

(CDDDDR '(LAMBDA (X) (+ X 5)))	=> NIL

(CADR (CDDDDR '(A B C D E F)))	=> F ;There isn't a CADDDDDR function

Lists


`LIST`	Function	`(LIST q₁ q₂ q₃ ...)`

LIST constructs and returns a list of the values of its arguments.

Example:

(LIST 3 4 'A (CAR '(B . C)) (+ 6 -2))	=>	(3 4 A B 4)


*`LIST`**	Function	`(LIST* q₁ q₂ q₃ ...)`

An LSUBR generalization of CONS -- same as (CONS q₁ (CONS q₂ (CONS q₃ ...))).

Examples:

(LIST* 'A)		=>	A

(LIST* 'A 'B)		=>	(A . B)

(LIST* 'A 'B 'C)	=>	(A B . C)

(LIST* 'A 'B 'C NIL)	=>	(A B C)


`MAKE-LIST`	Function	`(MAKE-LIST i)`

Makes a list i long, filled with NIL's.

Multics users must (%include runtime) to get MAKE-LIST.

Examples:

(MAKE-LIST 0)	=> NIL

(MAKE-LIST 5)	=> (NIL NIL NIL NIL NIL)


`LENGTH`	Function	`(LENGTH l)`

Returns the length of its argument list, l. The length of a list is the number of top-level conses in it. The warning about dotted lists given under LAST applies also to LENGTH.

Examples:

(LENGTH NIL) => 0

(LENGTH '(A B C D)) => 4

(LENGTH '(A (B C) D)) => 3

Definition:

(DEFUN LENGTH (X)
       (COND ((NULL X) 0)
             (T (1+ (LENGTH (CDR X))))))

Predicates


`NULL`	Function	`(NULL q)`

Returns T if q is NIL, else NIL.

Same function as NOT. For clarity, use NULL when expecting q to be a list. Use NOT when q may be arbitrary. The difference is purely semantic, but semantic differences are important if you are to understand your code. It makes perfect sense to say something like (NOT (NULL x)) instead of simply x in a predicate position; this provides visual information to the reader that x is a list which might be null and is no less inefficient, since they compile to exactly the same code.


`LISTP`	Function	`(LISTP q)`

Different implementations do different things with this.

In PDP-10 Maclisp, (LISTP q) is the same as:

(OR (NULL q) (EQ (TYPEP q) 'LIST))

This behavior is, incidentally, compatible with Common Lisp.

In Multics Maclisp, (LISTP q) is the same as:

(NOT (ATOM q))

This behavior is compatible with Lisp Machine Lisp.

PDP-10 and Multics Maclisp are not compatible, however, since (LISTP NIL) returns NIL on Multics and T on the PDP-10.

The author recommends simply avoiding this function.


`PAIRP`	Function	`(PAIRP q)`

[PDP-10 Only] Returns true if its argument, q, is of type LIST and NIL otherwise. This is not the same as (NOT (ATOM q)) because of its behavior with respect to hunks.

Examples:

(PAIRP NIL)		=> NIL	; NIL isn't a pair

(PAIRP 'X)		=> NIL	; in fact, no atoms are pairs

(PAIRP '(A . B . C .))	=> NIL	; hunks aren't pairs either

(PAIRP '(A . B))	=> T	; dotted pairs are pairs

(PAIRP '(A B C))	=> T	; non-empty lists are pairs

List Element Selectors


`LAST`	Function	`(LAST l)`

Returns the last dotted pair of its argument list, l, which must be NIL or a well-formed list. To get the last element, use (CAR (LAST l)). The behavior of LAST on lists which aren't well-formed, such as (A B . C), is not defined by the language and should not be relied upon, especially across implementations.

Examples:

(last '(a b c d))	=> (D)

(last '())		=> NIL


`NTH`	Function	`(NTH i l)`

Returns the ith element of the list, l, where i=0 denotes the first element. i must be a positive fixnum. If NTH falls off the end of l, NIL is returned.

Examples:

(NTH 3 '(A B C D))	=> D

(NTH 3 '(SHORT LIST))	=> NIL

Definition:

(DEFUN NTH (I L) (CAR (NTHCDR I L)))


`NTHCDR`	Function	`(NTHCDR i l)`

Returns the ith tail of the list, l, where i=0 means return the whole list. If NTHCDR `falls off the end' of l, NIL is returned.

Examples:

(NTHCDR 3 '(A B C D E))		=> (D E)

(NTHCDR 3 '(SHORT LIST))	=> NIL

Definition:

(DEFUN NTHCDR (I L)
  (COND ((OR (NOT (FIXP I)) (BIGP I) (MINUSP I))
         (ERROR "ILLEGAL ELEMENT NUMBER - NTH//NTHCDR" I
                'WRNG-TYPE-ARG))
        ((ZEROP I) L)
        (T (NTHCDR (1- I) (CDR L)))))

List Utilities


`APPEND`	Function	`(APPEND l₁ l₂ l₃ ...)`

The arguments to append are lists. The result is a list which is the concatenation of the arguments. To avoid modifying the arguments, copies are made of all but the last.

See also: NREVERSE, NRECONC

Example:

(REVERSE '(A (B C) D))	=> (D (B C) A)

Association Lists


`ASSOC`	Function	`(ASSOC object alist)`

Looks up object in alist (an association list---list of dotted pairs). The value is the first dotted pair whose car is EQUAL to object, or NIL if there is none such.

Definition:

(DEFUN ASSOC (X Y)
       (COND ((NULL Y) NIL)
             ((EQUAL X (CAAR Y)) (CAR Y))
             (T (ASSOC X (CDR Y)))))


`ASSQ`	Function	`(ASSQ object alist)`

ASSQ is like ASSOC except that the comparison uses EQ instead of EQUAL.

Definition:

(DEFUN ASSQ (X Y)
       (COND ((NULL Y) NIL)
             ((EQ X (CAAR Y)) (CAR Y))
             (T (ASSQ X (CDR Y)))))


`SASSOC`	Function	`(SASSOC object l f)`

Like (ASSOC object l) except if object is not found in l, the function f is called with no arguments and its return value is returned by SASSOC instead of the NIL which ASSOC would return.

The reason that f does not receive an argument of the missing object is for compatibility with the Lisp 1.5 dialect. As a result, this function is almost never used. Most people prefer to write simply:

(OR (ASSOC object l) (FUNCALL f object))

Definition:

(DEFUN SASSOC (OBJECT L F) (OR (ASSOC OBJECT L) (FUNCALL F)))


`SASSQ`	Function	`(SASSQ object l f)`

Like SASSOC, but uses ASSQ instead of ASSOC.

Definition:

(DEFUN SASSQ (OBJECT L F) (OR (ASSQ OBJECT L) (FUNCALL F)))

;; ASSQ is usually used for entries keyed by symbols.
(setq x (assq 'r (setq db '((a . b) (c d e) (r . x) (s . y) (r . z)))))
=> (R . X)

(assq 'c db)
=> (C D E)	; i.e., (C . (D E))

(setf (cdr x) 'new)
=> NEW

(assq 'r db)
=> (R . NEW)

(setf (car x) 'foo)
=> FOO	

(assq 'r db)
=> (R . Z)

(assq 'k db)
=> NIL

;; ASSOC is usually used for entries keyed by non-symbols
(assoc 3127. '((103. . (abc)) (2125. . foo) (3127. . something)))
=> (3127. . SOMETHING)

(assoc '(a b) '((a b c) ((a b c) b) ((a b) d)))
=> ((A B) D)

Deletion Operators


`DELETE`	Function	`(DELETE q l [i])`

If no i is specified, returns the list l with all top-level occurrences of q removed. EQUAL is used for the comparison. The argument l is actually modified (RPLACD'ed) when instances of q are spliced out. If i is given, only the first i instances of q are deleted. If i is zero, no occurrences will be deleted; if i is greater than (or, of course, equal to) the number of occurrences of q in l, all occurrences of q in l will be deleted.

Warning: Users are cautioned not to rely on the side-effect of this result unless they understand how it can differ from the return value. The return value is guaranteed to have all requested elements removed, but the side-effect on the second argument may not have been this severe; leading element(s) which are EQUAL to the element being deleted will not have been actually spliced out of the second argument.

Definition:

(DEFUN DELETE (Q L &OPTIONAL (N -1. N?))
       (COND ((NOT N?) (*DELETE Q L)) ;defined elsewhere in this manual
             ((FIXP N)
              (COND ((BIGP N)
                     (ERROR '|UNACCEPTABLE NUMERIC VALUE| N 'WRNG-TYPE-ARG))
                   ((OR (NULL L) (< N 1)) L)
                   ((EQUAL Q (CAR L))
                    (DELETE Q (CDR L) (1- N)))
                   (T (RPLACD L (DELETE Q (CDR L) N)))))
             (T (ERROR '|NON-NUMERIC VALUE| N 'WRNG-TYPE-ARG))))


`DELQ`	Function	`(DELQ q l [i])`

Same as DELETE except that EQ is used for the comparison instead of EQUAL.

(setq x '(a a b a c (a b) d a e))
=> (A A B A C (A B) D A E)

(setq y (delq 'a x))
=> (B C (A B) D E)

;; It is possible that the input to DELETE or DELQ may be modified but that all occurrences
;; will not be removed. In particular, leading elements will not have been removed.
x
(A A B C (A B) D E)

;; Only the return value is guaranteed to have been correct.
y
(B C (A B) D E)

MapLIST Operators


`MAP`	Function	`(MAP f l₁ l₂ ...)`

The first argument to map is a function, and the remaining arguments are lists. Map “cdrs down” the lists, applying the function to successive cdrs of the lists each time. The first value tried is the whole list and the value returned by map is its second argument. Map stops as soon as one of the lists is exhausted.

;; Simple example
(map #'print '(a b c))
(A B C)
(B C)
(C)
=> (A B C)

There are more examples on the next page.


`MAPLIST`	Function	`(MAPLIST f l₁ l₂ ...)`

Like MAP except that the return value is a list of the results of each application of the function.

Example:

(MAPLIST #'LENGTH '(A B C D)) => (4 3 2 1)


`MAPCON`	Function	`(MAPCON f l₁ l₂ ...)`

Like MAPLIST except that the values returned by the function are NCONC'ed together instead of being listed together. This can have disastrous effects on the arguments to MAPCON if one is not careful.

Note: The NCONC happens as the mapping process goes, not afterward; it is, therefore, not the same as NCONCing the results of a MAPLIST.

;; A complex example -- Bubble Sort
;; This example courtesy of Richard Bryan
(defun sort-a-list (ll predicate)
  (map #'(lambda (l)
           (map #'(lambda (m)
                    (if (not (funcall predicate (car l) (car m)))
                        (rplaca l (prog1 (car m) (rplaca m (car l))))))
                l))
       ll)
  ll)
=> SORT-A-LIST

(setq test-list '(this is a test))
=> (THIS IS A TEST)

(sort-a-list test-list #'alphalessp)
=> (A IS TEST THIS)

test-list
=> (A IS TEST THIS)

;; Another example -- comparing the results of the same function
;;  through each of several mappers.
(defun f (x) (list (length x) x))
=> F

(mapcar #'f '((a b c) (d e f) (g h i)))
=> ((3 (A B C)) (3 (D E F)) (3 (G H I)))

(maplist #'f '((a b c) (d e f) (g h i)))
=> ((3 ((A B C) (D E F) (G H I))) (2 ((D E F) (G H I))) (1 ((G H I))))

(mapcon #'f '((a b c) (d e f) (g h i)))
=> (3 ((A B C) (D E F) (G H I)) 2 ((D E F) (G H I)) 1 ((G H I)))

MapCAR Operators


`MAPC`	Function	`(MAPC f l₁ l₂ ...)`

Just like MAP except that the function is applied to successive elements of the lists rather than to the lists themselves. For use in place of MAPCAR when result won't be needed. MAPC returns l₁, but it is poor form to rely on that from code.

(mapc #'(lambda (x) (putprop x t 'color)) '(red blue green yellow))
=> (RED BLUE GREEN YELLOW)

(get 'red 'color)
=> T

(mapc #'(lambda (x y) (putprop x y 'magnitude))
      '(one two three)
      '(1 2 3))
=> (ONE TWO THREE)

(get 'two 'magnitude)
=> TWO


`MAPCAR`	Function	`(MAPCAR f l₁ l₂ ...)`

Mapcar is like mapc except that the return value is a list of the results of each application of the function.

Examples:

(MAPCAR #'1+ '(3 43 51))		=> (4 44 52)

(MAPCAR #'LIST '(A B C) '(D E F))	=> ((A D) (B E) (C F))


`MAPCAN`	Function	`(MAPCAN f l₁ l₂ ...)`

MAPCAN is like MAPCAR except that the values returned by the function are NCONC'ed together instead of being listed together. This is sometimes used to implement list filtering.

Note: Like MAPCON, MAPCAN does NCONCing as it goes, not afterward.

Example:

(MAPCAN #'(LAMBDA (X) (IF (FIXP X) (NCONS X))) '(A 3 B 4 2))
=> (3 4 2)

;; An example of MAPC
(defun print-elements (a-list)
  (mapc #'print a-list)
  'done)
=> PRINT-ELEMENTS

(print-elements '((a b c) d (4 . 5)))
(A B C)
D
(4 . 5)
=> DONE

;; A sophisticated MAPCAR example -- Matrix Transpose
(DEFUN TRANSPOSE (M) ;This example courtesy of Vaughan Pratt
  (LEXPR-FUNCALL #'MAPCAR #'LIST M))
=> TRANSPOSE

(TRANSPOSE '((A B C) (D E F) (G H I)))
=> ((A D G) (B E H) (C F I))

(TRANPOSE '((A B C) (D E F)))
=> ((A D) (B E) (C F))

;; An example of MAPCAN as a filter

(defun filter (predicate list)
  (mapcan #'(lambda (x) (if (funcall predicate x) (ncons x))) list))
=> FILTER

(filter #'plusp '(1 3 -3 4 5 0 2))
=> (1 3 4 5 2)

(filter #'symbolp '(1 a 3 () 4.0 (a list)))
=> (A NIL)

List Membership Operators


`MEMBER`	Function	`(MEMBER object l)`

Returns NIL if object is not a member of the list, l. Otherwise, it returns the portion of l beginning with the first occurrence of object. The comparison is made by EQUAL. l is searched on the top level only. Note that the value returned by MEMBER is EQ to the portion of the list beginning with x. Thus RPLACA on the result of MEMBER may be used, if the a check is made to ensure that MEMBER did not return NIL.

Definition:

(DEFUN MEMBER (X Y)
       (COND ((NULL Y) NIL)
             ((EQUAL X (CAR Y)) Y)
             ((MEMBER X (CDR Y)))))


`MEMQ`	Function	`(MEMQ object l)`

Like member, except EQ is used for the comparison.

Definition:

(DEFUN MEMQ (X Y)
       (COND ((NULL Y) NIL)
             ((EQ X (CAR Y)) Y)
             ((MEMQ X (CDR Y)))))

;; MEMQ is generally used when the thing sought is a symbol
(memq 'x '(1 2 3 4))
=> NIL

(memq 'x '(a (x y) c x d e x f))
=> (X D E X F)

;; MEMBER is used when the thing sought is not a symbol.
(member 1234 '(1 12 123 1234 12345))
=> (1234 12345)

(member '(a b) '(a b (a b) c d))
=> ((A B) C D)

Destructive List Utilities


`NCONC`	Function	`(NCONC l₁ l₂ l₃ ...)`

Takes lists as arguments. It returns a list which is the arguments concatenated together. The arguments are modified, rather than copied (as APPEND would do). This entails bashing the tails of all non-null arguments, other than the last.

Definition:

(DEFUN NCONC (&OPTIONAL (L1 NIL) (L2 NIL L2?) &REST MORE)
  (COND ((NOT L2?) L1)
        ((NULL MORE) (*NCONC L1 L2)) ;defined elsewhere in this manual
        (T (*NCONC L1 (LEXPR-FUNCALL #'NCONC L2 MORE)))))

`((new list) new list)`	in Maclisp on the PDP-10
`((a b) a b)`	in Maclisp on Multics
`((new list) a b)`	in Lisp Machine Lisp

`NIL`	This operation defined only on lists, hunks, or `NIL`.
`LIST`	This operation defined only on lists or hunks.
`SYMBOL`	This operation defined only on lists, symbols, hunks, or `NIL`.
`T`	This operation `defined' on any datatype.

The form...	Is displayed by `PRINT` as...
`(A . (B C D))`	`(A B C D)`
`(A . (B C))`	`(A B C)`
`(A . (B))`	`(A B)`
`(A . NIL)`	`(A)`


`REVERSE`	Function	`(REVERSE l)`