6.6 Pairs and Lists

Pairs and lists are one of the most fundamental data structure in Scheme. Gauche core provides all standard list procedures, plus some useful procedures that are commonly supported in lots of implementations. If they are not enough, you can find more procedures in the modules described in srfi-1 - List library and util.combinations - Combination library. See also gauche.collection - Collection framework and gauche.sequence - Sequence framework for generic collection/sequence operations.

6.6.1 Pair and null class

Builtin Class: <list>

An abstract class represents lists. A parent class of <null> and <pair>. Inherits <sequence>.

Note that a circular list is also an instance of the <list> class, while R5RS procedure list? returns false on the circular lists and dotted lists.

(use srfi-1) (list? (circular-list 1 2)) ⇒ #f (is-a? (circular-list 1 2) <list>) ⇒ #t

Builtin Class: <null>

A class of empty list. () is the only instance.

Builtin Class: <pair>

A class of pairs.

6.6.2 List predicates

Function: pair? obj

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

Function: null? obj

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

Function: null-list? obj

[SRFI-1] Returns #t if obj is an empty list, #f if obj is a pair. If obj is neither a pair nor an empty list, an error is signaled.

This can be used instead of null? to check the end-of-list condition when you want to be more picky about non-proper lists.

Function: list? obj

[R5RS] Returns #t if obj is a proper list, #f otherwise. This function returns #f if obj is a dotted or circular list.

See also proper-list?, circular-list? and dotted-list? below.

Function: proper-list? x

[SRFI-1] Returns #t if x is a proper list.

Function: circular-list? x

[SRFI-1] Returns #t if x is a circular list.

Function: dotted-list? x

[SRFI-1] Returns #t if x is a finite, non-nil-terminated list. This includes non-pair, non-() values (e.g. symbols, numbers), which are considered to be dotted lists of length 0.

6.6.3 List constructors

Function: cons obj1 obj2

[R5RS] Constructs a pair of obj1 and obj2 and returns it.

(cons 'a 'b) ⇒ (a . b)

Function: make-list len :optional fill

[SRFI-1] Makes a proper list of length len. If optional argument fill is provided, each element is initialized by it. Otherwise each element is undefined.

