For Gauche 0.9.6


Next: , Previous: , Up: ライブラリモジュール - Gauche拡張モジュール   [Contents][Index]

9.13 gauche.lazy - 遅延シーケンスユーティリティ

Module: gauche.lazy

このモジュールは、遅延シーケンスを生成するようなユーティリティ手続きの数々を提供します。 遅延シーケンス自体については遅延シーケンスを参照してください。

遅延シーケンスは自動的にforceされ、通常のリストと区別がつかないので、 引数にリストを取るか遅延シーケンスを取るかで別々の手続きを用意する必要はありません。 例えばfindは、リストから要素を探すのにも遅延シーケンスから要素を探すのにも使えます。

しかし、返り値としてリストを返すか遅延シーケンスを返すかは、 手続きを別にする必要があります。 例えばlmapは、引数としてはどちらも受け取ることができますが、 返り値は遅延シーケンスになります。(そして、高階手続きは必要な分だけ呼ばれます。)

この区別は混乱しやすいので、整理しておきます。 maplmapのどちらも、遅延シーケンスに適用することができます。 結果のリストを一度に計算した状態で手に入れたいなら、mapを使います。 その場合、遅延計算のオーバヘッドはかかりません。 もし結果のリスト全てを使うかどうかわからない、 あるいは結果のリストが巨大になるので中間結果の保持のためにメモリを圧迫したくない、 といった場合にはlmapを使いましょう。

Function: x->lseq obj

{gauche.lazy} objを(おそらく遅延された)リストに変換する便利な手続きです。 objがリストならそのまま返されます。 objが他のコレクション型なら、コレクションの各要素を順に返す遅延シーケンスが返されます。 objがそれ意外ならやはりそのまま返されます(ドットリストの特別な場合と考えられます)。

REPLでx->lseqを試すと、単に渡したコレクションをリストに変換しているだけのように見えるでしょう。

(x->lseq '#(a b c)) ⇒ (a b c)

実際には、返された遅延シーケンスがREPLの出力ルーチンによってforceされてリストになっています。

Function: lunfold p f g seed :optional tail-gen

{gauche.lazy} unfoldの遅延バージョンです (R7RSリスト参照)。 pfg引数はそれぞれ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)
Function: lmap proc seq seq2 …

{gauche.lazy} procseq seq2 …の各1番目の要素、各2番目の要素、… に適用したものからなる遅延シーケンスを返します。 どれかの入力が尽きた時が結果のシーケンスの終わりとなります。 procの適用は必要になるまで遅延されます。

;; lmapのかわりにmapを使うとこの式の評価は終わらない
(use math.prime)
(take (lmap (pa$ * 2) *primes*) 10)
  ⇒ (4 6 10 14 22 26 34 38 46 58)
Function: lmap-accum proc seed seq seq2 …

{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は最後のシード値を返しません。 最後のシード値を返すためには結果の遅延シーケンスを最後まで計算する必要があるので、 遅延計算にならないからです。

Function: lappend seq …

{gauche.lazy} シーケンスseq …をつなぎ合わせた遅延シーケンスを返します。 appendと違い、この手続きはO(1)時間で、すぐに返ります。 従って、大きなシーケンスをつなぎ合わせたいけれど全部使うとは限らない、といった場合に便利です。

Function: lconcatenate seqs

{gauche.lazy} seqs引数はシーケンスのシーケンスです。 それら各シーケンスを全てつなぎ合わせた遅延シーケンスを返します。

これと(apply lappend seqs)との違いは、lconcatenateは 無限個のseqをつなぎ合わせられるということです。

Function: lappend-map proc seq1 seq …

{gauche.lazy} append-mapの遅延バージョンです。 これは単にlappendlmapを合成したものとは異なります。 というのも、(apply lappend (lmap proc seq1 seq …))では、 applyが引数リストを確定するためにlmapを最後まで評価しなければ ならないからです。

また、これは(lconcatenate (lmap proc seq1 seq …))とも 微妙に異なります。

Gaucheの遅延シーケンスは1つ要素を余分に評価することを覚えていますか。 lconcatenatelmapの結果に対して「一つ余分に評価」を行います。 この効果を調べるために、デバッグプリントをつけた手続きを使ってみましょう。

(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
Function: linterweave seq …

{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 *)
Function: lfilter proc seq

{gauche.lazy} procseqの各要素に適用し、#fでない値だけを集めた遅延シーケンスを 返します。

Function: lfilter-map proc seq seq2 …

{gauche.lazy} filter-mapの遅延バージョンです。

Function: lstate-filter proc seed seq

{gauche.lazy} gstate-filterの遅延シーケンス版です (ジェネレータの操作参照)。

Function: ltake seq n :optional fill? padding
Function: ltake-while pred seq

{gauche.lazy} take*take-whileの遅延バージョンです (リストへのアクセスと変更参照)。 ltaketakeではなくtake*のように動作します。 つまり、入力シーケンスの長さがn以下でもエラーになりません。 というもの、ltakeは怠惰に動作するため、 値を返す時点では入力が足りないかどうかわからないからです。

ldropldrop-whiteはありません。必要ないからです。 dropdrop-whiteを遅延シーケンスに適用すれば、 遅延シーケンスが返されます。

Function: lrxmatch rx seq

{gauche.lazy} grxmatchの遅延シーケンス版です(ジェネレータの操作参照)。

seqは文字のシーケンス (文字列を含む) でなければなりません。 返り値は<rxmatch>オブジェクトからなる遅延シーケンスです。 各要素の<rxmatch>オブジェクトが、 入力中のrxにマッチした部分を表現しています。

この手続きは遅延文字シーケンス中からマッチするパターンを探すのに便利ですが、 入力が文字列ではなく、パターンが滅多にマッチしない場合に非常に遅くなる危険があることに 注意してください。lrxmatchは入力をある程度バッファしてスキャンし、 マッチがみつからなければ、バッファを拡張してまた最初からスキャンします。 というのも、新たなマッチが以前のバッファの末尾から新たに追加された部分へと またがっている可能性があるからです。

Function: lslices seq k :optional fill? padding

{gauche.lazy} slicesの遅延バージョンです(リストへのアクセスと変更参照)。

(lslices '(a b c d e f) 2)
  ⇒ ((a b) (c d) (e f))

Next: , Previous: , Up: ライブラリモジュール - Gauche拡張モジュール   [Contents][Index]