本章では (rnrs lists (6)) ライブラリについて述べる。このライブラリにはリスト上の操作を行なう有用な様々手続きが含まれている。
proc は引き数をひとつ取り値をひとつ返さなければならない。 proc はリストを変更するべきではない。 find 手続きは list の要素に順に proc を適用する。 proc がある要素に真値を返した場合、 find は即座にその要素を返す。 list のすべての要素に proc が #f を返した場合、 find は #f を返す。 proc は常に find 自体と同一の動的環境で呼び出される。
(find even? ’(3 1 4 1 5 9)) ⇒ 4 (find even? ’(3 1 5 1 5 9)) ⇒ #f
実装系の義務: 実装系は list が見つかった要素まで対のつながりであるか、あるいは見つからない場合には実際にリストであることを確認しなければならない。見つかった要素を越えて対のつながりであるかどうかを確認するべきではない。実装系は上で述べたように適用により機能する存続期間についての proc に対する制約を確認しなければならない。実装系は proc を適用する前に、それが適切な引き数を取るか確認してもよい。
リストはすべて同じ長さで、 proc は n 個の引き数を取りひとつの値を返す。 proc はリスト引き数を変更するべきではない。
自然数 i = 0, 1, ... について for-all 手続きは x_i^1 ... x_i^n 対して #f が返るまで順番に proc を適用する。ここで、 x_i^j は list^j の i 番目の要素である。 proc が list1 の最後の要素以外に真値を返した場合、 for-all は k 番目の要素に proc に対して末尾呼び出しを行なう。ここで、 k は list1 の長さである。 proc が要素の集合のいずれかに #f を返した場合、 for-all はそのような proc の最初の適用の後に #f を返す。リストが空の場合、 for-all は #t を返す。
自然数 i = 0, 1, ... について for-all 手続きは x_i^1 ... x_i^n 対して真値が返るまで順番に proc を適用する。ここで、 x_i^j は list^j の i 番目の要素である。 proc が list1 の最後の要素以外に #f を返した場合、 for-all は k 番目の要素に proc に対して末尾呼び出しを行なう。ここで、 k は list1 の長さである。 proc が要素の集合のいずれかに真値を返した場合、 exists はそのような proc の最初の適用の後にその値を返す。リストが空の場合、 exists は #f を返す。
proc は常にそれぞれ for-all や exists と同一の動的環境で呼び出される。
(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
実装系の義務: 実装系はリストが戻り値を決定するのに必要な範囲への対のつながりであることを検しなければならない。これによりリスト全体を走査しなければならない場合、実装系はリストがすべて同じ長さであることを確認すべきである。そうでなければ、走査範囲を越えてリストが対のつながりであることを確認するべきではない。実装系は上で述べたように proc が適用された範囲までこの制約を検しなければならない。実装系は proc が適切な引き数を取るか適用前に確認してもよい。
proc は引き数をひとつ取り値をひとつ返す。 proc はリストを変更するべきではない。
filter 手続きは proc を list の各要素に適用して proc が真値を返した要素のリストを返す。 partition 手続きも同様に各要素に proc を適用するが、値をふたつ、ひとつは proc が真値を返したもの、もうひとつは proc が #f を返したものを返す。どちらの場合も、結果のリストの要素の順番はは入力と同じである。 proc は常に、それぞれ filter と partition と同じ動的環境で呼び出される。 filter や partition から複数回返った場合でも、以前の呼び出しの戻り値は変更されない。
(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
実装系の義務: 実装系は上で述べたように proc が適用された範囲までこの制約を検しなければならない。実装系は proc が適切な引き数を取るか適用前に確認してもよい。
リストはすべて同じ長さでなければならず、 combine は手続きでなければならない。 combine はリストの数よりもひとつ多くの引き数を取り値をひとつ返す。このときリストを変更するべきではない。 fold-left 手続きは累積値の初期値を nil として、累積値とリストの要素上で combine 手続きを左から右へ繰り返す。リストが空でない場合、 conbine はまず nil とそれぞれの最初の要素に順に適用される。戻り値は新たな累積値になり、 combine が新たな累積値とリストの次の要素に適用される。この過程がリストの終端に到達するまで繰り返され、そして累積値が返る。 combine は常に fold-left 自身と同一の動的環境で呼び出される。
(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
実装系の義務: 実装系はリストがすべて同じ長さであることを確認すべきである。実装系は上で述べたように proc が適用された範囲までこの制約を検しなければならない。実装系は proc が適切な引き数を取るか適用前に確認してもよい。
リストはすべて同じ長さでなければならず、 combine は手続きでなければならない。 combine はリストの数よりもひとつ多くの引き数を取り値をひとつ返す。このときリストを変更するべきではない。 fold-right 手続きは累積値の初期値を nil として、累積値とリストの要素上で combine 手続きを右から左へ繰り返す。リストが空でない場合、 conbine はまず nil とそれぞれの最後の要素に順に適用される。戻り値は新たな累積値になり、 combine が新たな累積値とリストの前の要素に適用される。この過程がリストの先頭に到達するまで繰り返され、そして累積値が返る。 combine は常に fold-right 自身と同一の動的環境で呼び出される。
(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
実装系の義務: 実装系はリストがすべて同じ長さであることを確認すべきである。実装系は上で述べたように proc が適用された範囲までこの制約を検しなければならない。実装系は proc が適切な引き数を取るか適用前に確認してもよい。
proc は引き数をひとつ取り値をひとつ返す。 proc は list を変更するべきではない。
これらの各手続きは与えられた条件を見たさない要素のリストを返す。 remp 手続きは proc を list の各要素に適用し、 proc が #f を返した要素のリストを返す。。 proc は常に remp 自体と同一の動的環境で呼び出される。 remove、 remv, remq 手続きは obj でない要素のリストを返す。 remq 手続きは obj とリストの要素を比較するのに eq? を使い、 remv は eqv? を使い、 remove は equal? を使う。戻り値のリストの要素の順序は入力のリストに現れたときと同一である。 remp から複数回返った場合でも以前の呼び出しの戻り値は変更されない。
(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)
実装系の義務: 実装系は上で述べたように proc が適用された範囲までこの制約を検しなければならない。実装系は proc が適切な引き数を取るか適用前に確認してもよい。
proc は引き数をひとつ取り値をひとつ返す。 proc は list を変更するべきではない。 Proc should accept one argument and return a single value. Proc should not mutate list.
これらの手続きは、その car が与えられた条件を満たしたリストの部分リストを返す。ここで、リストの部分リストは k < <リストの長さ> なるときの (list-tail list k) の返すリストである。 memp 手続きは proc が真値を返すものが見つかるまで proc を list の部分リストの car に適用する。 proc は常に memp 自体と同一の動的環境で呼び出される。 member、 memv, memq 手続きは obj の最初の出現を探す。 list が条件を満たす要素を持たない場合には #f を返す（空リストではない）。 member 手続きは obj を要素と比較するのに equal? を使い、 memv は eqv? を使い、 memq は 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)
実装系の義務: 実装系は見つかった要素以前まで list が対のつながりであることを確認し、要素が見つからなかった場合には実際にリストであることを確認しなければならない。見つかった要素より後まで対のつながりであることを確認するべきではない。実装系は上で述べたように proc が適用された範囲までこの制約を検しなければならない。実装系は proc が適切な引き数を取るか適用前に確認してもよい。
alist （連想リスト）は対のリストである。 proc は引き数をひとつ取り値をひとつ返し、 alist を変更するべきではない。
これらの手続きは alist 中で car が与えられた条件を満たす最初の対を探し、 alist をそれ以上走査せずにその対を返す。 alist 中に条件を満たす対がない場合には #f が返る。 assp てつづきは順番に proc を alist の car 部分に適用して真値を返す対を探す。 proc は常に assq 自体と同一の動的環境で呼び出される。 assoc、 assv、 assq 手続きは car に obj を持つ要素を探す。 assoc 手続きは obj と対の car を比較するのに equal? を使い、 assv は eqv? を使い、 assq は eq? を使う。
実装系の義務: 実装系は見つかった要素以前まで list が対を格納した対のつながりであることを確認し、要素が見つからなかった場合には実際に対のリストであることを確認しなければならない。見つかった要素より後まで対のつながりであることを確認するべきではない。実装系は上で述べたように proc が適用された範囲までこの制約を検しなければならない。実装系は proc が適切な引き数を取るか適用前に確認してもよい。
(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* は car が obj1、 ...、 'objn であり、 cdr が obj である、新たに割り当てられた対のつながりを返す。一引き数で呼び出された場合にはその引き数を返す。
(cons* 1 2 ’(3 4 5)) ⇒ (1 2 3 4 5) (cons* 1 2 3) ⇒ (1 2 . 3) (cons* 1) ⇒ 1