(lispkit list)

Lists are heterogeneous data structures constructed out of pairs and an empty list object.

A pair consists of two fields called car and cdr (for historical reasons). Pairs are created by the procedure cons. The car and cdr fields are accessed by the procedures car and cdr. As opposed to most other Scheme implementations, lists are immutable in LispKit. Thus, it is not possible to set the car and cdr fields of an already existing pair.

Pairs are used primarily to represent lists. A list is defined recursively as either the empty list or a pair whose cdr is a list. More precisely, the set of lists is defined as the smallest set X such that

• The empty list is in X

• If list is in X, then any pair whose cdr field contains list is also in X.

The objects in the car fields of successive pairs of a list are the elements of the list. For example, a two-element list is a pair whose car is the first element and whose cdr is a pair whose car is the second element and whose cdr is the empty list. The length of a list is the number of elements, which is the same as the number of pairs.

The empty list is a special object of its own type. It is not a pair, it has no elements, and its length is zero.

The most general notation (external representation) for Scheme pairs is the "dotted" notation (c1 . c2) where c1 is the value of the car field and c2 is the value of the cdr field. For example (4 . 5) is a pair whose car is 4 and whose cdr is 5. Note that (4 . 5) is the external representation of a pair, not an expression that evaluates to a pair.

A more streamlined notation can be used for lists: the elements of the list are simply enclosed in parentheses and separated by spaces. The empty list is written (). For example,

(a b c d e)

and

(a . (b . (c . (d . (e . ())))))

are equivalent notations for a list of symbols.

A chain of pairs not ending in the empty list is called an improper list. Note that an improper list is not a list. The list and dotted notations can be combined to represent improper lists:

(a b c . d)

is equivalent to

(a . (b . (c . d)))

Basic constructors and procedures

(cons x y)

Returns a pair whose car is x and whose cdr is y.

(car xs)

Returns the contents of the car field of pair xs. Note that it is an error to take the car of the empty list.

(cdr xs)

Returns the contents of the cdr field of pair xs. Note that it is an error to take the cdr of the empty list.

(caar xs) (cadr xs) (cdar xs) (cddr xs)

These procedures are compositions of car and cdr as follows:

(define (caar x) (car (car x)))
(define (cadr x) (car (cdr x)))
(define (cdar x) (cdr (car x)))
(define (cddr x) (cdr (cdr x)))

(caaar xs) (caadr xs) (cadar xs) (caddr xs) (cdaar xs) (cdadr xs) (cddar xs) (cdddr xs)

These eight procedures are further compositions of car and cdr on the same principles. For example, caddr could be defined by (define caddr (lambda (x) (car (cdr (cdr x))))). Arbitrary compositions up to four deep are provided.

(caaaar xs) (caaadr xs) (caadar xs) (caaddr xs) (cadaar xs) (cadadr xs) (caddar xs) (cadddr xs) (cdaaar xs) (cdaadr xs) (cdadar xs) (cdaddr xs) (cddaar xs) (cddadr xs) (cdddar xs) (cddddr xs)

These sixteen procedures are further compositions of car and cdr on the same principles. For example, cadddr could be defined by (define cadddr (lambda (x) (car (cdr (cdr (cdr x)))))). Arbitrary compositions up to four deep are provided.

(make-list k) (make-list k fill)

Returns a list of k elements. If argument fill is given, then each element is set to fill. Otherwise the content of each element is the empty list.

(list x ...)

Returns a list of its arguments, i.e. (x ...).

(list ’a (+ 3 4) ’c)   ⇒  (a 7 c)
(list)                 ⇒  ()

(cons* e1 e2 ...)

Like list, but the last argument provides the tail of the constructed list, returning (cons e1 (cons e2 (cons ... en))). This function is called list* in Common Lisp.

(cons* 1 2 3 4)  ⇒  (1 2 3 . 4)
(cons* 1)        ⇒  1

(length xs)

Returns the length of list xs.

(length ’(a b c))          ⇒  3
(length ’(a (b) (c d e)))  ⇒  3
(length ’())               ⇒  0

Predicates

(pair? obj)

Returns #t if obj is a pair, #f otherwise.

(null? obj)

Returns #t if obj is an empty list, #f otherwise.

(list? obj)

Returns #t if obj is a proper list, #f otherwise. A chain of pairs ending in the empty list is called a proper list.

(every? pred xs ...)

Applies the predicate pred across the lists xs ..., returning #t if the predicate returns #t on every application. If there are n list arguments xs1 ... xsn, then pred must be a procedure taking n arguments and returning a single value, interpreted as a boolean. If an application of pred returns #f, then every? returns #f immediately without applying pred further anymore.

(any? pred xs ...)

