For Gauche 0.9.5

Next: , Previous: , Up: Library modules - SRFIs   [Contents][Index]

11.1 srfi-1 - List library

Module: srfi-1

SRFI-1 is a rich collection of list manipulation library (SRFI-1). It is available by saying (use srfi-1). The implementation is based on Olin Shivers’s reference implementation.

Note that Gauche supports quite a few SRFI-1 procedures as built-in. The following SRFI-1 procedures can be used without loading srfi-1 module. For the manual entries of these procedures, Pairs and Lists.

null-list? cons* last member
take drop take-right drop-right take! drop-right!
delete delete! delete-duplicates delete-duplicates!
assoc alist-copy alist-delete alist-delete!
any every filter filter! fold fold-right find find-tail
split-at split-at! iota

Next: , Previous: , Up: List library   [Contents][Index]

11.1.1 List utilities

List constructors

Function: xcons cd ca

[SRFI-1] Equivalent to (cons ca cd). Useful to pass to higher-order procedures.

Function: list-tabulate n init-proc

[SRFI-1] Constructs an n-element list, in which each element is generated by (init-proc i).

(list-tabulate 4 values) ⇒ (0 1 2 3)
Function: circular-list elt1 elt2 …

[SRFI-1] Constructs a circular list of the elements.

(circular-list 'z 'q) ⇒ (z q z q z q …)

List predicates

Function: not-pair? x

[SRFI-1] (lambda (x) (not (pair? x))).

SRFI-1 says: Provided as a procedure as it can be useful as the termination condition for list-processing procedures that wish to handle all finite lists, both proper and dotted.

Function: list= elt= list …

[SRFI-1] Determines list equality by comparing every n-th element of given lists by the procedure elt=.

It is an error to apply list= to anything except proper lists.

The equality procedure must be consistent with eq?, i.e.

(eq? x y) ⇒ (elt= x y).

List selectors

Function: first pair
Function: second pair
Function: third pair
Function: fourth pair
Function: fifth pair
Function: sixth pair
Function: seventh pair
Function: eighth pair
Function: ninth pair
Function: tenth pair

[SRFI-1] Returns n-th element of the (maybe improper) list.

Function: car+cdr pair

[SRFI-1] Returns two values, (car pair) and (cdr pair).

List miscellaneous routines

Function: zip clist1 clist2 …

[SRFI-1] Equivalent to (map list clist1 clist2 …). If zip is passed n lists, it returns a list as long as the shortest of these lists, each element of which is an n-element list comprised of the corresponding elements from the parameter lists.

