List Operations

Basing both data structures and code on lists as it does, Scheme naturally enough has a set of primitives for creating and manipulating lists.

List Constructors

List constructors are special forms which create lists out of atoms and smaller lists, The (list) form has already been mentioned; it accepts two or more atoms or lists and returns a proper list based on them: 

   > (list 'a 'b '(c d (e f) g) 'h)
   (a b (c d (e f) g) h)

Calls can be nested; the previous call could have been written 

   > (list 'a 'b (list 'c 'd (list 'e 'f) 'g) 'h)
   (a b (c d (e f) g) h)

A more basic function, (cons), takes exactly two arguments, and returns a cons cell with the first arg as it's CAR and the second as it's CDR. 

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

   > (cons 'a (cons (cons 'b (cons 'c '())) (cons 'd '())))
   (a (b c) d)

There is also (append), which takes a list as the first argument and appends the second argument to it; 

   > (append '(a (bc)) 'd)
   (a (bc) . d)

   > (append '(a (b c)) '(d))
   (a (b c) d)

List Decomposition

The CAR or CDR of a cons cell can be extracted using two other functions, predictably called (car) and (cdr). 

   > (car '(a (bc) d))
   a

   > (cdr '(a (bc) d))
   ((bc) d)

While many alternative names have been proposed for these two functions (head/tail, top/bottom, first/rest), these otherwise troublesome names have been retained because of one advantage: they can be composed easily into more complex functions: 

   > (car (cdr '(a (b c) d)))
   (b c)

can be composed into 

   > (cadr '(a (b c) d))
   (b c)

The Scheme standard mandates that these composed functions can up to a depth of at least 4 compositions (e.g., caadr, cdadr), and many interpeters allow an indefinite number of them.

List Manipulation

There are a variety of additional functions that compare lists and extract sublists. These include (list-ref), which returns the n member (zero-indexed) of a list: 

   > (list-ref '(a (b c) d) 0)
   a
   > (list-ref '(a (b c) d) 1)
   (b c)
   > (list-ref '(a (b c) d) 2)
   d

(list-tail), which returns the sub-list starting at (zero-index) member n 

   > (list-tail '(a (b c) d) 1) 
   ((b c) d)

Note that (list-ref a-list n) is equivalent to (car (list-tail a-list n)).

(length), which returns the length of a list; 

   > (length '(a (b c) d))
   3

(reverse), which returns a list in reverse order of the original: 

   > (reverse '(a (b c) d))
   (d (b c) a)

... and (member), which finds the first instance of a given element and returns the sublist that it is the CAR of (or false if it is not found): 

   >(member 'e '(a b c d e f g))
   (e f g)
   > (member '(b c) '(a (b c) d))
   ((b c) d)

   > (member 'b '(a (b c) d))
   #f

Contents Previous Next