#
Chapter 3
List utilities

This chapter describes the `(rnrs lists (6))`library, which contains various useful procedures that operate on lists.

`(find proc list)` procedure

Proc should accept one argument and return a single value. Proc should not mutate list. The `find` procedure applies proc to the elements of list in order. If proc returns a true value for an element, `find` immediately returns that element. If proc returns `#f` for all elements of the list, `find` returns `#f`. Proc is always called in the same dynamic environment as `find` itself.

`(find even? ’(3 1 4 1 5 9)) ⇒ 4
(find even? ’(3 1 5 1 5 9)) ⇒ `#f`

`

Implementation responsibilities: The implementation must check that list is a chain of pairs up to the found element, or that it is indeed a list if no element is found. It should not check that it is a chain of pairs beyond the found element. The implementation must check the restrictions on proc to the extent performed by applying it as described. An implementation may check whether proc is an appropriate argument before applying it.

`(for-all proc list1 list2 `...` listn)` procedure
`(exists proc list1 list2 `...` listn)` procedure

The lists should all have the same length, and proc should accept n arguments and return a single value. Proc should not mutate the list arguments.

For natural numbers i = 0, 1, `...`, the `for-all` procedure successively applies proc to arguments xi1 `...` xin, where xij is the ith element of listj, until `#f` is returned. If proc returns true values for all but the last element of list1, `for-all` performs a tail call of proc on the kth elements, where k is the length of list1. If proc returns `#f` on any set of elements, `for-all` returns `#f` after the first such application of proc. If the lists are all empty, `for-all` returns `#t`.

For natural numbers i = 0, 1, `...`, the `exists` procedure applies proc successively to arguments xi1 `...` xin, where xij is the ith element of listj, until a true value is returned. If proc returns `#f` for all but the last elements of the lists, `exists` performs a tail call of proc on the kth elements, where k is the length of list1. If proc returns a true value on any set of elements, `exists` returns that value after the first such application of proc. If the lists are all empty, `exists` returns `#f`.

Proc is always called in the same dynamic environment as `for-all` or, respectively, `exists` itself.

`(for-all even? ’(3 1 4 1 5 9))
⇒ `#f`
(for-all even? ’(3 1 4 1 5 9 . 2))
⇒ `#f`
(for-all even? ’(2 4 14)) ⇒ `#t`
(for-all even? ’(2 4 14 . 9))
⇒ ``&assertion`` exception
(for-all (lambda (n) (and (even? n) n))
’(2 4 14))
⇒ 14
(for-all < ’(1 2 3) ’(2 3 4))
⇒ `#t`
(for-all < ’(1 2 4) ’(2 3 4))
⇒ `#f`
(exists even? ’(3 1 4 1 5 9))
⇒ `#t`
(exists even? ’(3 1 1 5 9)) ⇒ `#f`
(exists even? ’(3 1 1 5 9 . 2))
⇒ ``&assertion`` exception
(exists (lambda (n) (and (even? n) n)) ’(2 1 4 14))
⇒ 2
(exists < ’(1 2 4) ’(2 3 4)) ⇒ `#t`
(exists > ’(1 2 3) ’(2 3 4)) ⇒ `#f`

`

Implementation responsibilities: The implementation must check that the lists are chains of pairs to the extent necessary to determine the return value. If this requires traversing the lists entirely, the implementation should check that the lists all have the same length. If not, it should not check that the lists are chains of pairs beyond the traversal. The implementation must check the restrictions on proc to the extent performed by applying it as described. An implementation may check whether proc is an appropriate argument before applying it.

`(filter proc list)` procedure
`(partition proc list)` procedure

Proc should accept one argument and return a single value. Proc should not mutate list.

The `filter` procedure applies proc to each element of list and returns a list of the elements of list for which proc returned a true value. The `partition` procedure also applies proc to each element of list, but returns two values, the first one a list of the elements of list for which proc returned a true value, and the second a list of the elements of list for which proc returned `#f`. In both cases, the elements of the result list(s) are in the same order as they appear in the input list. Proc is always called in the same dynamic environment as `filter` or, respectively, `partition` itself. If multiple returns occur from `filter` or `partitions`, the return values returned by earlier returns are not mutated.