(make-list 5 #t) ⇒ (#t #t #t #t #t)

Function: list obj …

[R5RS] Makes a list, whose elements are obj ….

(list 1 2 3) ⇒ (1 2 3) (list) ⇒ ()

Function: list* obj1 obj2 …

Function: cons* obj1 obj2 …

[SRFI-1] Like list, but the last argument becomes cdr of the last pair. Two procedures are exactly the same. Gauche originally had list*, and SRFI-1 defines cons*.

(list* 1 2 3) ⇒ (1 2 . 3) (list* 1) ⇒ 1

Function: list-copy list

[SRFI-1] Shallow copies list. If list is circular, this function diverges.

Function: iota count :optional (start 0) (step 1)

[SRFI-1] Returns a list of numbers, starting from start, increasing by step.

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

This creates a list eagerly. If the list is short it is fast enough, but if you want to count tens of thousands of numbers, you may want to do so lazily. See liota (See section Lazy sequences).

Macro: cond-list clause …

Construct a list by conditionally adding entries. Each clause has a test and expressions. When its test yields true, the result of associated expression is used to construct the resulting list. When the test yields false, nothing is inserted.

Clause must be either one of the following form:

(test expr …)

Test is evaluated, and when it is true, expr … are evaluated, and the return value becomes a part of the result. If no expr is given, the result of test is used if it is not false.

(test => proc)

Test is evaluated, and when it is true, proc is called with the value, and the return value is used to construct the result.

(test @ expr …)

Like (test expr …), except that the result of the last expr must be a list, and it is spliced into the resulting list, like unquote-splicing.

(test => @ proc)

Like (test => proc), except that the result of proc must be a list, and and it is spliced into the resulting list, like unquote-splicing.

(let ((alist '((x 3) (y -1) (z 6)))) (cond-list ((assoc 'x alist) 'have-x) ((assoc 'w alist) 'have-w) ((assoc 'z alist) => cadr))) ⇒ (have-x 6) (let ((x 2) (y #f) (z 5)) (cond-list (x @ `(:x ,x)) (y @ `(:y ,y)) (z @ `(:z ,z)))) ⇒ (:x 2 :z 5)

6.6.4 List accessors and modifiers

Function: car pair

Function: cdr pair

[R5RS] Returns car and cdr of pair, respectively.

Function: set-car! pair obj

Function: set-cdr! pair obj

[R5RS] Modifies car and cdr of pair, by obj, respectively.

Note: (setter car) ≡ set-car!, and (setter cdr) ≡ set-cdr!.

Function: caar pair

Function: cadr pair

…

Function: cdddar pair

Function: cddddr pair

[R5RS] caar ≡ (car (car x)), cadr ≡ (car (cdr x)), and so on.

The corresponding setters are also defined.

(let ((x (list 1 2 3 4 5))) (set! (caddr x) -1) x) ⇒ (1 2 -1 4 5)

Function: length list

[R5RS] Returns the length of a proper list list. If list is a dotted list, an error is signalled. If list is a circular list, this function diverges.

Function: length+ x

[SRFI-1] If x is a proper list, returns its length. For all other x, including a circular list, it returns #f.

Function: take x i

Function: drop x i

[SRFI-1] take returns the first i elements of list x. drop returns all but the first i elements of list x.

(take '(a b c d e) 2) => (a b) (drop '(a b c d e) 2) => (c d e)

x may be any value:

(take '(1 2 3 . d) 2) => (1 2) (drop '(1 2 3 . d) 2) => (3 . d) (drop '(1 2 3 . d) 3) => d

drop is exactly equivalent to performing i cdr operations on x. The returned value shares a common tail with x. On the other hand, take always allocates a new list for result if the argument is a list of non-zero length.

An error is signalled if i is past the end of list x. See take* and drop* below for more tolerant version.

For generic subsequence extraction from any sequence, see subseq in Slicing sequence.

Function: take* list k :optional (fill? #f) (padding #f)

Function: drop* list k

More tolerant version of take and drop. They won’t raise an error even if k is larger than the size of the given list.

If the list is shorter than k elements, take* returns a copy of list by default. If fill? is true, padding is added to the result to make its length k.

On the other hand, drop* just returns an empty list when the input list is shorter than k elements.

(take* '(a b c d) 3) ⇒ (a b c) (take* '(a b c d) 6) ⇒ (a b c d) (take* '(a b c d) 6 #t) ⇒ (a b c d #f #f) (take* '(a b c d) 6 #t 'z) ⇒ (a b c d z z) (drop* '(a b c d) 3) ⇒ (d) (drop* '(a b c d) 5) ⇒ ()

Note: For generic subsequence extraction from any sequence, see subseq in Slicing sequence.

Function: take-right lis k

Function: drop-right lis k

[SRFI-1] take-right returns the last k elements of lis. drop-right returns all but the last k elements of lis.

(take-right '(a b c d e) 2) => (d e) (drop-right '(a b c d e) 2) => (a b c)

lis may be any finite list.

(take-right '(1 2 3 . d) 2) => (2 3 . d) (drop-right '(1 2 3 . d) 2) => (1) (take-right '(1 2 3 . d) 0) => d (drop-right '(1 2 3 . d) 0) => (1 2 3)

take-right’s return value always shares a common tail with lis. drop-right always allocates a new list if the argument is a list of non-zero length.

An error is signalled if k is larger than the length of lis. See take-right* and drop-right* below, for more tolerant version.

Function: take-right* list k :optional (fill? #f) (padding #f)

Function: drop-right* list k

Like take* and drop*, but counts from right of list. If list is shorter than k elements, they won’t raise an error. Instead, drop-right* just returns an empty list, and take-right* returns list itself by default. If fill? is true for take-right*, padding is added on the left of the result to make its length k. The result still shares the list.

Function: take! lis k

Function: drop-right! lis k

[SRFI-1] Linear update variants of take and drop-right. Those procedures may destructively modifies lis.

If lis is circular, take! may return a list shorter than expected.

Function: list-tail list k :optional fallback

[R5RS] Returns k-th cdr of list. list can be a proper, dotted or circular list. (If list is a dotted list, its last cdr is simply ignored).

If k is negative or larger than the length of list, the behavior depends on whether the optional fallback argument is given or not. If fallback is given, it is returned. Otherwise, an error is signalled.

Function: list-ref list k :optional fallback

[R5RS+] Returns k-th element of list. list can be a proper, dotted or circular list.

By default, list-ref signals an error if k is negative, or greater than or equal to the length of list. However, if an optional argument fallback is given, it is returned for such case. This is an extension of Gauche.

Function: last-pair list

[SRFI-1] Returns the last pair of list. list can be a proper or dotted list.

(last-pair '(1 2 3)) ⇒ (3) (last-pair '(1 2 . 3)) ⇒ (2 . 3) (last-pair 1) ⇒ error

Function: last pair

[SRFI-1] Returns the last element of the non-empty, finite list pair. It is equivalent to (car (last-pair pair)).

(last '(1 2 3)) ⇒ 3 (last-pair '(1 2 . 3)) ⇒ 2

Function: split-at x i

Function: split-at! x i

[SRFI-1] split-at splits the list x at index i, returning a list of the first i elements, and the remaining tail.

(split-at '(a b c d e) 2) ⇒ (a b) (c d e)

split-at! is the linear-update variant. It may destructively modifies x to produce the result.

Function: split-at* list k :optional (fill? #f) (padding #f)

More tolerant version of split-at. Returns the results of take* and drop*.

(split-at* '(a b c d) 6 #t 'z) ⇒ (a b c d z z) and ()

Function: slices list k :optional fill? padding

Splits list into the sublists (slices) where the length of each slice is k. If the length of list is not a multiple of k, the last slice is dealt in the same way as take*; that is, it is shorter than k by default, or added padding if fill? is true.

(slices '(a b c d e f g) 3) ⇒ ((a b c) (d e f) (g)) (slices '(a b c d e f g) 3 #t 'z) ⇒ ((a b c) (d e f) (g z z))

Function: intersperse item list

Inserts item between elements in the list. (The order of arguments is taken from Haskell’s intersperse).

(intersperse '+ '(1 2 3)) ⇒ (1 + 2 + 3) (intersperse '+ '(1)) ⇒ (1) (intersperse '+ '()) ⇒ ()

6.6.5 Walking over lists

Function: map proc list1 list2 …

[R5RS+] Applies proc for each element(s) of given list(s), and returns a list of the results. R5RS doesn’t specify the application order of map, but Gauche guarantees proc is always applied in order of the list(s). Gauche’s map also terminates as soon as one of the list is exhausted.

(map car '((a b) (c d) (e f))) ⇒ (a c e) (map cons '(a b c) '(d e f)) ⇒ ((a . d) (b . e) (c . f))

Note that the gauche.collection module (See section gauche.collection - Collection framework) extends map to work on any type of collection.

Function: map* proc tail-proc list1 list2 …

Like map, except that tail-proc is applied to the cdr of the last pair in the argument(s) to get the cdr of the last pair of the result list. This procedure allows improper list to appear in the arguments. If a single list is given, tail-proc always receives a non-pair object.

(map* - / '(1 2 3 . 4)) ⇒ (-1 -2 -3 . 1/4) (define (proper lis) (map* values (lambda (p) (if (null? p) '() (list p))) lis)) (proper '(1 2 3)) ⇒ (1 2 3) (proper '(1 2 3 . 4)) ⇒ (1 2 3 4)

If more than one list are given, the shortest one determines how tail-proc is called. When map* reaches the last pair of the shortest list, tail-proc is called with cdrs of the current pairs.

(map* + vector '(1 2 3 4) '(1 2 . 3)) ⇒ (3 6 . #((3 4) 3))

Note: The name map* is along the line of list*/cons* that can produce improper list (See section List constructors, See section List utilities).

Function: for-each proc list1 list2 …

[R5RS] Applies proc for each element(s) of given list(s) in order. The results of proc are discarded. The return value of for-each is undefined. When more than one list is given, for-each terminates as soon as one of the list is exhausted.

Note that the gauche.collection module (See section gauche.collection - Collection framework) extends for-each to work on any type of collection.

Function: fold kons knil clist1 clist2 …

[SRFI-1] The fundamental list iterator. When it is given a single list clist1 = (e1 e2 … en), then this procedure returns

(kons en … (kons e2 (kons e1 knil)) … )

If n list arguments are provided, then the kons function must take n+1 parameters: one element from each list, and the "seed" or fold state, which is initially knil. The fold operation terminates when the shortest list runs out of values. At least one of the list arguments must be finite.

Examples:

(fold + 0 '(3 1 4 1 5 9)) ⇒ 23 ;sum up the elements (fold cons '() '(a b c d e)) ⇒ (e d c b a) ;reverse (fold cons* '() '(a b c) '(1 2 3 4 5)) ⇒ (c 3 b 2 a 1) ;n-ary case

Function: fold-right kons knil clist1 clist2 …

[SRFI-1] The fundamental list recursion operator. When it is given a single list clist1 = (e1 e2 … en), then this procedure returns

(kons e1 (kons e2 … (kons en knil)))

If n list arguments are provided, then the kons function must take n+1 parameters: one element from each list, and the "seed" or fold state, which is initially knil. The fold operation terminates when the shortest list runs out of values. At least one of the list arguments must be finite.

Examples:

(fold-right cons '() '(a b c d e)) ⇒ (a b c d e) ;copy list (fold-right cons* '() '(a b c) '(1 2 3 4 5)) ⇒ (a 1 b 2 c 3) ;n-ary case

Function: fold-left snok knil clist1 clist2 …

[R6RS] This is another variation of left-associative folding. When it is given a single list clist1 = (e1 e2 … en), then this procedure returns:

(snok (… (snok (snok knil e1) e2) …) en)

Compare this with fold above; association is the same, but the order of arguments passed to the procedure snok is reversed from the way arguments are passed to kons in fold. If snok is commutative, fold and fold-left produces the same result.

(fold-left + 0 '(1 2 3 4 5) ⇒ 15 (fold-left cons 'z '(a b c d)) ⇒ ((((z . a) . b) . c) . d) (fold-left (^[a b] (cons b a)) 'z '(a b c d)) ⇒ (a b c d z)

If more than one lists are given, snok is called with the current seed value knil and each corresponding element of the input lists clist1 clist2 ….

(fold-left list 'z '(a b c) '(A B C)) ⇒ (((z a A) b B) c C)

Note: Most functional languages have left- and right- associative fold operations, which correspond to fold-left and fold-right, respectively. (e.g. Haskell’s foldl and foldr). In Scheme, SRFI-1 first introduced fold and fold-right. R6RS introduced fold-left. (However, in R6RS the behavior is undefined if the lengths of clist1 clist2 … aren’t the same, while in Gauche fold-left terminates as soon as any one of the lists terminates.)

Function: filter pred list

Function: filter! pred list

[SRFI-1] A procedure pred is applied on each element of list, and a list of elements that pred returned true on it is returned.

(filter odd? '(3 1 4 5 9 2 6)) ⇒ (3 1 5 9)

filter! is the linear-update variant. It may destructively modifies list to produce the result.

Function: filter-map f clist1 clist2 …

[SRFI-1] Like map, but only true values are saved. At least one of the list arguments must be finite.

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

Function: remove pred list

Function: remove! pred list

[SRFI-1] A procedure pred is applied on each element of list, and a list of elements that pred returned false on it is returned.

(remove odd? '(3 1 4 5 9 2 6)) ⇒ (4 2 6)

remove! is the linear-update variant. It may destructively modifies list to produce the result.

Function: find pred clist

[SRFI-1] Applies pred for each element of clist, from left to right, and returns the first element that pred returns true on. If no element satisfies pred, #f is returned.

Function: find-tail pred clist

[SRFI-1] Applies pred for each element of clist, from left to right, and when pred returns a true value, returns the pair whose car is the element. If no element satisfies pred, #f is returned.

Function: any pred clist1 clist2 …

[SRFI-1] Applies pred across each element of clists, and returns as soon as pred returns a non-false value. The return value of any is the non-false value pred returned. If clists are exhausted before pred returns a non-false value, #f is returned.

Function: every pred clist1 clist2 …

[SRFI-1] Applies pred across each element of clists, and returns #f as soon as pred returns #f. If all application of pred return a non-false value, every returns the last result of the applications.

Function: delete x list :optional elt=

Function: delete! x list :optional elt=

[SRFI-1] Equivalent to

(remove (lambda (y) (elt= x y)) list) (remove! (lambda (y) (elt= x y)) list)

The comparison procedure, elt=, defaults to equal?.

Function: delete-duplicates list :optional elt=

Function: delete-duplicates! list :optional elt=

[SRFI-1] Removes duplicate elements from list. If there are multiple equal elements in list, the result list only contains the first or leftmost of these elements in the result. The order of these surviving elements is the same as in the original list. The comparison procedure, elt=, defaults to equal?.

6.6.6 Other list procedures

Function: append list …

[R5RS] Returns a list consisting of the elements of the first list followed by the elements of the other lists. The resulting list is always newly allocated, except that it shares structure with the last list argument. The last argument may actually be any object; an improper list results if the last argument is not a proper list.

Function: append! list …

[SRFI-1] Returns a list consisting of the elements of the first list followed by the elements of the other lists. The cells in the lists except the last one may be reused to construct the result. The last argument may be any object.

Function: reverse list :optional (tail '())

Function: reverse! list :optional (tail '())

[R5RS+, SRFI-1+] Returns a list consisting of the elements of list in the reverse order. While reverse always returns a newly allocated list, reverse! may reuse the cells of list. Even list is destructively modified by reverse!, you should use its return value, for the first cell of list may not be the first cell of the returned list.

If an optional argument tail is given, it becomes the tail of the returned list (tail isn’t copied). It is useful in the idiom to prepend the processed results on top of already existing results.

(reverse '(1 2 3 4 5)) ⇒ (5 4 3 2 1) (reverse '(1 2 3) '(a b)) ⇒ (3 2 1 a b)

The tail argument isn’t in the traditional Scheme’s reverse. The rationale is the following correspondence:

(reverse xs) ≡ (fold cons xs '()) (reverse xs tail) ≡ (fold cons xs tail)

Function: memq obj list

Function: memv obj list

Function: member obj list :optional obj=

[R5RS][SRFI-1] Searches obj in the list. If n-th element of list equals to obj (in the sense of eq? for memq, eqv? for memv, and equal? for member), (list-tail list n) is returned. Otherwise, #f is returned.

The optional obj= argument of member is SRFI-1’s extension to R5RS. If given, it is used as a equivalence predicate instead of equal?.

(memq 'a '(a b c)) ⇒ (a b c) (memq 'b '(a b c)) ⇒ (b c) (memq 'a '(b c d)) ⇒ #f (memq (list 'a) '(b (a) c)) ⇒ #f (memv 101 '(100 101 102)) ⇒ (101 102)

6.6.7 Association lists

Function: acons obj1 obj2 obj3

Returns (cons (cons obj1 obj2) obj3). Useful to put an entry at the head of an associative list.

(This procedure is defined in SRFI-1 as alist-cons; See section srfi-1 - List library).

(acons 'a 'b '((c . d))) ⇒ ((a . b) (c . d))

Function: alist-copy alist

[SRFI-1] Returns a fresh copy of alist. The spine of alist and each cell that points a key and a value is copied.

(define a (list (cons 'a 'b) (cons 'c 'd))) a ⇒ ((a . b) (c . d)) (define b (alist-copy a)) b ⇒ ((a . b) (c . d)) (set-cdr! (car a) 'z) a ⇒ ((a . z) (c . d)) b ⇒ ((a . b) (c . d))

Function: assq obj list

Function: assv obj list

Function: assoc obj list :optional key=

[R5RS][SRFI-1] Each element in list must be a pair. These procedures search a pair whose car matches obj (in the sense of eq? for assq, eqv? for assv, and equal? for assoc) from left to right, and return the leftmost matched pair if any. If no pair matches, these return #f.

The optional argument of ascoc is an extension defined in SRFI-1. If given, it is called instead of equal? to check the equivalence of obj and each key.

Function: alist-delete key alist :optional key=

Function: alist-delete! key alist :optional key=

[SRFI-1] Deletes all cells in alist whose key is the same as key. Comparison is done by a procedure key=. The default is eqv?.

The linear-update version alist-delete! may or may not modify alist.

Function: rassoc key alist :optional eq-fn

Function: rassq key alist

Function: rassv key alist

Reverse associations—given key is matched to the cdr of each element in alist, instead of the car. Handy to realize bidirectional associative list. Rassoc takes an optional comparison function, whose default is equal?. Rassq and rassv uses eq? and eqv?.

Function: assoc-ref alist key :optional default eq-fn

Function: assq-ref alist key :optional default

Function: assv-ref alist key :optional default

These procedures provide the access to the assoc list symmetric with other *-ref procedures. (Note that the argument order is different from assoc, assq and assv – *-ref procedures take a container first, and an item second.)

This captures the common pattern of alist access:

(assoc-ref alist key default eq-fn) ≡ (cond [(assoc key alist eq-fn) => cdr] [else default])))

If default is omitted, #f is used.

Assoc-ref takes an optional comparison function eq-fn, whose default is equal?. Assq-ref and assv-ref uses eq? and eqv?, respectively.

Function: rassoc-ref alist key :optional default eq-fn

Function: rassq-ref alist key :optional default

Function: rassv-ref alist key :optional default

Reverse association version of assoc-ref.

(rassoc-ref alist key default eq-fn) ≡ (cond ((rassoc key alist eq-fn) => car) (else default))))

The meanings of optional arguments are the same as assoc-ref.

Function: assoc-set! alist key val :optional eq-fn

Function: assq-set! alist key val

Function: assv-set! alist key val

Returns an alist who has (key . val) pair added to the alist. If alist already has an element with key, the element’s cdr is destructively modified for val. If alist doesn’t have an element with key, a new pair is created and appended in front of alist; so you should use the return value to guarantee key-val pair is added.

Assoc-set! takes optional comparison function eq-fn, whose default is equal?. Assq-set! and assv-set! uses eq? and eqv?, respectively.

This document was generated by Shiro Kawai on May 28, 2012 using texi2html 1.82.