Applies the predicate pred across the lists xs ..., returning #t if the predicate returns #t for at least one application. If there are n list arguments xs1 ... xsn, then pred must be a procedure taking n arguments and returning a single value, interpreted as a boolean. If an application of pred returns #t, then any? returns #t immediately without applying pred further anymore.

Composing and transforming lists

(append xs ...)

Returns a list consisting of the elements of the first list xs followed by the elements of the other lists. If there are no arguments, the empty list is returned. If there is exactly one argument, it is returned. The last argument, if there is one, can be of any type. An improper list results if the last argument is not a proper list.

(append ’(x) ’(y))          ⇒  (x y)
(append ’(a) ’(b c d))      ⇒  (a b c d)
(append ’(a (b)) ’((c)))    ⇒  (a (b) (c))
(append ’(a b) ’(c . d))    ⇒  (a b c . d)
(append ’() ’a)             ⇒  a

(concatenate xss)

This procedure appends the elements of the list of lists xss. That is, concatenate returns (apply append xss).

(reverse xs)

Procedure reverse returns a list consisting of the elements of list xs in reverse order.

(reverse '(a b c))              ⇒ (c b a)
(reverse '(a (b c) d (e (f))))  ⇒ ((e (f)) d (b c) a)

(filter pred xs)

Returns all the elements of list xs that satisfy predicate pred. Elements in the result list occur in the same order as they occur in the argument list xs.

(filter even? '(0 7 8 8 43 -4))  ⇒  (0 8 8 -4)

(remove pred xs)

Returns a list without the elements of list xs that satisfy predicate pred: (lambda (pred list) (filter (lambda (x) (not (pred x))) list)). Elements in the result list occur in the same order as they occur in the argument list xs.

(remove even? '(0 7 8 8 43 -4))  ⇒  (7 43)

(partition pred xs)

Partitions the elements of list xs with predicate pred returning two values: the list of in-elements (i.e. elements from xs satisfying pred) and the list of out-elements. Elements occur in the result lists in the same order as they occur in the argument list xs.

(partition symbol? '(one 2 3 four five 6))  ⇒  (one four five)
                                               (2 3 6)

(map f xs ...)

The map procedure applies procedure proc element-wise to the elements of the lists xs ... and returns a list of the results, in order. If more than one list is given and not all lists have the same length, map terminates when the shortest list runs out. The dynamic order in which proc is applied to the elements of the lists is unspecified.

It is an error if proc does not accept as many arguments as there are lists xs ... and return a single value.

(map cadr '((a b) (d e) (g h)))             ⇒  (b e h)

(map (lambda (n) (expt n n)) '(1 2 3 4 5))  ⇒  (1 4 27 256 3125)

(map + '(1 2 3) '(4 5 6 7))                 ⇒  (5 7 9)

(let ((count 0))
  (map (lambda (ignored)
         (set! count (+ count 1)) count)
       '(a b)))                             ⇒  (1 2)

(append-map f xs ...)

Maps f over the elements of the lists xs ..., just as in function map. However, the results of the applications are appended together to determine the final result. append-map uses append to append the results together. The dynamic order in which the various applications of f are made is not specified. At least one of the list arguments xs ... must be finite.

This is equivalent to (apply append (map f xs ...)).

(append-map!
  (lambda (x)
    (list x (- x))) '(1 3 8))
⇒ (1 -1 3 -3 8 -8)

(filter-map f xs ...)

This function works like map, but only values differently from #f are being included in the resulting list. The dynamic order in which the various applications of f are made is not specified. At least one of the list arguments xs ... must be finite.

(filter-map
  (lambda (x)
    (and (number? x) (* x x))) '(a 1 b 3 c 7))
⇒ (1 9 49)

(for-each f xs ...)

The arguments to for-each xs ... are like the arguments to map, but for-each calls proc for its side effects rather than for its values. Unlike map, for-each is guaranteed to call proc on the elements of the lists in order from the first element to the last. If more than one list is given and not all lists have the same length, for-each terminates when the shortest list runs out.

(fold-left f z xs ...)

Fundamental list recursion operator applying f to the elements x1 ... xn of list xs in the following way: (f ... (f (f z x1) x2) ... xn). In other words, this function applies f recursively based on the following rules, assuming one list parameter xs:

(fold-left f z xs)   ⇒  (fold-left f (f z (car xs)) (cdr xs))
(fold-left f z '())  ⇒  z

If n list arguments are provided, then function f must take n + 1 parameters: one element from each list, and the "seed" or fold state, which is initially z as its very first argument. The fold-left operation terminates when the shortest list runs out of values.

(fold-left (lambda (x y) (cons y x)) '() '(1 2 3 4))  ⇒  (4 3 2 1)
(define (xcons+ rest a b) (cons (+ a b) rest))
(fold-left xcons+ '() '(1 2 3 4) '(10 20 30 40 50))   ⇒  (44 33 22 11)

Please note, compared to function fold from library (srfi 1), this function applies the "seed"/fold state always as its first argument to f.

(fold-right f z xs ...)

Fundamental list recursion operator applying f to the elements x1 ... xn of list xs in the following way: (f x1 (f x2 ... (f xn z))). In other words, this function applies f recursively based on the following rules, assuming one list parameter xs:

(fold-right f z xs)               ⇒  (f (car xs) (fold-right f z (cdr xs)))
(fold-right f z '())              ⇒  z
(define (xcons xs x) (cons x xs))
(fold-left xcons '() '(1 2 3 4))  ⇒  (4 3 2 1)

If n list arguments xs ... are provided, then function f must take n + 1 parameters: one element from each list, and the "seed" or fold state, which is initially z. The fold-right operation terminates when the shortest list runs out of values.

(fold-right (lambda (x l) (if (even? x) (cons x l) l))
            '()
            '(1 2 3 4 5 6))  ⇒  (2 4 6)

As opposed to fold-left, procedure fold-right is not tail-recursive.

(sort less xs)

Returns a sorted list containing all elements of xs such that for every element xi at position i, (less xj xi) returns #t for all elements xj at position j where j < i.

(merge less xs ys)

Merges two lists xs and ys which are both sorted with respect to the total ordering predicate less and returns the result as a list.

(tabulate count proc)

Returns a list with count elements. Element i of the list, where 0 ≤ i < count, is produced by (proc i).

(tabulate 4 fx1+)  ⇒  (1 2 3 4)

(iota count) (iota count start) (iota count start step)

Returns a list containing the elements (start start+step ... start+(count-1)*step). The start and step parameters default to 0 and 1.

(iota 5)         ⇒  (0 1 2 3 4)
(iota 5 0 -0.1)  ⇒  (0 -0.1 -0.2 -0.3 -0.4)

Finding and extracting elements

(list-tail xs k)

Returns the sublist of list xs obtained by omitting the first k elements. Procedure list-tail could be defined by

(define (list-tail xs k)
  (if (zero? k) xs (list-tail (cdr xs) (- k 1))))

(list-ref xs k)

Returns the k-th element of list xs. This is the same as the car of (list-tail xs k).

(memq obj xs) (memv obj xs) (member obj xs) (member obj xs compare)

These procedures return the first sublist of xs whose car is obj, where the sublists of xs are the non-empty lists returned by (list-tail xs k) for k less than the length of xs. If obj does not occur in xs, then #f is returned. The memq procedure uses eq? to compare obj with the elements of xs, while memv uses eqv? and member uses compare, if given, and equal? otherwise.

(delq obj xs) (delv obj xs) (delete obj xs) (delete obj xs compare)

Returns a copy of list xs with all entries equal to element obj removed. delq uses eq? to compare obj with the elements in list xs, delv uses eqv?, and delete uses compare if given, and equal? otherwise.

(assq obj alist) (assv obj alist) (assoc obj alist) (assoc obj alist compare)

alist must be an association list, i.e. a list of key/value pairs. This family of procedures finds the first pair in alist whose car field is obj, and returns that pair. If no pair in alist has obj as its car, then #f is returned. The assq procedure uses eq? to compare obj with the car fields of the pairs in alist, while assv uses eqv? and assoc uses compare if given, and equal? otherwise.

(define e '((a 1) (b 2) (c 3)))
(assq 'a e)                             ⇒  (a 1)
(assq 'b e)                             ⇒  (b 2)
(assq 'd e)                             ⇒  #f
(assq (list 'a) '(((a)) ((b)) ((c))))   ⇒  #f
(assoc (list 'a) '(((a)) ((b)) ((c))))  ⇒  ((a))
(assq 5 '((2 3) (5 7) (11 13)))	        ⇒  unspecified
(assv 5 '((2 3) (5 7) (11 13)))	        ⇒  (5 7)

(alist-delq obj alist) (alist-delv obj alist) (alist-delete obj alist) (alist-delete obj alist compare)

Returns a copy of association list alist with all entries removed whose car is equal to element obj. alist-delq uses eq? to compare obj with the first elements of all members of list xs, alist-delv uses eqv?, and alist-delete uses compare if given, and equal? otherwise.

(key xs) (key xs default)

Returns (car xs) if xs is a pair, otherwise default is being returned. If default is not provided as an argument, #f is used instead.

(value xs) (value xs default)

Returns (cdr xs) if xs is a pair, otherwise default is being returned. If default is not provided as an argument, #f is used instead.