`(filter even? ’(3 1 4 1 5 9 2 6))
⇒ (4 2 6)
(partition even? ’(3 1 4 1 5 9 2 6))
⇒ (4 2 6) (3 1 1 5 9) ; two values

`

Implementation responsibilities: The implementation must check the restrictions on proc to the extent performed by applying it as described. An implementation may check whether proc is an appropriate argument before applying it.

`(fold-left combine nil list1 list2 `...`listn)` procedure

The lists should all have the same length. Combine must be a procedure. It should accept one more argument than there are lists and return a single value. It should not mutate the list arguments. The `fold-left` procedure iterates the combine procedure over an accumulator value and the elements of the lists from left to right, starting with an accumulator value of nil. More specifically, `fold-left` returns nil if the lists are empty. If they are not empty, combine is first applied to nil and the respective first elements of the lists in order. The result becomes the new accumulator value, and combine is applied to the new accumulator value and the respective next elements of the list. This step is repeated until the end of the list is reached; then the accumulator value is returned. Combine is always called in the same dynamic environment as `fold-left` itself.

`(fold-left + 0 ’(1 2 3 4 5)) ⇒ 15
(fold-left (lambda (a e) (cons e a)) ’()
’(1 2 3 4 5))
⇒ (5 4 3 2 1)
(fold-left (lambda (count x)
(if (odd? x) (+ count 1) count))
0
’(3 1 4 1 5 9 2 6 5 3))
⇒ 7
(fold-left (lambda (max-len s)
(max max-len (string-length s)))
0
’("longest" "long" "longer"))
⇒ 7
(fold-left cons ’(q) ’(a b c))
⇒ ((((q) . a) . b) . c)
(fold-left + 0 ’(1 2 3) ’(4 5 6))
⇒ 21

`

Implementation responsibilities: The implementation should check that the lists all have the same length. The implementation must check the restrictions on combine to the extent performed by applying it as described. An implementation may check whether combine is an appropriate argument before applying it.

`(fold-right combine nil list1 list2 `...`listn)` procedure

The lists should all have the same length. Combine must be a procedure. It should accept one more argument than there are lists and return a single value. Combine should not mutate the list arguments. The `fold-right` procedure iterates the combine procedure over the elements of the lists from right to left and an accumulator value, starting with an accumulator value of nil. More specifically, `fold-right` returns nil if the lists are empty. If they are not empty, combine is first applied to the respective last elements of the lists in order and nil. The result becomes the new accumulator value, and combine is applied to the respective previous elements of the lists and the new accumulator value. This step is repeated until the beginning of the list is reached; then the accumulator value is returned. Proc is always called in the same dynamic environment as `fold-right` itself.

`(fold-right + 0 ’(1 2 3 4 5))
⇒ 15
(fold-right cons ’() ’(1 2 3 4 5))
⇒ (1 2 3 4 5)
(fold-right (lambda (x l)
(if (odd? x) (cons x l) l))
’()
’(3 1 4 1 5 9 2 6 5))
⇒ (3 1 1 5 9 5)
(fold-right cons ’(q) ’(a b c))
⇒ (a b c q)
(fold-right + 0 ’(1 2 3) ’(4 5 6))
⇒ 21

`

Implementation responsibilities: The implementation should check that the lists all have the same length. The implementation must check the restrictions on combine to the extent performed by applying it as described. An implementation may check whether combine is an appropriate argument before applying it.

`(remp proc list)` procedure
`(remove obj list)` procedure
`(remv obj list)` procedure
`(remq obj list)` procedure

Proc should accept one argument and return a single value. Proc should not mutate list.

Each of these procedures returns a list of the elements of list that do not satisfy a given condition. The `remp` procedure applies proc to each element of list and returns a list of the elements of list for which proc returned `#f`. Proc is always called in the same dynamic environment as `remp` itself. The `remove`, `remv`, and `remq` procedures return a list of the elements that are not obj. The `remq` procedure uses `eq?` to compare obj with the elements of list, while `remv` uses `eqv?` and `remove` uses `equal?`. The elements of the result list are in the same order as they appear in the input list. If multiple returns occur from `remp`, the return values returned by earlier returns are not mutated.