(zip '(one two three)
     '(1 2 3)
     '(odd even odd even odd even odd even))
     ⇒ ((one 1 odd) (two 2 even) (three 3 odd))

(zip '(1 2 3)) ⇒ ((1) (2) (3))

At least one of the argument lists must be finite:

(zip '(3 1 4 1) (circular-list #f #t))
     ⇒ ((3 #f) (1 #t) (4 #f) (1 #t))
Function: unzip1 list
Function: unzip2 list
Function: unzip3 list
Function: unzip4 list
Function: unzip5 list

[SRFI-1] unzip1 takes a list of lists, where every list must contain at least one element, and returns a list containing the initial element of each such list. unzip2 takes a list of lists, where every list must contain at least two elements, and returns two values: a list of the first elements, and a list of the second elements. unzip3 does the same for the first three elements of the lists, and so on.

(unzip2 '((1 one) (2 two) (3 three))) ⇒
   (1 2 3) and
   (one two three)

List fold, unfold & map

Function: pair-fold kons knil clist1 clist2 …
Function: pair-fold-right kons knil clist1 clist2 …

[SRFI-1] Like fold and fold-right, but the procedure kons gets each cdr of the given clists, instead of car.

(pair-fold cons '() '(a b c d e))
  ⇒ ((e) (d e) (c d e) (b c d e) (a b c d e))

(pair-fold-right cons '() '(a b c d e))
  ⇒ ((a b c d e) (b c d e) (c d e) (d e) (e))
Function: unfold p f g seed :optional tail-gen

[SRFI-1] Fundamental recursive list constructor. Defined by the following recursion.

(unfold p f g seed tail-gen) ≡
   (if (p seed)
       (tail-gen seed)
       (cons (f seed)
             (unfold p f g (g seed))))

That is, p determines where to stop, g is used to generate successive seed value from the current seed value, and f is used to map each seed value to a list element.

(unfold (pa$ = 53) integer->char (pa$ + 1) 48)
  ⇒ (#\0 #\1 #\2 #\3 #\4)
Function: unfold-right p f g seed :optional tail

[SRFI-1] Fundamental iterative list constructor. Defined by the following recursion.

(unfold-right p f g seed tail) ≡
  (let lp ((seed seed) (lis tail))
    (if (p seed)
        (lp (g seed) (cons (f seed) lis))))
(unfold-right (pa$ = 53) integer->char (pa$ + 1) 48)
 ⇒ (#\4 #\3 #\2 #\1 #\0)
Function: map! f clist1 clist2 …

[SRFI-1] The procedure f is applied to each element of clist1 and corresponding elements of clist2s, and the result is collected to a list. Cells in clist1 is reused to construct the result list.

Function: map-in-order f clist1 clist2 …

[SRFI-1] A variant of map, but it guarantees to apply f on each elements of arguments in a left-to-right order. Since Gauche’s map implementation follows the same order, this function is just a synonym of map.

Function: pair-for-each f clist1 clist2 …

[SRFI-1] Like for-each, but the procedure f is applied on clists themselves first, then each cdrs of them, and so on.

(pair-for-each write '(a b c))
 ⇒ prints (a b c)(b c)(c)

List partitioning

Function: partition pred list
Function: partition! pred list

[SRFI-1] filter and remove simultaneously, i.e. returns two lists, the first is the result of filtering elements of list by pred, and the second is the result of removing elements of list by pred.

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

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

List searching

Function: take-while pred clist
Function: take-while! pred list

[SRFI-1] Returns the longest initial prefix of clist whose elements all satisfy pred.

Function: drop-while pred clist

[SRFI-1] Drops the longest initial prefix of clist whose elements all satisfy pred, and returns the rest.

Function: span pred clist
Function: span! pred list
Function: break pred clist
Function: break! pred list

[SRFI-1] span is equivalent to (values (take-while pred clist) (drop-while pred clist)). break inverts the sense of pred.

Function: list-index pred clist1 clist2 …

[SRFI-1] Returns the index of the leftmost element that satisfies pred. If no element satisfies pred, #f is returned.

Association lists

Function: alist-cons key datum alist

[SRFI-1] Returns (cons (cons key datum) alist). This is an alias of the Gauche builtin procedure acons.

Previous: , Up: List library   [Contents][Index]

11.1.2 Lists as sets

These procedures use a list as a set, that is, the elements in a list matter, but their order doesn’t.

All procedures in this category takes a comparison procedure elt=, as the first argument, which is used to determine two elements in the given sets are the same.

Since lists require linear time to search, those procedures aren’t suitable to deal with large sets. See Sets and bags, if you know your sets will contain more than a dozen items or so.

See also Combination library, which concerns combinations of elements in the set.

Function: lset<= elt= list1 …

[SRFI-1] Returns #t iff all elements in list1 are also included in list2, and so on. If no lists are given, or a single list is given, #t is returned.

Function: lset= elt= list1 list2 …

[SRFI-1] Returns #t if all elements in list1 are in list2, and all elements in list2 are in list1, and so on.

(lset= eq? '(b e a) '(a e b) '(e e b a)) ⇒ #t
Function: lset-adjoin elt= list elt …

[SRFI-1] Adds elt … to the set list, if each one is not already a member of list. (The order doesn’t matter).

(lset-adjoin eq? '(a b c) 'a 'e) ⇒ '(e a b c)
Function: lset-union elt= list1 …

[SRFI-1] Returns the union of the sets list1 ….

Function: lset-intersection elt= list1 list2 …

[SRFI-1] Returns a set of elements that are in every lists.

Function: lset-difference elt= list1 list2 …

[SRFI-1] Returns a set of elements that are in list1 but not in list2. In n-ary case, binary differece operation is simply folded.

Function: lset-xor elt= list1 …

[SRFI-1] Returns the exclusive-or of given sets; that is, the returned set consists of the elements that are in either list1 or list2, but not in both. In n-ary case, binary xor operation is simply folded.

Function: lset-diff+intersection elt= list1 list2 …

[SRFI-1] Returns two sets, a difference and an intersection of given sets.

Function: lset-union! elt= list …
Function: lset-intersection! elt= list1 list2 …
Function: lset-difference! elt= list1 list2 …
Function: lset-xor! elt= list1 …
Function: lset-diff+intersection! elt= list1 list2 …

[SRFI-1] Linear update variant of the corresponding procedures. The cells in the first list argument may be reused to construct the result.

Previous: , Up: List library   [Contents][Index]