For Development HEAD DRAFTSearch (procedure/syntax/module):

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 scheme.list - R7RS lists 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 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 Mutable and immutable pairs

A pair may be either mutable or immutable. You can desctructively modify mutable pairs with set-car!, set-cdr!, or other destructive procedures (usually they have ! at the end). An error is signaled when you try to modify an immutable pair.

In Gauche, both type of pairs can be treated the same unless you try to modify them. Both satisfies the predicate pair?. If you need to test specifically if a pair is immutable, use ipair? (see List predicates). The traditional constructor cons creates a mutable pair; you can create an immutable pair with ipair (see List constructors). More procedures that use immutable pairs are defined in R7RS-large scheme.ilist module (see scheme.ilist - R7RS immutable lists).

Note that quoted literals are immutable. Old versions of Gauche wasn’t supported immutable pairs and quoted literal lists were mutable. If your code accidentally mutate such pairs, you’ll get an error. If you need to run such code without tracking down the error, you can define the environment variable GAUCHE_MUTABLE_LITERALS.


6.6.3 List predicates

Function: pair? obj

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

Function: ipair? obj

[R7RS ilist] Returns #t iff obj is an immutable pair, #f otherwise.

An immutable pair is indistinguishable from a mutable pair except using this predicate, or when you attempt to modify it. See Mutable and immutable pairs.

Function: null? obj

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

Function: null-list? obj

[R7RS list] 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

[R7RS base] 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

[R7RS list] Returns #t fif x is a proper list, that is, a finite list terminated by ().

Function: circular-list? x

[R7RS list] Returns #t if x is a circular list. A list is circular if you follow cdr of the pairs you’ll eventually get to a pair you already visited. It doesn’t necessary that the head of the list x is a part of the circle. A list isn’t circular by the cycle that involves car of the paris.

Function: dotted-list? x

[R7RS list] 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.4 List constructors

Function: cons obj1 obj2

[R7RS base] Constructs a mutable pair of obj1 and obj2 and returns it.

(cons 'a 'b) ⇒ (a . b)
Function: ipair obj1 obj2

[R7RS ilist] Constructs an immutable pair of obj1 and obj2 and returns it.

(ipair 'a 'b) ⇒ (a . b)
Function: make-list len :optional fill

[R7RS base] 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 …

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

(list 1 2 3) ⇒ (1 2 3)
(list) ⇒ ()
Function: ilist obj …

[R7RS ilist] Makes a list, whose elements are obj …, and which consists of immutable pairs.

(ilist 1 2 3) ⇒ (1 2 3)
(ilist) ⇒ ()

