R5RS Scheme はリスト処理のためのユーティリティが貧弱であり、ポータブルなコードを書くときの問題となっている。 この SRFI では、首尾一貫した包括的なリスト処理手続きを提案する。また、この仕様の参照実装を与える。参照実装は次の特徴をもつ。
R4RS/R5RS Scheme で与えられる基本的なリスト処理およびペア処理は、十分といえるには程遠いものである。 そこで与えられる手続きはごく少数で基本的なものに限られるため、ほとんどの実装系ではリスト フィルタ関数や左畳み込み演算子のような追加のユーティリティを提供している。 しかし、当然のことながら、これにより非互換性が発生する。 Scheme 実装系が異なれば手続きの集合も異なるからである。
私はリスト処理のためのフル機能の手続きライブラリを設計した。 ライブラリを統合するにあたり、私は可能な限り多くの Scheme 実装系を参照した (これらの実装系のうちのいくつかについては、私はかなりの使用経験がある)。 Chez Scheme は除外した。オンライン マニュアルを見つけることができなかったからである。 しかし、大きなフル機能の Scheme 実装系はほとんど網羅した。 私が参照したリスト処理システムの一覧を以下に示す。
結果として、ここで提案するライブラリはかなり豊かなものとなった。
最初の設計フェーズが終了した後、このライブラリは SRFI メーリングリストにおいて数ヶ月間議論され、そこで得られたアイデアと提案をもとに変更がなされた。
私はこの API の設計と並行して参照実装のコーディングも行った。 私はそのソースコードをネット上に置き、障害のないオープンな著作権のもとに公開した。 以下に参照実装に関するいくつかの注記を示す。
error 手続き
values および簡単な receive マクロ
:optional および let-optionals マクロ
check-arg 手続き
filter! のような副作用を与える手続きでは、
不必要で冗長な set-cdr! は使用していない。
これは世代管理 GC の書き込みバリアや高速なプロセッサのストア バッファにおいてスラッシングを引き起こす。
関数は、可能であれば入力パラメータから最長共通末尾 (longest common tails) を再利用して結果を構築する。
再帰よりも定数容量の繰り返しを使用する。
一時的な中間データ構造を cons するよりも、ローカル再帰を使用する。
このことは、この実装が個別の Scheme 実装系に対して最適化されていることを意味するのではない。 参照実装を最適化するための方法はコメントに記してある。
要するに、実装者や通常のプログラマが、できるだけ労せずしてこのライブラリを採用し、望ましい結果を得ることができるように書いたのである。
list-lib パッケージにより提供される手続きの一覧を以下に示す。 R5RS 手続きは 太字 で記した。 また、拡張された R5RS 手続きは 太字の斜体 で記した。
cons list xcons cons* make-list list-tabulate list-copy circular-list iota
pair? null? proper-list? circular-list? dotted-list? not-pair? null-list? list=
car cdr ... cddadr cddddr list-ref first second third fourth fifth sixth seventh eighth ninth tenth car+cdr take drop take-right drop-right take! drop-right! split-at split-at! last last-pair
length length+ append concatenate reverse append! concatenate! reverse! append-reverse append-reverse! zip unzip1 unzip2 unzip3 unzip4 unzip5 count
map for-each fold unfold pair-fold reduce fold-right unfold-right pair-fold-right reduce-right append-map append-map! map! pair-for-each filter-map map-in-order
filter partition remove filter! partition! remove!
member memq memv find find-tail any every list-index take-while drop-while take-while! span break span! break!
delete delete-duplicates delete! delete-duplicates!
assoc assq assv alist-cons alist-copy alist-delete alist-delete!
lset<= lset= lset-adjoin lset-union lset-union! lset-intersection lset-intersection! lset-difference lset-difference! lset-xor lset-xor! lset-diff+intersection lset-diff+intersection!
set-car! set-cdr!
このライブラリでは、R4RS/R5RS の 4 つのリスト処理手続きが後方互換となるように拡張される。
map for-each
| (等しくない長さをもつ複数のリストを受け付けるように拡張) |
member assoc
| (比較手続きをオプション引数として受け付けるように拡張) |
次の R4RS/R5RS のリスト処理およびペア処理手続きも list-lib に含まれており、R5RS の定義と同じである。
cons pair? null? car cdr ... cdddar cddddr set-car! set-cdr! list append reverse length list-ref memq memv assq assv
R4RS/R5RS の残り 2 つのリスト処理手続きは、このライブラリには含まれない。
list-tail
|
(drop に名前が変更される)
|
list?
|
(proper-list?,
circular-list?,
dotted-list? を見よ)
|
このライブラリでは、いくつかの一般的な判断基準を設計の指針とした。
「破壊的な」(私の言い方では「線形更新な」) 手続きは、 リスト引数の cons セルを変更して再利用することは必須ではない。 再利用することは許されるが、必須ではない。 (私の書いた参照実装ではリスト引数を再利用している。)
filter や delete のようなリストのフィルタ手続きは、リストの順序を変更しない。
返されるリストに現れる要素は、引数のリストに現れる要素と同じ順序になる。
この仕様は実装を難しくするが、リストを使用する多くの場面では順序が重要になってくるので、これは望ましい機能であろう。
(特に、連想リストの順序を変更してしまうことは間違いなく悪い考えである。)
逆に、リスト フィルタ手続きの参照実装では、 引数のリストと返り値のリストが最長共通末尾を共有するが、 このことは仕様としては規定しない。
リストは (ベクタなどと違って) 本質的にシーケンシャルなデータ構造であるので、
find, find-tail, for-each, any, every のようなリスト検査関数は、引数のリストを左から右に横断するものとする。
しかしながら、list-tabulateappend-map, append-map!, map!, pair-for-each, filter-map, map-in-order)
においては、引数の手続きを値に適用する順序は定めていない。
述語が真値を返す場合、可能な限り有用な値を返すものとする。
したがって、any はその述語により生成された真値を返し、
every はリスト引数の最後の要素に述語引数を適用して得られる真値を返す。
各関数は、それが意味をなすものであれば、 純粋な形式と線形更新な (潜在的に破壊的な) 形式で提供される。
Scheme 組み込みの同値関数を特別扱いすることはしない。
デフォルトで eq?、eqv?、equal?
を使用する関数であっても、ユーザー定義の同値関数を使用できるように配慮した。
適切な設計というものは後方互換性よりも価値があるが、他の条件が同じであるならば可能な限り既存のリスト処理ライブラリと後方互換であるように努め、古いコードがこのライブラリを使用して実行できるように移植する作業が容易になるように考慮した。 名前とセマンティクスは、そのほとんどが現在流布している多くの Scheme 実装系と折り合うようになっている。 互換性のない部分については、手続きの解説において指摘しておいた。
以下の手続きは「シーケンス汎用」ではない。 すなわち、手続きはベクタとリストの両方に適用されるものではなく、リストに固有な手続きである。 私はこのライブラリが簡素で焦点を絞ったものであることを望んだのだ。
Scheme の既存のリスト処理ユーティリティに合わせるため、手続きの名前に接頭辞 "list-" をつけることはしなかった。
手続きの名前をつける際、アクション名の前に型名をつけるという、Scheme に一般的な慣習に従った (vector-length, string-ref など)。
したがって、list-copy や pair-for-each のように命名し、より流暢であるが慣習に合わない copy-list や for-each-pair という名前は使用しない。
手続き名は基本的な語彙素から構成するという、標準的で一貫性のある名前付け規則に概ね従うことにする。
このライブラリの多くの手続きでは、「純粋な」（pure）手続きと、「線形更新な」（linear update）手続きの双方が用意されている。
「純粋な」手続きには副作用がなく、特にその引数を変更することは決してない。
「線形更新な」手続きは、返り値を構築するためにその引数に副作用を与えてもよい (しかし副作用を与えなくてもよい)。
「線形更新な」手続きは、通常その名前の最後に感嘆符がつく。
たとえば (append! list1 list2) は、単に set-cdr! を使用して list1 の最後のペアの cdr が list2 を指すように変更することで返り値を構築し、その list1 を返すように実装できる。
(ただし list1 は空リストではないものとする。空リストの場合は単に list2 を返せばよい)。
しかし、append! は純粋な append 操作として定義してもよく、この定義は append! の有効な定義として認められる。
(define append! append)
この理由から、このような手続きを「破壊的な」(destructive) と呼ぶことはしない。 破壊的であることは必ずしも要求しないからである。 これらは潜在的に破壊的なだけである。
このことが何を意味するかといえば、線形更新な手続きは「死んだ」値 (プログラム中で二度と使われない値) に対してのみ適用できるということである。 なぜなら、線形更新な手続きに渡された値は、手続き呼出し後は変更されていないかも知れないし変更されているかも知れないので、その値を信頼することはできないからである。
「線形更新」という用語における「線形」という言葉は、「線形時間」や「線形容量」や他の「n の定数倍」という種類の意味を表すのではない。 これは、変数 1 つにつきちょうど 1 つの参照しかもてないシステムを記述するときに、理論家や関数プログラマが使う気の利いた用語である。 これは、変数に束縛された値が他の変数に束縛されていないことを保証する。 そのため、変数参照において変数を使用すると、その変数は「使い果たされる」のである。 他の何ものもその値へのポインタを保持していないということが確かであれば、 システム プリミティブはその引数に副作用を与えながらも純粋に関数的な結果を返すことができる。
このライブラリの文脈における「線形更新」では、手続きに渡される値に対して他の何ものも有効な参照をしていないことをプログラマが知っている必要がある。 線形更新な手続きに値を渡した後は、その値を参照する古いポインタの振る舞いは不確定になる。 要するに、Scheme 実装系に対してデータ構造を変更するように許可を与え、その変更処理において値を破壊するか破壊しないかについてはどちらでもよいと宣言しているのである。
手続きに渡した値が実際に「線形」であるかどうかについて Scheme は何も検査してくれないので、プログラマがそれを確認していないといけない。 あるいは、安全策をとって ! のつかない手続きのみを使用するという方法もある。 どんなに高速に計算したところで、間違った値を得るのであれば意味がないだろうから。
一般的に使われている「破壊的な」という概念を使わずに、「線形更新」の概念を定義して使うことに何の益があるのかと問われるかもしれない。 まず第一に、破壊的なリスト処理手続きは、ほとんどの場合線形更新な方法で使用されているということに注意していただきたい。 その理由の一つとして、副作用を与えることのできない空リストに対しても処理を行う必要があるからである。 つまり、このような破壊的な手続きは純粋に副作用を与えるのではなく、返り値を返す必要があるのである。 第二に、線形更新な手続きを使用して書かれたコードは、その線形更新な手続きの実装を純粋な実装に変更するだけで、Scheme の純粋に関数的なサブセットに移植できるという点が挙げられる。 第三に、破壊的な副作用を使用すると、その操作を並列化することができなくなるという点がある。 コード中で破壊的な操作を使用することが困難な場所というのは、たいていの場合プログラマが並列化コンパイラに並列化してほしいと望むコード部分、つまり、効率が非常に重要になるアルゴリズムの核の部分なのだ。 しかし線形更新な操作は容易に並列化することができる。 線形更新という概念を仕様に取り込むことで、このような貴重な実装テクニックを視野に含めることができる。 このリスト ライブラリは低レベルで基本的な手続きを提供することを目的としているので、並列処理を行う実装系も排除したくはなかったのである。
このライブラリに含まれる線形更新な手続きを以下に示す。
take! drop-right! split-at!
append! concatenate! reverse! append-reverse!
append-map! map!
filter! partition! remove!
take-while! span! break!
delete! alist-delete! delete-duplicates!
lset-adjoin! lset-union! lset-intersection!
lset-difference! lset-xor! lset-diff+intersection!
C 言語に文字列型というものはないのと同じように、厳密に言えば Scheme にはリスト型というものはない。 正確には Scheme には 2 要素タプル型 (binary-tuple type) があり、そこから 2 分木を構築できるのである。 そして、その 2 分木をリストとして解釈する方法が Scheme に備わっている。 Scheme がこのタプルに副作用を施すと、長さ制限のないリストや深さ制限のないツリー (つまり循環データ構造体) が生ずる可能性があるという複雑な事情が起きてくる。
しかしながら、Scheme の値集合をある種のリストとして分類する方法があり、すべての Scheme の値は以下のいずれかに分類される。
(a b c)()(32)(a b c . d)(x . y)42george長さ 0 のドット リストは、空リストおよびペア以外のすべての値を意味することに注意せよ。
この分類は述語 proper-list?, dotted-list?, circular-list? により判定できる。
ドット リストは通常は使用されない。
多くの Scheme プログラマは、ドット リストは Scheme に真のリスト型が欠けていることから生ずる醜い人工物だと考えている。
しかし、ドット リストは (lambda (x y . rest) ...) のような n 項ラムダ関数の残余引数の処理において顕著な働きをする。
ドット リストは list-lib では完全にはサポートされていない。 ほとんどの手続きは真正リスト (有限で nil 終端のリスト) に対してのみ定義されている。 循環リストやドット リストも扱うことのできる手続きについては、特別に言及している。 この設計は、手続きに渡すことのできる引数に制限をかけることになるが、プログラマが不注意でリストを渡すべき引数にスカラ値を渡しても、その手続きがエラーを捕捉できるという利点がある。 たとえば、手続き呼び出しで引数の位置を交換してしまった場合などである。
「～はエラーである」という文は、単に「～をしてはいけない」という意味であることに注意せよ。
このことは、仕様を満たす実装であっても、「エラーである」場合にたとえば何らかの例外を起動することによりそのエラーを捕捉できるという保証を与えない。
残念ながら、R5RS Scheme は
car や cdr のような基本的な演算子に対してさえこれより堅固な保証を与えてはいない。
そのため、このライブラリの手続きにそれ以上のエラー処理を要求する必要はないだろう。
関連する R5RS のセクションを以下に引用する。
エラーの状況が起きた場合、このレポートでは「エラーが発生する」 (an error is signalled) という文句によって、 実装系がそれを検出しエラーを報告しなければならないことを表現する。 エラーに関する議論においてそのような言い回しが現れない場合、 実装系はエラーを検出したりエラーを報告したりする必要はないが、 そうすることを推奨する。 実装系が検出する必要のないエラー状況に対しては、 通常は単に「エラーである」(is an error) という文句を使用する。
たとえば、手続きが処理することを明示的には規定されていない引数を渡した場合、 そのような引数のエラーはこのレポートではほとんど言及されないが、 それはエラーである。実装系は手続きの引数を拡張し、 そのような引数の指定を許可してもよい。
以下の項目はこのライブラリには含まれない。
これらに関しては、それ自身の SRFI 仕様が与えられるべきである。
モジュール システムやパッケージ システムをもつ Scheme システムにおいては、 以下の手続きは "list-lib" というモジュール名に含まれること。 以下で述べるテンプレートでは、手続きの引数は次の慣習に従うものとする。
| list | 真正の (有限で nil 終端の) リスト |
|---|---|
| clist | 真正リストまたは循環リスト |
| flist | 有限の (真正のまたはドットの) リスト |
| pair | ペア |
| x, y, d, a | 任意の値 |
| object, value | 任意の値 |
| n, i | 自然数 (0 以上の整数) |
| proc | 手続き |
| pred | ブール値を返す手続き |
| = | 2 つの引数をとりブール値を返す手続き |
循環リストやドット リストを、そのような引数をとらない手続きに渡すことはエラーである。
cons a d -> pair
eqv? の意味で)、
既存のどのオブジェクトとも異なることが保証されている。
(cons 'a '()) => (a)
(cons '(a) '(b c d)) => ((a) b c d)
(cons "a" '(b c)) => ("a" b c)
(cons 'a 3) => (a . 3)
(cons '(a b) 'c) => ((a b) . c)
list object ... -> list
(list 'a (+ 3 4) 'c) => (a 7 c) (list) => ()
xcons d a -> pair
(lambda (d a) (cons a d))高階の手続きの引数として渡すためのユーティリティ。
(xcons '(b c) 'a) => (a b c)手続き名は "eXchanged CONS" を意味する。
cons* elt1 elt2 ... -> object
list に似ているが、最後の引数は構築されたリストの末尾になり、次の値を返す。
(cons elt1 (cons elt2 (cons ... eltn)))
list* という名前であり、
Scheme 実装系の約半分でもそう呼ばれている。
Scheme 実装系の残りの半分では、cons* と呼ばれている。
(cons* 1 2 3 4) => (1 2 3 . 4) (cons* 1) => 1
make-list n [fill] -> list
(make-list 4 'c) => (c c c c)
list-tabulate n init-proc -> list
(init-proc i) によって生成される。
init-proc がこれらのインデックスに適用される順序については、何も保証されない。
(list-tabulate 4 values) => (0 1 2 3)
list-copy flist -> flist
circular-list elt1 elt2 ... -> list
(circular-list 'z 'q) => (z q z q z q ...)
iota count [start step] -> list
(start start+step ... start+(count-1)*step)引数 start と step のデフォルトはそれぞれ 0 と 1 である。 この手続きの名前は APL のプリミティブから拝借した。
(iota 5) => (0 1 2 3 4) (iota 5 0 -0.1) => (0 -0.1 -0.2 -0.3 -0.4)
ノート: 述語 proper-list?, circular-list?, dotted-list? は、Scheme の任意の値を排他的に分類する。
proper-list? x -> boolean
空リストは真正リストである。 ペアの cdr が真正リストであれば、そのペアも真正リストである。
<proper-list> ::= () (Empty proper list)
| (cons <x> <proper-list>) (Proper-list pair)
この定義規則からは循環リストは導出されないことに注意せよ。
この関数は、循環リストに対しては偽を返さなければならない。
nil 終端リストは R5RS と Common Lisp では「真正な」(proper) リストと呼ばれる。 「真正」の対義語は「非真正」(improper) である。
R5RS では、
この関数を変数 list? に束縛する。
(not (proper-list? x)) = (or (dotted-list? x) (circular-list? x))
circular-list? x -> boolean
用語について: 「循環」の対義語は「有限」である。
(not (circular-list? x)) = (or (proper-list? x) (dotted-list? x))
dotted-list? x -> boolean
(not (dotted-list? x)) = (or (proper-list? x) (circular-list? x))
pair? object -> boolean
(pair? '(a . b)) => #t (pair? '(a b c)) => #t (pair? '()) => #f (pair? '#(a b)) => #f (pair? 7) => #f (pair? 'a) => #f
null? object -> boolean
null-list? list -> boolean
not-pair? x -> boolean
(lambda (x) (not (pair? x)))有限リスト (真正リストおよびドット リスト) を処理するリスト処理手続きの終了条件として使用すると便利である。
list= elt= list1 ... -> boolean
(elt= a b)
という形で呼び出される。
n 個のリストを引数にとる場合、
各 listi は listi+1 と比較される
(たとえば、list1 を他のすべての listi
(i>1) と比較するということはしない)。
リスト引数を 1 つも指定しない場合、list= は単に真を返す。
真正リスト以外の値に list= を適用することはエラーである。
循環リストをサポートするように実装を拡張してもよいが、
ドット リストをサポートするように拡張することはできないことに注意せよ。
リスト終端子を比較するための同値手続きを指定する方法がないからである。
要素に対して elt= 手続きが適用される順序は規定しない。
たとえば、list= を 3 つのリスト
A、B、C に適用する場合、
最初に A と B を完全に比較し、その後で
B と C を比較するかもしれないし、あるいは、
最初に A と B の 1 つめの要素を比較し、
次に B と C の 1 つめの要素を比較し、
続いて A と B の 2 つめの要素を比較し (以下同様)、
という順序になるかもしれない。
同値手続きは eq? と整合性を持たなければならない。
つまり、次が成り立たなければならない。
(eq? x y) => (elt= x y).
eq? の意味で同値なリストは、常に list=
でも同値になるということである。
実装によっては、この事実を利用して要素比較の省略をしてもよい。
(list= eq?) => #t ; 自明なケース (list= eq? '(a)) => #t
car pair -> value
cdr pair -> value
(car '(a b c)) => a (cdr '(a b c)) => (b c) (car '((a) b c d)) => (a) (cdr '((a) b c d)) => (b c d) (car '(1 . 2)) => 1 (cdr '(1 . 2)) => 2 (car '()) => *error* (cdr '()) => *error*
caar pair -> value
cadr pair -> value
:
cdddar pair -> value
cddddr pair -> value
car と cdr の合成である。
たとえば、caddr は次のように定義できる。
(define caddr (lambda (x) (car (cdr (cdr x))))).深さ 4 までの任意の合成手続きが提供される。 手続きは全部で 28 個である。
list-ref clist i -> value
(drop clist i) の car に等しい)。
i >= n (n は clist の長さ)
を指定するとエラーである。
(list-ref '(a b c d) 2) => c
first pair -> object
second pair -> object
third pair -> object
fourth pair -> object
fifth pair -> object
sixth pair -> object
seventh pair -> object
eighth pair -> object
ninth pair -> object
tenth pair -> object
car, cadr, caddr, ... の同義語。
(third '(a b c d e)) => c
car+cdr pair -> [x y]
(lambda (p) (values (car p) (cdr p)))もちろん、コンパイラによりもっと効率的に実装できるだろう。
take x i -> list
drop x i -> object
take は、リスト x の最初の i 個の要素を返す。drop は、リスト x の最初の i 個の要素以外の要素を返す。
(take '(a b c d e) 2) => (a b) (drop '(a b c d e) 2) => (c d e)x は任意の値でよい。真正リスト、循環リスト、ドット リストのいずれでもよい。
(take '(1 2 3 . d) 2) => (1 2) (drop '(1 2 3 . d) 2) => (3 . d) (take '(1 2 3 . d) 3) => (1 2 3) (drop '(1 2 3 . d) 3) => di が有効な値であれば、
take と drop
で分割されたリストは append で復元できる。
(append (take x i) (drop x i)) = x
drop は x に cdr を i 回適用する操作と正確に一致する。
したがって、返される値は x と末尾を共有する。
引数のリストが長さ 0 でなければ、
take は新しく割り当てられたリストを返すことが保証されている。
このことは、(take lis (length lis)) のようにリスト全体を返す場合でも当てはまる。
take-right flist i -> object
drop-right flist i -> list
take-right は flist の最後の i 個の要素を返す。drop-right は flist の最後の i 個の要素以外の要素を返す。
(take-right '(a b c d e) 2) => (d e) (drop-right '(a b c d e) 2) => (a b c)返されるリストは、引数リストと末尾を共有するかもしれないし、共有しないかもしれない。
flist は任意の有限リスト (真正リストまたはドット リスト) が許される。
(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)i が有効な値であれば、
take-right と drop-right
で分割されたリストは append で復元できる。
(append (take flist i) (drop flist i)) = flist
take-right の返り値は、flist と末尾を共有することが保証されている。
引数のリストが長さ 0 でなければ、
drop-right は新しく割り当てられたリストを返すことが保証されている。
このことは、(drop-right lis 0) のようにリスト全体を返す場合でも当てはまる。
take! x i -> list
drop-right! flist i -> list
take! と drop-right! は take と
drop-right を線形更新な形で実装したものである。
この手続きがリスト引数を変更して結果を返すことは許可されるが要求はされない。
x が循環リストの場合、take!
は期待されるリストよりも短いリストを返す場合がある。
(take! (circular-list 1 3 5) 8) => (1 3) (take! (circular-list 1 3 5) 8) => (1 3 5 1 3 5 1 3)
split-at x i -> [list object]
split-at! x i -> [list object]
split-at はリスト x をインデックス i で分割し、
最初の i 個の要素のリストと、残りの末尾を返す。
これは以下の式に等価である。
(values (take x i) (drop x i))
split-at! は線形更新な形で実装したものである。
この手続きがリスト引数を変更して結果を返すことは許可されるが要求はされない。
(split-at '(a b c d e f g h) 3) =>
(a b c)
(d e f g h)
last pair -> object
last-pair pair -> pair
last は、空でない有限リスト pair の最後の要素を返す。
last-pair は、 空でない有限リスト pair の最後のペアを返す。
(last '(a b c)) => c (last-pair '(a b c)) => (c)
length list -> integer
length+ clist -> integer or #f
length と length+ はともに引数の長さを返す。
length に真正リスト (有限で nil 終端のリスト)
以外のリストを渡すことはエラーである。
つまり、length を循環リストに適用すると、
その実装は無限に発散するか、またはエラーが発生する。
一方 length+ は循環リストに適用すると #f を返す。
真正リストが非負の長さ n をもつ場合、
cdr を n 回適用すると空リストになる。
append list1 ... -> list
append! list1 ... -> list
append は、list1
の要素に他のリスト引数の要素を加えたリストを返す。
(append '(x) '(y)) => (x y) (append '(a) '(b c d)) => (a b c d) (append '(a (b)) '((c))) => (a (b) (c))結果のリストは常に新しく割り当てられたリストであるが、 最後の listi 引数と構造を共有する。 この最後の引数はどのような値でもよく、それが真正リストでなければ非真正リストを返す。 最後の引数以外の引数は真正リストでなければならない。
(append '(a b) '(c . d)) => (a b c . d) (append '() 'a) => a (append '(x y)) => (x y) (append) => ()
append! は append を線形更新な形で実装したものである。
引数のリストの cons セルを変更して結果のリストを構築することは許可されるが要求されてはいない。
最後の引数は決して変更されない。
結果のリストは最後の引数を共有する。
concatenate list-of-lists -> value
concatenate! list-of-lists -> value
concatenate は次の値を返す。
(apply append list-of-lists)あるいは、これに等価な次の値を返す。
(reduce-right append '() list-of-lists)
concatenate! は線形更新な形で実装したもので、
append ではなく append! を使用して実装している。
Scheme 実装系の中には、n 個の引数をとる手続きに対して、
特定の個数 (たとえば 64) 以上の引数を渡すことをサポートしていないものがある。
そのような実装系においては、長いリストに対して (apply append ...)
を計算すると誤った動作をするが、しかし concatenate
は何も起こらなかったように振舞う場合がある。
append および append! と同じように、
リスト引数の最後の要素には任意の値が許される。
reverse list -> list
reverse! list -> list
reverse は list
の要素を逆順に並べたリストを新しく割り当てて返す。
(reverse '(a b c)) => (c b a)
(reverse '(a (b c) d (e (f))))
=> ((e (f)) d (b c) a)
reverse! は reverse を線形更新な形で実装したものである。
引数の cons セルを変更して反転したリストを構築することは許可されるが要求されてはいない。
append-reverse rev-head tail -> list
append-reverse! rev-head tail -> list
append-reverse は
(append (reverse rev-head) tail) を返す。
この関数が用意されているのは、この操作がよく使われるからである。
リストを反転して別のリストの前に追加するというこの操作が、リスト処理ではよく使われることがある。
この関数の実装は、単純な手続きの合成よりもかなり効率的である。
(しかし、反転の後で繰り返しを行うというこのパターンは、
しばしば再帰により書き換えることができ、
reverse や append-reverse を省くことができる。
この場合、一時的な中間ストレージはヒープからスタックに移ることになり、
通常はキャッシュ ローカル性やストレージ回収の面で効率がよい。)
append-reverse! は線形更新な形の実装を与える。
rev-head の cons セルを変更して結果のリストを構築することは許可されるが要求はされない。
zip clist1 clist2 ... -> list
(lambda lists (apply map list lists))
zip に n 個のリストを渡すと、
その中で最小のリストの長さをもつリストを返す。
返されるリストの要素は、引数のリストの対応する要素から構成される
n 要素のリストである。
(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))
引数のリストのうち、少なくとも 1 つは有限でなければならない。
(zip '(3 1 4 1) (circular-list #f #t))
=> ((3 #f) (1 #t) (4 #f) (1 #t))
unzip1 list -> list
unzip2 list -> [list list]
unzip3 list -> [list list list]
unzip4 list -> [list list list list]
unzip5 list -> [list list list list list]
unzip1 はリストのリストを引数にとる。
各リスト少なくとも 1 つの要素を含まなければならず、
その要素の最初の要素からなるリストを返す。
つまり、(map car lists) を返す。
unzip2 はリストのリストを引数にとる。
各リストは少なくとも 2 つの要素を含まなければならず、
1 つめの要素のリストおよび 2 つめの要素のリスト、という 2 つの値を返す。
unzip3 は最初の 3 つの要素に対して同じ処理を行い、
他の手続きも同様である。
(unzip2 '((1 one) (2 two) (3 three))) =>
(1 2 3)
(one two three)
count pred clist1 clist2 -> integer
count は「繰り返し処理」を行う。
すなわち、左から右の順序で pred を list の要素に適用することが保証されている。
最も短いリストの要素が尽きると、カウントは終了する。
(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少なくとも 1 つのリスト引数は有限でなければならない。
(count < '(3 1 4 1) (circular-list 1 10)) => 2
fold kons knil clist1 clist2 ... -> value
まず、リスト引数が 1 つの場合を考えてみる。 clist1 = (e1 e2 ... en) とすると、この手続きは次の値を返す。
(kons en ... (kons e2 (kons e1 knil)) ... )
(fold kons knil lis) = (fold kons (kons (car lis) knil) (cdr lis)) (fold kons knil '()) = knil例:
(fold + 0 lis) ; LIS の要素を合計する
(fold cons '() lis) ; LIS を反転する
(fold cons tail rev-head) ; APPEND-REVERSE を参照せよ
;; LIS 内のシンボルの個数
(fold (lambda (x count) (if (symbol? x) (+ count 1) count))
0
lis)
;; LIS 内の最長の文字列の長さ
(fold (lambda (s max-len) (max max-len (string-length s)))
0
lis)
n 個のリスト引数を指定する場合、kons 関数は
n+1 個の引数をとらなければならない。
各リストからの要素を 1 つづつと、畳み込みの「種」(最初は knil) を引数にとる。
畳み込みは最も短いリストの要素が尽きたときに終了する。
(fold cons* '() '(a b c) '(1 2 3 4 5)) => (c 3 b 2 a 1)少なくとも 1 つのリスト引数は有限でなければならない。
fold-right kons knil clist1 clist2 ... -> value
まず、リスト引数が 1 つの場合を考えてみる。
If clist1 = (e1 e2 ... en) とすると、
この手続きは次の値を返す。
(kons e1 (kons e2 ... (kons en knil)))
(fold-right kons knil lis) = (kons (car lis) (fold-right kons knil (cdr lis))) (fold-right kons knil '()) = knil例:
(fold-right cons '() lis) ; LIS をコピーする ;; LIS から偶数を抽出する (fold-right (lambda (x l) (if (even? x) (cons x l) l)) '() lis))n 個のリスト引数を指定する場合、kons 関数は n+1 個の引数をとらなければならない。各リストから要素を 1 つづつと、 畳み込みの「種」(最初は knil) を引数にとる。 畳み込みは最も短いリストの要素が尽きたときに終了する。
(fold-right cons* '() '(a b c) '(1 2 3 4 5)) => (a 1 b 2 c 3)少なくとも 1 つのリスト引数は有限でなければならない。
pair-fold kons knil clist1 clist2 ... -> value
fold に同様だが、kons
は後続の要素に適用されるのではなく、後続のサブリストに適用される。
つまり、kons はリストを構成する各ペアに対して適用され、
次の (末尾) 再帰に従う。
(pair-fold kons knil lis) = (let ((tail (cdr lis)))
(pair-fold kons (kons lis knil) tail))
(pair-fold kons knil '()) = knil
有限リストに対しては、kons がペアに set-cdr!
を施しても実行順序は変更されない。
例:
;;; 破壊的にリストを反転する (pair-fold (lambda (pair tail) (set-cdr! pair tail) pair) '() lis))少なくとも 1 つのリスト引数は有限でなければならない。
pair-fold-right kons knil clist1 clist2 ... -> value
pair-fold と fold の間と同様な関係が
この手続きと fold-right の間に成り立つ。
次のような再帰に従う。
(pair-fold-right kons knil lis) =
(kons lis (pair-fold-right kons knil (cdr lis)))
(pair-fold-right kons knil '()) = knil
例:
(pair-fold-right cons '() '(a b c)) => ((a b c) (b c) (c))少なくとも 1 つのリスト引数は有限でなければならない。
reduce f ridentity list -> value
reduce は fold の変種である。
ridentity は手続き f の右単位元 (right identity) である。 つまり、f の引数として可能な任意の値 x に対して次を満たす。
(f x ridentity) = x
reduce は次のように定義される。
(fold f (car list) (cdr list)).
(fold f ridentity list)
を計算する。
ridentity は空リストに対してのみ使用されることに注意せよ。
reduce が使用される場面としては、
手続き f のコストが高く、
fold が list の先頭要素と単位元に対して f
を適用して同じ値を返すという冗長性を回避したい場合である。
たとえば、f がディレクトリ内のファイルを検索したり
データベース クエリを発行したりする処理を含む場合、このことが重要になる。
しかし一般には、reduce よりも fold のほうがよく使われる。
(fold の定義で示した例を考えてみるとよい。
fold 関数の 5 つの使用例のうち 1 つだけが右単位元を使用している。
他の 4 つの例は reduce では実現できないだろう)。
ノート: MIT Scheme と Haskell では
reduce および fold 関数の
F の引数の順序が反対である。
;; 非負整数のリストの最大値 (reduce max 0 nums) ; すなわち (apply max 0 nums)
reduce-right f ridentity list -> value
reduce-right は reduce の fold-right のような変種である。
これは次のように定義される。
(reduce-right f ridentity '()) = ridentity
(reduce-right f ridentity '(e1)) = (f e1 ridentity) = e1
(reduce-right f ridentity '(e1 e2 ...)) =
(f e1 (reduce f ridentity (e2 ...)))
言い換えると、
(fold-right f ridentity list)
を計算する。
;; 一連のリストをアペンドする。 ;; つまり、(apply append list-of-lists) を計算する。 (reduce-right append '() list-of-lists)
unfold p f g seed [tail-gen] -> list
unfold は次のような再帰により定義される。
(unfold p f g seed) =
(if (p seed) (tail-gen seed)
(cons (f seed)
(unfold p f g (g seed))))
(lambda (x) '()) である。
言い換えると、g はシード値のシーケンスを生成する。
fold-right が基本的な再帰的リスト コンシューマであるのと同様に、
unfold は基本的な再帰的リスト コンストラクタである。
関数プログラミングの初心者にとっては unfold
は少々抽象的に感じられるかもしれないが、
この手続きは様々な方法で使用することができる。
;; 2 乗のリスト 1^2 ... 10^2
(unfold (lambda (x) (> x 10))
(lambda (x) (* x x))
(lambda (x) (+ x 1))
1)
(unfold null-list? car cdr lis) ; 真正リストをコピー
;; カレント入力ポートを読み込んで、値のリストを生成する。
(unfold eof-object? values (lambda (x) (read)) (read))
;; 非真正リストである可能性があるリストをコピーする
(unfold not-pair? car cdr lis
values)
;; 先頭を末尾にアペンドする。
(unfold null-list? car cdr head
(lambda (x) tail))
馴れた関数プログラマであれば、
fold-right と unfold
はある意味で逆操作であることを指摘するだろう。
つまり、手続き knull?, kar,
kdr, kons, knil
を次の式を満たすように定義するとしよう。
(kons (kar x) (kdr x)) = x
かつ
(knull? knil) = #t
(fold-right kons knil (unfold knull? kar kdr x)) = x
(unfold knull? kar kdr (fold-right kons knil x)) = x.
unfold-right p f g seed [tail] -> list
unfold-right は次のループによりリストを構築する。
(let lp ((seed seed) (lis tail))
(if (p seed) lis
(lp (g seed)
(cons (f seed) lis))))
'() 。
言い換えると、g はシード値のシーケンスを生成する。
fold が基本的な反復的リスト コンシューマであるのと同様に、
unfold-right は基本的な反復的リスト コンストラクタである。
関数プログラミングの初心者にとっては unfold-right
は少々抽象的に感じられるかもしれないが、
この手続きは様々な方法で使用することができる。
;; 2 乗のリスト 1^2 ... 10^2
(unfold-right zero?
(lambda (x) (* x x))
(lambda (x) (- x 1))
10)
;; 真正リストを反転する
(unfold-right null-list? car cdr lis)
;; カレント入力ポートを読み込んで、値のリストを生成する
(unfold-right eof-object? values (lambda (x) (read)) (read))
;; (append-reverse rev-head tail)
(unfold-right null-list? car cdr rev-head tail)
馴れた関数プログラマであれば fold と unfold-right
はある意味で逆操作であることを指摘するだろう。
つまり、手続き knull?, kar,
kdr, kons, knil
を次の式を満たすように定義するとしよう。
(kons (kar x) (kdr x)) = x
かつ
(knull? knil) = #t
(fold kons knil (unfold-right knull? kar kdr x)) = x
(unfold-right knull? kar kdr (fold kons knil x)) = x.
map proc clist1 clist2 ... -> list
map は各リストの要素ごとに proc を適用し、
その戻り値からなるリストを返す。
リストの要素に proc を適用する順序は既定されない。
(map cadr '((a b) (d e) (g h))) => (b e h)
(map (lambda (n) (expt n n))
'(1 2 3 4 5))
=> (1 4 27 256 3125)
(map + '(1 2 3) '(4 5 6)) => (5 7 9)
(let ((count 0))
(map (lambda (ignored)
(set! count (+ count 1))
count)
'(a b))) => (1 2) or (2 1)
この手続きは
R5RS
の仕様を拡張しており、各リスト引数は同じ長さでなくてもよい。
もっとも短い長さをもつリストが尽きると終了する。
少なくとも 1 つのリスト引数は有限でなければならない。
(map + '(3 1 4 1) (circular-list 1 0)) => (4 1 5 1)
for-each proc clist1 clist2 ... -> unspecified
for-each の引数は map の引数と似ているが、
for-each は値を生成する目的ではなく副作用を目的として
proc を呼び出す。
map とは異なり、for-each
は各リスト引数の左から右の順序で proc
を呼び出すことが保証されている。
また for-each の返り値は不定値である。
(let ((v (make-vector 5)))
(for-each (lambda (i)
(vector-set! v i (* i i)))
'(0 1 2 3 4))
v) => #(0 1 4 9 16)
この手続きは
R5RS
の仕様を拡張しており、各リスト引数の長さは同じでなくてもよい。
もっとも短い長さをもつリストが尽きると終了する。
少なくとも 1 つのリスト引数は有限でなければならない。
append-map f clist1 clist2 ... -> value
append-map! f clist1 clist2 ... -> value
(apply append (map f clist1 clist2 ...))
(apply append! (map f clist1 clist2 ...))
map 関数と同様に f を適用し、
適用の結果のリストをすべてアペンドして返す。
append-map は結果のアペンドに append を使用し、
append-map! は append! を使用する。
f が適用される順序については規定されない。
Example:
(append-map! (lambda (x) (list x (- x))) '(1 3 8))
=> (1 -1 3 -3 8 -8)
少なくとも 1 つの引数リストは有限でなければならない。
map! f list1 clist2 ... -> list
map を線形更新な形で実装した手続きである。
map! が list1 の
cons セルを変更して結果のリストを構築することは許されるが要求はされない。
f が適用される順序については規定されない。 リスト引数が複数ある場合、clist2, clist3, ... は list1 の要素数以上の要素をもたなければならない。
map-in-order f clist1 clist2 ... -> list
map 手続きの変種であり、
listi 引数の各要素に対して f
が左から右の順序で適用されることが保証されている。
この手続きは、マッピング手続きが返り値を返すとともに副作用をもつ場合に有用である。
少なくとも 1 つのリスト引数は有限でなければならない。
pair-for-each f clist1 clist2 ... -> unspecific
for-each と似ているが、f
はリスト引数の連続する部分リストに対して適用される。
つまり、f はリストの要素に適用されるのではなく、リストの
cons セルに適用される。適用の順序は左から右である。
手続き f がペアに対して set-cdr! を呼び出しても、実行の順序は変化しない。
(pair-for-each (lambda (pair) (display pair) (newline)) '(a b c)) ==>
(a b c)
(b c)
(c)
少なくとも 1 つのリスト引数は有限でなければならない。
filter-map f clist1 clist2 ... -> list
map, but only true values are saved.
(filter-map (lambda (x) (and (number? x) (* x x))) '(a 1 b 3 c 7))
=> (1 9 49)
手続き f が適用される順序は規定されない。
少なくとも 1 つのリスト引数は有限でなければならない。
filter pred list -> list
(filter even? '(0 7 8 8 43 -4)) => (0 8 8 -4)
partition pred list -> [list list]
(partition symbol? '(one 2 3 four five 6)) =>
(one four five)
(2 3 6)
remove pred list -> list
(lambda (pred list) (filter (lambda (x) (not (pred x))) list))リストの順序は変更されない。 結果のリストの要素の順序は引数のリストの要素の順序と同じである。 結果のリストは引数のリストと共通の末尾を共有してもよい。 pred が適用される順序は規定されない。
(remove even? '(0 7 8 8 43 -4)) => (7 43)
filter! pred list -> list
partition! pred list -> [list list]
remove! pred list -> list
filter、partition、remove を線形更新な形で実装したもの。
これらの手続きがリスト引数の cons セルを変更して結果のリストを返すことが許可されるが要求はされない。
以下の手続きは、リストを検索してある基準を満たす最左の要素を探す。 このため、必ずしもリスト全体を調べるわけではない。 したがって、ドット リストや循環リストを指定した場合、それを検出してエラーを発生させるための効率的な方法はない。 異なる種類のリストに対して手続きを適用した場合の一般的な規則を述べる。
要するに、SRFI-1 に準拠するコードは以下の手続きにドット リストを渡してはいけない。
典型的な手続きである find と any を使用した例を以下に示す。
;; 真正リスト、成功 (find even? '(1 2 3)) => 2 (any even? '(1 2 3)) => #t ;; 真正リスト、失敗 (find even? '(1 7 3)) => #f (any even? '(1 7 3)) => #f ;; ドット リストに対して失敗するとエラー (find even? '(1 3 . x)) => error (any even? '(1 3 . x)) => error ;; ドット リストは検索を満たす要素を含む。 ;; この場合の動作は規定されない。 ;; 成功、エラー、あるいは別の結果となってもよい。 (find even? '(1 2 . x)) => error/undefined (any even? '(1 2 . x)) => error/undefined ; success, error or other. ;; 循環リスト、成功 (find even? (circular-list 1 6 3)) => 6 (any even? (circular-list 1 6 3)) => #t ;; 循環リスト、失敗はエラーであり、手続きは終了しないこともある (find even? (circular-list 1 3)) => error (any even? (circular-list 1 3)) => error
find pred clist -> value
(find even? '(3 1 4 1 5 9)) => 4
find は検索のセマンティクスにおいて曖昧さをもつことに注意せよ。
find が #f を返す場合、
pred を満たす #f 要素を見つけたのか、
または、満たす要素がまったく見つからなかったのか、
(一般的には) 判断することができない。
多くの状況では、このような曖昧さは起こらない。
検索対象のリストが #f 要素を含まないことがわかっているか、あるいは、
リストに pred を満たす要素が含まれていることが保証されているという場合が多い。
しかし、曖昧さが起きる場合には、find の代わりに find-tail
を使うとよい。find-tail にはこのような曖昧さがない。
(cond ((find-tail pred lis) => (lambda (pair) ...)) ; (CAR PAIR) を処理
(else ...)) ; 検索失敗
find-tail pred clist -> pair or false
find-tail は member 関数を汎用化した述語であると見ることができる。
例:
(find-tail even? '(3 1 37 -8 -5 0 0)) => (-8 -5 0 0) (find-tail even? '(3 1 37 -5)) => #f ;; MEMBER X LIS: (find-tail (lambda (elt) (equal? x elt)) lis)循環リストの場合、この手続きはリストを「ローテート」することになる。
find-tail は、その意味は逆であるが、本質的に
drop-while と同等である。
find-tail は述語を満たす要素を見つけるまで検索を行うのに対し、
drop-while は述語を満たさない要素を見つけるまで検索を行う。
take-while pred clist -> list
take-while! pred clist -> list
take-while! は線形更新な形で実装したものである。
引数のリストを変更して結果のリストを作成することは許されるが要求はされない。
(take-while even? '(2 18 3 10 22 9)) => (2 18)
drop-while pred clist -> list
(drop-while even? '(2 18 3 10 22 9)) => (3 10 22 9)循環リストに対しては、リストを「ローテート」したように見える場合もある。
span pred clist -> [list clist]
span! pred list -> [list list]
break pred clist -> [list clist]
break! pred list -> [list list]
span は、要素が述語 pred
を満たす最長の先頭部分と残りの部分とに分割する。
break はこの述語の逆の意味をもち、
要素が述語を満たさない最長の先頭部分と残りの部分とに分割する。
言い換えると、
span は pred を満たさない最初の要素を探し、
break は pred を満たす最初の要素を探すのである。
span は以下の式に等価である。
(values (take-while pred clist)
(drop-while pred clist))
span! と break! は線形更新な形で実装したものである。
これらの手続きは、引数のリストを変更して結果のリストを作成することは許されるが、要求はされない。
(span even? '(2 18 3 10 22 9)) => (2 18) (3 10 22 9) (break even? '(3 1 4 1 5 9)) => (3 1) (4 1 5 9)
any pred clist1 clist2 ... -> value
n 個のリスト clist1 ... clistn を指定する場合、pred は n 個の引数をとり、ブール値を返す必要がある。
まず any は pred を clisti
の最初の要素に適用する。述語が真値を返す場合、any
はすぐにその真値を返す。
そうでない場合、pred を clisti の
2 番目の要素、3 番目の要素、というふうに繰り返し適用する。
この繰り返しは、真値が返されたとき、または、
引数リストのうちのいずれかが尽きたときに終了する。
後者の場合、any は #f を返す。
リストの最後の要素に対して pred を呼び出す場合、それは末尾呼び出しになる。
find と any の違いに注意せよ。
find は述語を満たす要素を返すのに対し、
any は述語により生成される真値を返す。
every と同様に any はその名前が疑問符で終っていない。
このことは、この手続きが単純にブール値 (#t または #f)
を返すのではなく、一般的な値を返すことを示唆している。
(any integer? '(a 3 b 2.7)) => #t
(any integer? '(a 3.1 b 2.7)) => #f
(any < '(3 1 4 1 5)
'(2 7 1 8 2)) => #t
every pred clist1 clist2 ... -> value
n 個のリスト引数 clist1 ... clistn を指定する場合、手続き pred は n 個の引数をとりブール値を返す必要がある。
まず every は pred を clisti
の最初の要素に適用する。述語が偽を返す場合、every
はすぐに偽を返す。
そうでない場合、pred を clisti の
2 番目の要素、3 番目の要素、というふうに繰り返し適用する。
この繰り返しは、偽が返されたとき、または、
引数リストのうちのいずれかが尽きたときに終了する。
後者の場合、every は最後の pred
呼び出しで返された真値を返す。
リストの最後の要素に対して pred を呼び出す場合、それは末尾呼び出しになる。
clisti のいずれかが要素を 1 つも持たない場合、every
は #t を返す。
any と同様に every はその名前が疑問符で終っていない。
このことは、この手続きが単純にブール値 (#t または #f)
を返すのではなく、一般的な値を返すことを示唆している。
list-index pred clist1 clist2 ... -> integer or false
n 個のリスト引数 clist1 ... clistn を指定する場合、pred は n 個の引数をとりブール値を返す必要がある。
まず list-index は pred を clisti
の最初の要素に適用する。それが真を返す場合、list-index
はすぐに 0 を返す。
そうでない場合、pred を clisti の
2 番目の要素、3 番目の要素、というふうに繰り返し適用する。
この繰り返しは、pred が真を返すと終了し、
そのときの要素の 0-based のインデックスを返す。
この繰り返しは、各リストのいずれかが尽きたときにも終了する。
その場合、list-index は #f を返す。
(list-index even? '(3 1 4 1 5 9)) => 2 (list-index < '(3 1 4 1 5 9 2 5 6) '(2 7 1 8 2)) => 1 (list-index = '(3 1 4 1 5 9 2 5 6) '(2 7 1 8 2)) => #f
member x list [=] -> list
memq x list -> list
memv x list -> list
(drop list i)
(i は list の長さより小さい)
により返される非空リストである。
x が list の中に存在しない場合、#f
を返す。
memq は eq? を使用して、
x と list の要素を比較する。
また、memv は eqv? を使用し、
member は 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
(member (list 'a)
'(b (a) c)) => ((a) c)
(memq 101 '(100 101 102)) => *unspecified*
(memv 101 '(100 101 102)) => (101 102)
member は
R5RS
の定義を拡張しており、キーの比較に使用する同値手続き =
をオプション引数として指定することができる。
比較手続きは list の各要素 ei とキー x を以下のように比較する。
(= x ei) ; リストを (E1 ... En) とする
(member 5 list <)
とすればよい。
完全に一般的なリスト検索は、
find-tail および find 手続きにより実現できる。
たとえば、
(find-tail even? list) ; 偶数キーをもつ最初の要素を見つける
delete x list [=] -> list
delete! x list [=] -> list
delete は比較手続き = (デフォルトでは equal?)
を使用して x に等しい list の要素をすべて検索し、
それらを list から削除する。
= が適用される順序は規定されない。
リストの順序は変更されない。 結果のリストに現れる要素の順序は、それらが引数のリストに現れる順序と同じである。 結果のリストは引数のリストと共通の末尾を共有してもよい。
完全に汎用的な要素削除は remove および remove!
により実行できることに注意せよ。たとえば、
;; LIS からすべての偶数を削除する (remove even? lis)比較手続きは
(= x ei) のように使われる。
つまり、x は常に 1 つめの引数となり、リストの要素は 2 つめの引数となる。
比較手続きは list の要素 1 つに対してちょうど 1 回だけ使用される。
個々の ei に述語が適用される順序は規定されない。
したがって、(delete 5 list <) という式により、
リストから 5 より大きい要素をすべて削除できる。
delete! は delete を線形更新にしたものである。
引数のリストの cons セルを変更して結果のリストを構築することは許可されるが要求されてはいない。
delete-duplicates list [=] -> list
delete-duplicates! list [=] -> list
delete-duplicates はリスト引数から重複した要素を削除する。
リスト引数に複数の等しい要素がある場合、結果のリストには最初の要素 (最左の要素)
だけが含まれる。
削除されずに残る要素は元のリストの要素と同じ順序になる。
delete-duplicates はリストの順序を変更しない
(このため、この手続きは連想リストの「お掃除」に使うことができる)。
引数 = は、リストの要素を比較するために使用される。
デフォルトは equal? である。
list において x が y の前に現れる場合、
比較は (= x y) のように行われる。
比較手続きは list の要素 1 組につき多くても 1 度しか使用されない。
比較手続きが適用される順序は規定されない。
delete-duplicates の実装では、
引数のリストと結果のリストが共通の末尾を共有してもよい。
たとえば、引数のリストが 1 つの要素のみを含む場合、そのリストをそのまま返してもよい。
一般的にいうと、delete-duplicates は n 個の要素のリストに対して
O(n2) の実行時間がかかることに注意せよ。
長いリストに対しては、そのリストをソートして同じ要素を 1 箇所に集め、
線形時間アルゴリズムにより等しい要素を削除することで、
重複削除を O(n lg n) の時間で実行できる。
別の方法として、要素マーキングによるアルゴリズムを使えば線形時間で重複削除が行える。
delete-duplicates! は delete-duplicates を線形更新にしたものである。
引数のリストの cons セルを変更して結果のリストを構築することは許可されるが要求されてはいない。
(delete-duplicates '(a b a c a b c z)) => (a b c z)
;; 連想リストのお掃除
(delete-duplicates '((a . 3) (b . 7) (a . 9) (c . 1))
(lambda (x y) (eq? (car x) (car y))))
=> ((a . 3) (b . 7) (c . 1))
「連想リスト」("association list" または "alist") はペアのリストである。 各ペアの car はキー値を格納し、cdr はそれに関連付けられたデータ値を格納する。 連想リストは Scheme でシンプルな検索テーブルを構築するときに使用される。 連想リストはたいていの場合、大きなデータに対して高速な検索が必要な用途には適切でないことに注意せよ。 このような用途には、ハッシュ テーブルや他の方法を使用すべきである。
assoc key alist [=] -> pair or #f
assq key alist -> pair or #f
assv key alist -> pair or #f
#f を返す。
assq は alist の中のペアの car フィールドと key
の比較に eq? を使用し、
assv は eqv? を使用し、
assoc は equal? を使用する。
(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)
assoc は
R5RS
の定義を拡張しており、オプションでキーの比較を行う同値述語 =
を渡すことができる。
比較手続きは、list の要素 ei と引数 key を次のように比較するために使用される。
(= key (car ei)) ; list is (E1 ... En)
(assoc 5 alist <) とすればよい。
完全に汎用的な連想リストの検索は、
find-tail および find 手続きにより実行できることに注意せよ。
たとえば、
;; alist の中で偶数キーをもつ最初の最初のエントリを検索する (find (lambda (a) (even? (car a))) alist)
alist-cons key datum alist -> alist
(lambda (key datum alist) (cons (cons key datum) alist))連想リスト alist に新しいエントリ key -> datum を作成する。
alist-copy alist -> alist
(lambda (a) (map (lambda (elt) (cons (car elt) (cdr elt))) a))
alist-delete key alist [=] -> alist
alist-delete! key alist [=] -> alist
alist-delete は、連想リスト alist からキー key
をもつエントリをすべて削除する。
キーの比較には手続き = を使用し、そのデフォルトは equal? である。
手続き = を適用する順序は既定されない。
結果のリストは引数 alist と共通の末尾を共有するかもしれない。 結果の連想リストは順序が変更されない。 結果の連想リストの要素の順序は、引数の連想リストの要素の順序と同じである。
比較手続きは、連想リスト alist のキー
ki のエントリと引数 key
とを比較するために次のように使用される。
(= key ki) 。
このため、キー値が 5 以上である alist のすべてのエントリを削除するには、
(alist-delete 5 alist <) とすればよい。
alist-delete! は alist-delete を線形更新な形で実装したものである。
引数 alist の cons セルを変更して結果のリストを作成することは許可されるが要求はされない。
以下の手続きは、要素のリストで表現される集合に対して演算を施す。
これらの手続きは、リストの要素を比較するために引数 = を使用する。
この同値手続きは eq? と整合性をもたなければならない。
すなわち、次の式を持たす必要がある。
(eq? x y) => (= x y).
eq? により同値な 2 つのリストは、有効な同値手続きのもとで集合的に同値であるということである。
これにより、eq? で同値なリストに対する集合演算が定数時間で終了する。
n 個および m 個の要素をもつ 2 つのリストに対して、ここで述べる集合演算は通常 O(n * m) の時間を要することに注意せよ。 大きな集合に対する高速な演算が必要なアプリケーションでは、専用のデータ構造体およびアルゴリズムを使用するほうが望ましいであろう。
lset<= = list1 ... -> boolean
(lset<= eq? '(a) '(a b a) '(a b c c)) => #t (lset<= eq?) => #t ; 自明なケース (lset<= eq? '(a)) => #t
lset= = list1 list2 ... -> boolean
(lset= eq? '(b e a) '(a e b) '(e e b a)) => #t (lset= eq?) => #t ; 自明なケース (lset= eq? '(a)) => #t
lset-adjoin = list elt1 ... -> list
引数のリストは常に結果のリストの末尾となる。 引数のリストに重複する要素が含まれていても、それは削除されない。
(lset-adjoin eq? '(a b c d c e) 'a 'e 'i 'o 'u) => (u o i a b c d c e)
lset-union = list1 ... -> list
リスト A と B の和は次のようにして構成される。
(= r b) を計算する。
すべての比較が偽を返すと、結果リストの先頭に cons される。
eq? である場合、
この操作はすぐに終了するかも知れない。
n 個のリストに対してこの手続きを適用する場合、 2 個のリストに対するリスト和の計算が、すべてのリストに対して fold される。
(lset-union eq? '(a b c d e) '(a e i o u)) =>
(u o i a b c d e)
;; LIST1 の重複する要素は保持される
(lset-union eq? '(a a c) '(x a x)) => (x a a c)
;; 自明なケース
(lset-union eq?) => ()
(lset-union eq? '(a b c)) => (a b c)
lset-intersection = list1 list2 ... -> list
リスト A と B の共通集合は、
A の要素のうち B のいずれかの要素に =
の意味で等しい要素から構成される。
すべての A の要素 a と
B の要素 b に対して
(= a b) が計算される。
この手順によると、B の要素に同値な要素が
A に重複して存在する場合、
結果のリストにも要素が重複して現れることに注意せよ。
結果のリストに現れる要素の順序は、list1 の要素の順序に等しい。
つまり、実質的には lset-intersection は要素の順序を変えることなく
list1 をフィルタするのである。
結果のリストは list1 と共通の末尾を共有する。
n 個のリストにこの手続きを適用する場合、 2 個のリストに対する共通集合の計算が、すべてのリストに対して fold される。 しかし、= が適用される順序は規定されない。 list1 の各要素に対して、 それが他のすべてのリストに含まれるかどうか調べることを繰り返すかもしれないし、 あるいは、 list1 と list2 の共通集合を完全に計算してから、 その結果と list3 で共通部分の計算を行うことを繰り返すかもしれないし、 あるいは、 これらとは別の方法で計算するかもしれない。
(lset-intersection eq? '(a b c d e) '(a e i o u)) => (a e) ;; LIST1 の重複する要素は保持される (lset-intersection eq? '(a x y a) '(x a x z)) => '(a x a) (lset-intersection eq? '(a b c)) => (a b c) ; 自明なケース
lset-difference = list1 list2 ... -> list
= 手続きの 1 つめの引数は、常に list1 の要素であり、
2 つめの引数は他の listi の要素である。
list1 引数に重複する要素がある場合、結果のリストでも要素が重複して現れる。
結果のリストの要素の順序は、list1 の要素の順序と同じである。
つまり、実質的には lset-difference は要素の順序を変えることなく
list1 をフィルタするのである。
結果のリストは list1 と共通の末尾を共有する。
手続き = が適用される順序は規定されない。
この手続きは、list1
の各要素ごとに他のリストに含まれるかどうかの検査を繰り返すかもしれないし、
あるいは、
list1 と list2 の差集合を完全に計算してから、
その結果と list3 の差集合を計算するということを繰り返すかもしれないし、
あるいは、
これらとは別の方法で計算するかもしれない。
(lset-difference eq? '(a b c d e) '(a e i o u)) => (b c d) (lset-difference eq? '(a b c)) => (a b c) ; 自明なケース
lset-xor = list1 ... -> list
より正確には、2 つのリスト A と B に対して、 リスト A xor B の要素は次のように決定される。
(= a b) となるような
B の要素 b が存在しない要素。
(= b a) となるような
A の要素 a が存在しない要素。
(= a b) =>
(= b a).
(= a b)
が A のある要素 a と B のある要素 b
に対して真であれば、
a と b はともに結果のリストから削除してもよい。
引数が n 個の場合、引数が 2 個の xor 演算を fold した結果となる。
(lset-xor eq? '(a b c d e) '(a e i o u)) => (d c b i o u) ;; 自明なケース (lset-xor eq?) => () (lset-xor eq? '(a b c d e)) => (a b c d e)
lset-diff+intersection = list1 list2 ... -> [list list]
(values (lset-difference = list1 list2 ...)
(lset-intersection = list1
(lset-union = list2 ...)))
しかし、これより効率的に実装することが可能である。
= 手続きの 1 つめの引数は list1 の要素であり、2 つめの引数は他の listi の要素である。
結果のリストのどちらかが list1 と共通の末尾を共有するかもしれない。 この演算は実質的に list1 を分割することになる。
lset-union! = list1 ... -> list
lset-intersection! = list1 list2 ... -> list
lset-difference! = list1 list2 ... -> list
lset-xor! = list1 ... -> list
lset-diff+intersection! = list1 list2 ... -> [list list]
lset-union! は任意のリスト引数の cons セルを再利用することが許される。
以下に述べる手続きは、 R5RS のペアに対する基本的な副作用演算である。
set-car! pair object -> unspecified
set-cdr! pair object -> unspecified
(define (f) (list 'not-a-constant-list)) (define (g) '(constant-list)) (set-car! (f) 3) => *unspecified* (set-car! (g) 3) => *error*
このライブラリの設計は、SRFI の議論フェーズにおけるフィードバックから多くの恩恵を受けた。 次の方々がメーリングリストと個人的な議論において思慮深い論評や提案をしてくれました。 Mike Ashley, Darius Bacon, Alan Bawden, Phil Bewig, Jim Blandy, Dan Bornstein, Per Bothner, Anthony Carrico, Doug Currie, Kent Dybvig, Sergei Egorov, Doug Evans, Marc Feeley, Matthias Felleisen, Will Fitzgerald, Matthew Flatt, Dan Friedman, Lars Thomas Hansen, Brian Harvey, Erik Hilsdale, Wolfgang Hukriede, Richard Kelsey, Donovan Kolbly, Shriram Krishnamurthi, Dave Mason, Jussi Piitulainen, David Pokorny, Duncan Smith, Mike Sperber, Maciej Stachowiak, Harvey J. Stein, John David Stone, Joerg F. Wittenberger。 彼らの支援に感謝したい。
私はまた、論拠において述べたシステムの設計者、実装者、文書作成者に感謝したい。 Aubrey Jaffer と Kent Pitman は、ウェブからアクセス可能な R5RS と Common Lisp の仕様書を作り上げてくれた。 これは、非常に大きな助けとなった。
もちろん、以上に謝辞を述べたからといって、 援助してくださった方々が最終的なこの文書を是認しなければならないというわけではない。
The Common Lisp "HyperSpec," produced by Kent Pitman, is essentially the ANSI spec for Common Lisp: http://www.harlequin.com/education/books/HyperSpec/.
Certain portions of this document -- the specific, marked segments of text describing the R5RS procedures -- were adapted with permission from the R5RS report.
All other text is copyright (C) Olin Shivers (1998, 1999). All Rights Reserved.
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.