`(remp even? ’(3 1 4 1 5 9 2 6 5))
⇒ (3 1 1 5 9 5)
(remove 1 ’(3 1 4 1 5 9 2 6 5))
⇒ (3 4 5 9 2 6 5)
(remv 1 ’(3 1 4 1 5 9 2 6 5))
⇒ (3 4 5 9 2 6 5)
(remq ’foo ’(bar foo baz)) ⇒ (bar baz)

`

Implementation responsibilities: The implementation must check the restrictions on proc to the extent performed by applying it as described. An implementation may check whether proc is an appropriate argument before applying it.

`(memp proc list)` procedure
`(member obj list)` procedure
`(memv obj list)` procedure
`(memq obj list)` procedure

Proc should accept one argument and return a single value. Proc should not mutate list.

These procedures return the first sublist of list whose car satisfies a given condition, where the sublists of lists are the lists returned by `(list-tail list k)` for k less than the length of list. The `memp` procedure applies proc to the cars of the sublists of list until it finds one for which proc returns a true value. Proc is always called in the same dynamic environment as `memp` itself. The `member`, `memv`, and `memq` procedures look for the first occurrence of obj. If list does not contain an element satisfying the condition, then `#f` (not the empty list) is returned. The `member` procedure uses `equal?` to compare obj with the elements of list, while `memv` uses `eqv?` and `memq` uses `eq?`.

`(memp even? ’(3 1 4 1 5 9 2 6 5))
⇒ (4 1 5 9 2 6 5)
(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`
(member (list ’a)
’(b (a) c)) ⇒ ((a) c)
(memq 101 ’(100 101 102)) ⇒ unspecified
(memv 101 ’(100 101 102)) ⇒ (101 102)

`

Implementation responsibilities: The implementation must check that list is a chain of pairs up to the found element, or that it is indeed a list if no element is found. It should not check that it is a chain of pairs beyond the found element. The implementation must check the restrictions on proc to the extent performed by applying it as described. An implementation may check whether proc is an appropriate argument before applying it.

`(assp proc alist)` procedure
`(assoc obj alist)` procedure
`(assv obj alist)` procedure
`(assq obj alist)` procedure

Alist (for “association list”) should be a list of pairs. Proc should accept one argument and return a single value. Proc should not mutate alist.

These procedures find the first pair in alist whose car field satisfies a given condition, and returns that pair without traversing alist further. If no pair in alist satisfies the condition, then `#f` is returned. The `assp` procedure successively applies proc to the car fields of alist and looks for a pair for which it returns a true value. Proc is always called in the same dynamic environment as `assp` itself. The `assoc`, `assv`, and `assq` procedures look for a pair that has obj as its car. The `assoc` procedure uses `equal?` to compare obj with the car fields of the pairs in alist, while `assv` uses `eqv?` and `assq` uses `eq?`.

Implementation responsibilities: The implementation must check that alist is a chain of pairs containing pairs up to the found pair, or that it is indeed a list of pairs if no element is found. It should not check that it is a chain of pairs beyond the found element. The implementation must check the restrictions on proc to the extent performed by applying it as described. An implementation may check whether proc is an appropriate argument before applying it.

`(define d ’((3 a) (1 b) (4 c)))
(assp even? d) ⇒ (4 c)
(assp odd? d) ⇒ (3 a)
(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)

`

`(cons* obj1 `...` objn obj)` procedure
`(cons* obj)` procedure

If called with at least two arguments, `cons*` returns a freshly allocated chain of pairs whose cars are obj1, `...`, objn, and whose last cdr is obj. If called with only one argument, `cons*` returns that argument.

`(cons* 1 2 ’(3 4 5)) ⇒ (1 2 3 4 5)
(cons* 1 2 3) ⇒ (1 2 . 3)
(cons* 1) ⇒ 1

`