gauche.lazy - 遅延シーケンスユーティリティ ¶遅延シーケンスは自動的にforceされ、通常のリストと区別がつかないので、
引数にリストを取るか遅延シーケンスを取るかで別々の手続きを用意する必要はありません。
例えばfindは、リストから要素を探すのにも遅延シーケンスから要素を探すのにも使えます。
しかし、返り値としてリストを返すか遅延シーケンスを返すかは、 手続きを別にする必要があります。 例えばlmapは、引数としてはどちらも受け取ることができますが、 返り値は遅延シーケンスになります。(そして、高階手続きは必要な分だけ呼ばれます。)
この区別は混乱しやすいので、整理しておきます。
mapとlmapのどちらも、遅延シーケンスに適用することができます。
結果のリストを一度に計算した状態で手に入れたいなら、mapを使います。
その場合、遅延計算のオーバヘッドはかかりません。
もし結果のリスト全てを使うかどうかわからない、
あるいは結果のリストが巨大になるので中間結果の保持のためにメモリを圧迫したくない、
といった場合にはlmapを使いましょう。
| • 遅延シーケンスのコンストラクタ: | ||
| • 遅延シーケンスの操作: | ||
| • 位置情報つき遅延シーケンス: |
遅延シーケンスは組み込みのgenerator->lseqやlconsで作ることができます。
このモジュールでは追加でいくつかのコンストラクタを用意しています。
{gauche.lazy}
objを(おそらく遅延された)リストに変換する便利な手続きです。
objがリストならそのまま返されます。
objが他のコレクション型なら、コレクションの各要素を順に返す遅延シーケンスが返されます。
objがそれ以外ならやはりそのまま返されます(ドットリストの特別な場合と考えられます)。
REPLでx->lseqを試すと、単に渡したコレクションをリストに変換しているだけのように見えるでしょう。
(x->lseq '#(a b c)) ⇒ (a b c)
実際には、返された遅延シーケンスがREPLの出力ルーチンによってforceされてリストになっています。
{gauche.lazy}
unfoldの遅延バージョンです (scheme.list - R7RSリスト参照)。
p、f、g引数はそれぞれ1引数を取る手続きで、
現在のシード値を受けとります。
pは生成を停止するかどうかを決める述語、
fは要素を生成する手続き、そして
gは次のシード値を生成する手続きです。
seed引数には最初のシード値を与えます。
tail-genが与えられた場合、それは最後のシード値
(つまり、(p seed)が#fを返した時のシード値)を
受け取り、リストあるいは遅延シーケンスを返す手続きです。
それが結果のシーケンスの末尾に付け足されます。
(lunfold ($ = 10 $) ($ * 2 $) ($ + 1 $) 0 (^_ '(end))) ⇒ (0 2 4 6 8 10 12 14 16 18 end)
{gauche.lazy}
(seed (proc seed) (proc (proc seed)) …) という無限シーケンスを作ります。
同じシーケンスは(lunfold (^_ #f) identity proc seed)でも作れますが、
こちらの方がずっと効率的です。
類似の手続きとして、util.streamにstream-iterateがあります
(Stream constructors参照)。
(take (literate (pa$ + 1) 0) 10) ⇒ (0 1 2 3 4 5 6 7 8 9)
{gauche.lazy}
proc引数がひとつの引数yieldを伴って呼び出されます。
yeidlはそれ自体がひとつの引数を取る手続きで、呼ばれるとそこに渡された
値が、結果のlseqの要素となります。procからリターンしたらlseqも終了となります。
(coroutine->lseq (^[yield] (dotimes [i 10] (yield (square i))))) ⇒ (0 1 4 9 16 25 36 49 64 81)
ジェネレータの生成のgenerate、および
control.cseq - 並行シーケンスのcoroutine->cseqも参照。
{gauche.lazy}
objを返しますが、それがlseqであった場合、その要素を全て計算します。
ある時点までに必要な計算が全て行われることを保証したい場合に便利です。
例えばポートから遅延計算でデータを読み出している場合に、
ポートを閉じる時点で全てのデータが読まれたことを保証したい、といった場合です。
{gauche.lazy}
procをseq seq2 …の各1番目の要素、各2番目の要素、…
に適用したものからなる遅延シーケンスを返します。
どれかの入力が尽きた時が結果のシーケンスの終わりとなります。
procの適用は必要になるまで遅延されます。
p;; lmapのかわりにmapを使うとこの式の評価は終わらない (use math.prime) (take (lmap (pa$ * 2) *primes*) 10) ⇒ (4 6 10 14 22 26 34 38 46 58)
{gauche.lazy}
procは各シーケンスseq seq2 …からの要素一つづつと、
現在のシード値を取り、結果の要素値と次のシード値を返す手続きです。
lmap-accumの結果は、procが生成する要素値からなる遅延シーケンスとなります。
(use math.prime) (take (lmap-accum (^[p sum] (values sum (+ p sum))) 0 *primes*) 10) ⇒ (0 2 5 10 17 28 41 58 77 100)
これはmap-accumの遅延バージョンです(コレクションに対するマッピング参照)。
ただ、lmap-accumは最後のシード値を返しません。
最後のシード値を返すためには結果の遅延シーケンスを最後まで計算する必要があるので、
遅延計算にならないからです。
{gauche.lazy}
シーケンスseq …をつなぎ合わせた遅延シーケンスを返します。
appendと違い、この手続きはO(1)時間で、すぐに返ります。
従って、大きなシーケンスをつなぎ合わせたいけれど全部使うとは限らない、といった場合に便利です。
{gauche.lazy}
seqs引数はシーケンスのシーケンスです。
それら各シーケンスを全てつなぎ合わせた遅延シーケンスを返します。
これと(apply lappend seqs)との違いは、lconcatenateは
無限個のseqをつなぎ合わせられるということです。
{gauche.lazy}
append-mapの遅延バージョンです。
これは単にlappendとlmapを合成したものとは異なります。
というのも、(apply lappend (lmap proc seq1 seq …))では、
applyが引数リストを確定するためにlmapを最後まで評価しなければ
ならないからです。
また、これは(lconcatenate (lmap proc seq1 seq …))とも
微妙に異なります。
Gaucheの遅延シーケンスは1つ要素を余分に評価することを覚えていますか。
lconcatenateはlmapの結果に対して「一つ余分に評価」を行います。
この効果を調べるために、デバッグプリントをつけた手続きを使ってみましょう。
(define (p x) #?=(list x x))
次の例で、(apply lappend (lmap ...))がp
の適用を遅延しないことがわかります。
gosh> (car (apply lappend (lmap p '(1 2 3)))) (car (apply lappend (lmap p '(1 2 3)))) #?="(standard input)":4:(list x x) #?- (1 1) #?="(standard input)":4:(list x x) #?- (2 2) #?="(standard input)":4:(list x x) #?- (3 3) 1
lconcatenateはどうでしょう。
gosh> (car (lconcatenate (lmap p '(1 2 3)))) (car (lconcatenate (lmap p '(1 2 3)))) #?="(standard input)":4:(list x x) #?- (1 1) #?="(standard input)":4:(list x x) #?- (2 2) 1
おっと、最初の要素だけを取り出しているので、
lmapの最初の結果である(1 1)だけが必要なはずなのに、
pは2番目の入力に対しても適用されてしまいました。
これは、lmapの結果である中間の遅延リストが「1要素余分に」評価されるためです。
lappend-mapにはこの問題がありません。
gosh> (car (lappend-map p '(1 2 3))) (car (lappend-map p '(1 2 3))) #?="(standard input)":4:(list x x) #?- (1 1) 1
{gauche.lazy}
seq …の最初の要素を順番に取り、次に2番目の要素を順番に取り…として
得られる遅延シーケンスを返します。
入力のシーケンスのうち最も短いシーケンスの長さをNとすれば、
結果の遅延シーケンスの長さは(* N シーケンスの数)となります。
もし全ての入力シーケンスが無限長ならば、結果も無限長となります。
(linterweave (lrange 0) '(a b c d e) (circular-list '*)) ⇒ (0 a * 1 b * 2 c * 3 d * 4 e *)
{gauche.lazy}
procをseqの各要素に適用し、#fでない値だけを集めた遅延シーケンスを
返します。
{gauche.lazy}
filter-mapの遅延バージョンです。
{gauche.lazy}
take*とtake-whileの遅延バージョンです
(リストへのアクセスと変更参照)。
ltakeはtakeではなくtake*のように動作します。
つまり、入力シーケンスの長さがn以下でもエラーになりません。
というもの、ltakeは怠惰に動作するため、
値を返す時点では入力が足りないかどうかわからないからです。
ldropとldrop-whiteはありません。必要ないからです。
dropとdrop-whiteを遅延シーケンスに適用すれば、
遅延シーケンスが返されます。
{gauche.lazy}
grxmatchの遅延シーケンス版です(ジェネレータの操作参照)。
seqは文字のシーケンス (文字列を含む) でなければなりません。 返り値は<rxmatch>オブジェクトからなる遅延シーケンスです。 各要素の<rxmatch>オブジェクトが、 入力中のrxにマッチした部分を表現しています。
この手続きは遅延文字シーケンス中からマッチするパターンを探すのに便利ですが、
入力が文字列ではなく、パターンが滅多にマッチしない場合に非常に遅くなる危険があることに
注意してください。lrxmatchは入力をある程度バッファしてスキャンし、
マッチがみつからなければ、バッファを拡張してまた最初からスキャンします。
というのも、新たなマッチが以前のバッファの末尾から新たに追加された部分へと
またがっている可能性があるからです。
{gauche.lazy}
slicesの遅延バージョンです(リストへのアクセスと変更参照)。
(lslices '(a b c d e f) 2) ⇒ ((a b) (c d) (e f))
入力データストリームを遅延シーケンスとして取り扱うのは強力な抽象化です。 とりわけ、単純なリスト操作を使って制限の無い先読みを実現できます。
しかし、データの入力ストリーム内での位置情報を、例えばエラーメッセージのために取りたいといった ことは難しくなります。ポートから読んでいる場合は、ポートに問い合わせれば現在の位置を 教えてくれます。しかし遅延シーケンスは普通のリストと同じように見え、 入力ソースに問い合わせようにも既にデータは先読みされてしまっているかもしれません。
Gaucheは拡張ペアと呼ばれる、補助的な情報を保持できる特別なペアを持っています (拡張ペアとペア属性参照)。それを利用して、 遅延シーケンスに入力位置情報を持たせることができます。
{gauche.lazy}
位置情報を保持する変更不可な構造で、lseq-positionから返されます。
情報は以下の手続きでアクセスできます。
{gauche.lazy}
<sequence-position>のインスタンスseqposから情報を取り出します。
それぞれ、ソースの名前(通常はソースファイル名)、 行番号(1から)、カラム番号(1から)、アイテムカウント(読まれた文字数、0から)です。
ソース名が不明な場合は#fになっています。
{gauche.lazy}
port->char-lseqと同じように、portから読まれる文字の遅延シーケンスを
返します。ただし、そのシーケンスには位置情報が付加されており、
lseq-positionで取り出すことができます。
source-name、start-line、start-column、
start-item-countは最初の文字を読み出す前の位置情報の初期化に使われます。
デフォルトはそれぞれ、(port-name port)、1、1、0で、
オープンしたばかりのポートから読み出す場合はデフォルトが適切な値となっています。
既にポートからいくらか読み出してしまった場合などにこれらの値を指定してください。
{gauche.lazy}
generator->lseqと同じように、ジェネレータchar-genから生成される
文字からなる遅延シーケンスを返します。ただし、そのシーケンスには位置情報が付加されており、
lseq-positionで取り出すことができます。
source-name、start-line、start-column、
start-item-countは最初の文字を読み出す前の位置情報の初期化に使われます。
デフォルトはそれぞれ、(port-name port)、1、1、0です。
{gauche.lazy}
seqが遅延シーケンスで位置情報が付加されている場合は、
その情報を<sequence-position>のインスタンスにして返します。
seqに位置情報が付加されていない、あるいは遅延シーケンス以外のオブジェクトであった
場合は#fが返されます。