Chapter 3

List utilities

This chapter describes the (rnrs lists (6))library.

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.

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 x_i¹ ... x_iⁿ, where x_i^j is the ith element of list_j, until #f is returned. If proc returns true values for all but the last element of list₁, for-all performs a tail call of proc on the kth elements, where k is the length of list₁. 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 x_i¹ ... x_iⁿ, where x_i^j is the ith element of list_j, 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 list₁. 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.

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.

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.

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.

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.

(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.

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, without traversing list further. 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.

Rationale:   Although they are ordinarily used as predicates, memp, member, memv, memq, do not have question marks in their names because they return useful values rather than just #t or #f.

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.

(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)

If called with at least two arguments, cons* returns a freshly allocated chain of pairs whose cars are obj₁, ..., obj_n, 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