# (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, ```scheme (a b c d e) ``` and ```scheme (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: ```scheme (a b c . d) ``` is equivalent to ```scheme (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*****)** \ \&#xNAN;**(cadr *****xs*****)**\ \&#xNAN;**(cdar *****xs*****)**\ \&#xNAN;**(cddr *****xs*****)** These procedures are compositions of `car` and `cdr` as follows: ```scheme (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*****)** \ \&#xNAN;**(caadr *****xs*****)**\ \&#xNAN;**(cadar *****xs*****)**\ \&#xNAN;**(caddr *****xs*****)**\ \&#xNAN;**(cdaar *****xs*****)**\ \&#xNAN;**(cdadr *****xs*****)**\ \&#xNAN;**(cddar *****xs*****)**\ \&#xNAN;**(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*****)** \ \&#xNAN;**(caaadr *****xs*****)**\ \&#xNAN;**(caadar *****xs*****)**\ \&#xNAN;**(caaddr *****xs*****)**\ \&#xNAN;**(cadaar *****xs*****)**\ \&#xNAN;**(cadadr *****xs*****)**\ \&#xNAN;**(caddar *****xs*****)**\ \&#xNAN;**(cadddr *****xs*****)**\ \&#xNAN;**(cdaaar *****xs*****)**\ \&#xNAN;**(cdaadr *****xs*****)**\ \&#xNAN;**(cdadar *****xs*****)**\ \&#xNAN;**(cdaddr *****xs*****)**\ \&#xNAN;**(cddaar *****xs*****)**\ \&#xNAN;**(cddadr *****xs*****)**\ \&#xNAN;**(cdddar *****xs*****)**\ \&#xNAN;**(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*****)** \ \&#xNAN;**(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 ...*). ```scheme (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. ```scheme (cons* 1 2 3 4) ⇒ (1 2 3 . 4) (cons* 1) ⇒ 1 ``` **(length *****xs*****)** Returns the length of list *xs*. ```scheme (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. ```scheme (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. ```scheme (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*. ```scheme (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*. ```scheme (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*. ```scheme (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. ```scheme (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 ...))`. ```scheme (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. ```scheme (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*: ```scheme (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. ```scheme (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*: ```scheme (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. ```scheme (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*`)`. ```scheme (tabulate 4 fx1+) ⇒ (1 2 3 4) ``` **(iota *****count*****)** \ \&#xNAN;**(iota *****count start*****)**\ \&#xNAN;**(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. ```scheme (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 ```scheme (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*****)** \ \&#xNAN;**(memv *****obj xs*****)**\ \&#xNAN;**(member *****obj xs*****)**\ \&#xNAN;**(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*****)** \ \&#xNAN;**(delv *****obj xs*****)**\ \&#xNAN;**(delete *****obj xs*****)**\ \&#xNAN;**(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*****)** \ \&#xNAN;**(assv *****obj alist*****)**\ \&#xNAN;**(assoc *****obj alist*****)**\ \&#xNAN;**(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. ```scheme (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*****)** \ \&#xNAN;**(alist-delv *****obj alist*****)**\ \&#xNAN;**(alist-delete *****obj alist*****)**\ \&#xNAN;**(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*****)** \ \&#xNAN;**(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*****)** \ \&#xNAN;**(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. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://www.lisppad.app/libraries/lispkit/lispkit-list.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.