(list-set! (ilist 1 2 3) 1 'a)
  ⇒ ERROR: Attempt to modify an immutable pair: (2 3)
Function: list* obj1 obj2 …
Function: cons* obj1 obj2 …

[R7RS list] 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 (R7RS (scheme list))defines cons*.

(list* 1 2 3) ⇒ (1 2 . 3)
(list* 1) ⇒ 1
Function: list-copy list

[R7RS base] Shallow copies list. If list is circular, an error is thrown. (Detecting circular list is Gauche’s extension; R7RS allows the procedure to diverge.)

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

[R7RS list] Returns a list of count numbers, starting from start, increasing by step. Count must be a nonnegative integer. If both start and step are exact, the result is a list of exact numbers; otherwise, it is a list of inexact numbers.

(iota 5)        ⇒ (0 1 2 3 4)
(iota 5 1 3/7)  ⇒ (1 10/7 13/7 16/7 19/7)
(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 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.5 List accessors and modifiers

Function: car pair
Function: cdr pair

[R7RS base] Returns car and cdr of pair, respectively.

Function: set-car! pair obj
Function: set-cdr! pair obj

[R7RS base] 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

[R7RS base][R7RS cxr] caar(car (car x)), cadr(car (cdr x)), and so on.

In R7RS, more than two-level of accessors are defined in the (scheme cxr) library.

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

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

Function: length+ x

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

If you want a length of dotted list in terms of the number of pairs, use num-pairs below.

Function: length=? x k
Function: length<? x k
Function: length<=? x k
Function: length>? x k
Function: length>=? x k

Returns #t iff x is a (possibly improper) list whose length is equal to, less than, less than or equal to, greater than, or greater than or equal to an exact integer k, respectively. This procedure only follows the list up to the k items, so it doesn’t realize elements of lazy sequence more than needed (See Lazy sequences, for the lazy sequences).

Dotted lists and circular lists are allowed. For the dotted list, the cdr of the last pair isn’t counted; that is, a non-pair object has length 0, and (a . b) has length 1. A circular list is treated as if it has infinite length.

(length<=? '(a b) 2)  ⇒ #t
(length<=? '(a b) 1)  ⇒ #f
(length<=? '()    0)  ⇒ #t

;; dotted list cases
(length<=? 'a       0)  ⇒ #t
(length<=? '(a . b) 0)  ⇒ #f
(length<=? '(a . b) 1)  ⇒ #t

NB: The name of these procedures might be misleading, for other procedures with the name something<=? etc. usually takes objects of the same type. We don’t have any better idea now, unfortunately.

Function: num-pairs lis

Returns the number of pairs that consists a (proper, dotted, or circular) list lis, in an exact ineger. If lis is a proper list, it is the same as length.

(num-pairs '(a b c d e))    ⇒ 5
(num-pairs '())             ⇒ 0
(num-pairs '(a b c d . e))  ⇒ 4
(num-pairs 'a)              ⇒ 0
(num-pairs '#0=(a b . #0#)) ⇒ 2
(num-pairs '(a . #0=(b c . #0#))) ⇒ 3
Function: take x i
Function: drop x i

[R7RS list] 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 signaled 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

[R7RS list] 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 signaled 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

[R7RS list] 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

[R7RS base] 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 signaled.

Function: list-ref list k :optional fallback

[R7RS+ base] 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: list-set! list k v

[R7RS base] Modifies the k-th element of a list by v. It is an error unless k is an exact integer between 0 and one minus the length of k. If list is immutable, no error is signalled but the behavior is undefined.

Function: last-pair list

[R7RS list] 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

[R7RS list] 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 '(1 2 . 3)) ⇒ 2
Function: split-at x i
Function: split-at! x i

[R7RS list] 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.6 Walking over lists

Function: map proc list1 list2 …

[R7RS+ base] Applies proc for each element(s) of given list(s), and returns a list of the results. R7RS 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 gauche.collection - Collection framework) extends map to work on any type of collection.

Function: append-map f clist1 clist2 …
Function: append-map! f clist1 clist2 …

[R7RS list] Functionally equivalent to the followings, though a bit more efficient:

  (apply append (map f clist1 clist2 ...))
  (apply append! (map f clist1 clist2 ...))

At least one of the list arguments must be finite.

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))
  ⇒ (2 4 . #((3 4) 3))

Note: The name map* is along the line of list*/cons* that can produce improper list (See List constructors, see scheme.list - R7RS lists).

Function: for-each proc list1 list2 …

[R7RS base] 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 gauche.collection - Collection framework) extends for-each to work on any type of collection.

Function: fold kons knil clist1 clist2 …

[R7RS list] The fundamental list iterator. When it is given a single list clist1 = (e1 e2en), 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 …

[R7RS list] The fundamental list recursion operator. When it is given a single list clist1 = (e1 e2en), 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 e2en), 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: reduce f ridentity list
Function: reduce-right f ridentity list

[R7RS list] Variant of fold and fold-right. f must be a binary operator, and ridentity is the value such that for any value x that is valid as f’s input,

 (f x ridentity) ≡ x

These functions effectively do the same thing as fold or fold-right, respectively, but omit the first application of f to ridentity, using the above nature. So ridentity is used only when list is empty.

Function: filter pred list
Function: filter! pred list

[R7RS list] 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 …

[R7RS list] 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

[R7RS list] 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

[R7RS list] 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

[R7RS list] 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 …

[R7RS list] 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 …

[R7RS list] 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: count pred clist1 clist2 …

[R7RS list] A procedure pred is applied to the n-th element of given lists, from n is zero to the length of the the shortest finite list in the given lists, and the count of times pred returned true is returned.

(count even? '(3 1 4 1 5 9 2 5 6)) ⇒ 3
(count < '(1 2 4 8) '(2 4 6 8 10 12 14 16)) ⇒ 3

At least one of the argument lists must be finite:

(count < '(3 1 4 1) (circular-list 1 10)) ⇒ 2
Function: delete x list :optional elt=
Function: delete! x list :optional elt=

[R7RS list] 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=

[R7RS list] 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.7 Other list procedures

Function: append list …

[R7RS base] 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 …

[R7RS list] 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: concatenate list-of-lists
Function: concatenate! list-of-lists!

[R7RS list] Equivalent to (apply append list-of-lists) and (apply append! list-of-lists), respectively, but this can be a bit efficient by skipping overhead of apply.

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

[R7RS+ base] 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 is Gauche’s extension, and it 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)

For portable code, append-reverse/append-reverse! below can be used in place of two-argument reverse/reverse!.

Function: append-reverse rev-head tail
Function: append-reverse! rev-head tail

[R7RS list] Equivalent to the two-argument reverse and reverse!. Provided for SRFI-1 (R7RS (scheme list)) compatibility.

Function: memq obj list
Function: memv obj list
Function: member obj list :optional obj=

[R7RS base] 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.

If the optional obj= argument of member is 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.8 Association lists

An association list is a list of pairs. Each car of a pair is a key, and each cdr of a pair is an associated value. It is the earliest data structure to represent mappings.

It takes O(N) to lookup so it’s not suitable for large amount of data, but it is still widely used since it’s easy to realize immutable mapping (the new entries can “shadow” the existing entries with the same key, allowing to “change” the content without mutating existing maps).

Basic constructor and accessors

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 (R7RS (scheme list)) as alist-cons; see scheme.list - R7RS lists).

(acons 'a 'b '((c . d))) ⇒ ((a . b) (c . d))
Function: assq obj list
Function: assv obj list
Function: assoc obj list :optional key=

[R7RS base] Each element in list should be a pair (Gauche ignores non-pair element in list, but other R7RS implementation may raise an error, so be aware of it when you’re writing a portable code). 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.

If the optional argument of assoc is given, it is called instead of equal? to check the equivalence of obj and each key.

Function: rassoc val alist :optional val=
Function: rassq val alist
Function: rassv val alist

Reverse associations—given val 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?.

Advanced operations

Function: alist-copy alist

[R7RS list] 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: alist-ref alist key :optional key= default

Lookup key from an assoc list alist, in the symmetric way with other *-ref procedures. Keys are compared with key=, which defaults to equal?.

This captures the common pattern of alist access:

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

If default is omitted, #f is used.

NB: This procedure supersedes a legacy assoc-ref, assq-ref and assv-ref, by the following reasons: Its name is very similar to assoc etc. but the argument order is different, and most other modern alist operators has the name prefix alist-. Be aware that the optional arguments of alist-ref differs from assoc-ref, when you update your code. It is to make it easier to cover the valiations of key equality procedures, e.g. (assq-ref alist key)(alist-ref alist key eq?).

Function: alist-key alist val :optional val= default

Returns a key that has the associated value equal to val. This is to alist-ref as rassoc is to assoc. The value is compared by val=, whose default is equal?. If no entry’s value matches val, default is returned, whose default is #f.

(alist-key alist val val= default)
  ≡
  (cond ((rassoc val alist val=) => car)
        (else default))

NB: This procedure supersedes legacy rassoc-ref, rassq-ref, and rassv-ref. See alist-ref entry above for the rationale. Be aware of the order of optional arguments, which differs from rassoc-ref.

Function: alist-set! alist key val :optional key=

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.

The keys are compared with key=, whose default is equal?.

If you don’t want to mutate the original alist, use alist-adjoin below.

Function: alist-adjoin alist key val :optional key=

A functional variation of alist-set!.

If alist contains an entry with key, returns a new associative list where the value of the key is replaced for val. The order of entries in alist is preserved. If alist doesn’t contain the entry, it returns (acons key val alist).

The original alist is left unmodified. The returned associative list may share a part of its tail with the original alist, however.

The optional key= argument is a procedure with two arguments to be used to compare the keys; the default is equal?.

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

[R7RS list] Deletes all cells in alist whose key is the same as key. Comparison is done by a procedure key=. The default is equal?.

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

Note the order of arguments: Unfortunately, this procedure doesn’t follow the rule to take alist as the first argument This is defined in srfi-1 and followed assoc.

Function: alist-merge [key=] reducer alist1 alist2 …

Returns a new assoc list that contains all keys in alist1 alist2 …. If more than one input alist have the same key, they are merged to a single entry using reducer as follows: Suppose values of those entries are x, y, and z, in the order of appearance in the input alists. Then the value of the resulting entry is (reducer x (reducer y z).

(alist-merge + '((a . 1) (b . 2)) '((c . 3) (a . 4)) '((b . 5)))
 ⇒ ((a . 5) (b . 7) (c . 3))
(alist-merge string=? append
  '(("a" 1) ("b" 2) ("c" 3))
  '(("b" 4) ("d" 5))
  '(("c" 6)))
 ⇒ (("a" 1) ("b" 2 4) ("c" 3 6) ("d" 5))

The order of entries of the result preserves the order of the input, except the duplicate key entries are merged into the first one.

Note: This assumes each alist doesn’t have duplicate keys in itself. To gether entries of the same keys in an alist, you can use group-collection->alist in gauche.collection (see gauche.collection - Collection framework).

Function: alist-update-in alist keys proc :optional key= default

This procedure allows to update a nested associative list. The alist argument is a (possibly nested) associative list, keys are a list of keys, and proc is a procedure that takes one argument. First, the keys are looked up recursively in alist; then its value is passed to proc. The return value is a new (nested) associative list where the value pointed by keys is replaced with the return value of proc.

(assoc-update-in '((a (b . 1) (c . 2))) '(a c) (cut + <> 1))
  ⇒ ((a (b . 1) (c . 3))

The order of entries are preserved. The original alist is left unmodified, but the returned value may share a part of the structure with alist.

If alist doesn’t have the entry specified by keys, a new entry is added. A new entry is added at the beginning of the sequence where specified key didn’t exist.

(assoc-update-in '((a (b . 1) (c . 2))) '(a d e) (^_ 99))
  ⇒ ((a (d (e . 99)) (b . 1) (c . 3)))

The default argument is passed to proc when there’s no entry with specified keys. If omitted, #f is assumed.

The optional key= argument is a procedure with two arguments to be used to compare the keys; the default is equal?.

Note: For destructively updating general nested aggregate structures, setter of ~ is handy (see Universal accessor). You can modify an entry in a hashtable in a vector in a list, for example. Associative list is a bit special, since you can’t distinguish it from lists (thus ~ can’t be used), and it is mostly used in functional way. So we added a special update procedure.

Deprecated procedures

The following procedures are deprecated for the naming consistency. Except a handful historical procedures (assoc etc.), associative list operations are now named alist-* and takes alist as the first argument as long as it is relevant.

Function: assoc-ref alist key :optional default key=
Function: assq-ref alist key :optional default
Function: assv-ref alist key :optional default

Deprecated. (assoc-ref alist key default key=)(alist-ref alist key key= default). Note the order of the optional arguments.

(assq-ref alist key default)(alist-ref alist key eq? default).

(assv-ref alist key default)(alist-ref alist key eqv? default).

Function: rassoc-ref alist val :optioanl default val=
Function: rassq-ref alist val :optional default
Function: rassv-ref alist val :optional default

Deprecated. (rassoc-ref alist val default val=)(alist-key alist val val= default). Note the order of the optional arguments.

(rassq-ref alist val default)(alist-key alist val eq? default).

(rassv-ref alist key default)(alist-key alist val eqv? default).

Function: assoc-set! alist key val :optional key=
Function: assq-set! alist key val
Function: assv-set! alist key val

Deprecated. (assoc-set! alist key key=)(alist-set! alist key key=).

(assq-set! alist key)(alist-set! alist key eq?).

(assv-set! alist key)(alist-set! alist key eqv?).

Function: assoc-adjoin alist key val :optional key=

Deprecated. Same as alist-adjoin.

Function: assoc-update-in alist keys proc :optional default key=

Deprecated. assoc-update-in alist keys proc default key=alist-update-in alist keys proc key= default

Note the order of optional arguments.


6.6.9 Extended pairs and pair attributes

Gauche has a special kind of pairs, called extended pairs. It behaves exactly the same as ordinary pairs, but you can associate an attribute list to it. Gauche uses it to keep source-code location information, for example.

Extended pairs don’t incur any overhead in accessing its car/cdr; set-car! and set-cdr! has a little overhead (another reason you should avoid mutation!). Internally it takes up twice of memory than the ordinary pairs.

Pair attributes are not written out in the external representation, and not copied by copy-list and many other list procedures that constructs the output list from the input list. That is, they are easily lost. Use them for the ancillary information which is nice to have but not mandatory.

Keep in mind that code using extended pairs is not easily ported to other Scheme implementations, although the feature can be emulated with a separate weak hash table.

Function: extended-pair? obj

Returns #t iff obj is an extended pair.

Function: extended-cons car cdr :optional attrs

Returns an extended pair of car and cdr. If an optional attrs argument is given, it must be an alist, specifying initial pair attributes. By default, the pair attributes of the created extended pair is empty.

Function: extended-list obj obj2 …

Creates and returns a list of obj obj2 …, but its first pair is an extended pair. Note that the subsequent pairs are ordinary pairs.

Function: pair-attributes pair

Returns pair attributes of pair as an alist. You can pass an ordinary pair, in which case an empty list is returned.

(pair-attributes (extended-cons 'a 'b '((c . d) (e . f))))
  ⇒ ((c . d) (e . f))

(pair-attributes (cons 'a 'b)
  ⇒ ()
Function: pair-attribute-get pair key :optional default

Returns the value associated to the key key in the pair attributes of pair. Key can be any Scheme object, and compared with eq?. If there’s no value associated with the given key, default is returned if it is given, otherwise an error is signaled.

You can pass an ordinary pair as pair; in that case, it is treated with empty pair attributes.

Function: pair-attribute-set! pair key value

Adds a pair attribute of key with value to an extended pair pair. Key and value can be any Scheme object. An error is thrown if pair is not an exteded pair.

This procedure does not mutate the exising alist, but rather makes a necessary copy. The pair attributes are not supposed to be mutated frequently.



For Development HEAD DRAFTSearch (procedure/syntax/module):
DRAFT