環境: Gauche 0.9.3
Gaucheで無限に続く列を表現するには遅延シーケンスを使う. 遅延シーケンスはgenerator->lseqにジェネレータ手続きを与えることで作成できる. ジェネレータ手続きとは引数を取らない手続きで, 呼ばれる度に次の値を返すようなもの. EOFが返されるとシーケンスの終了とみなされる. また, gauche.generatorのgenerateで作成できる.
よって, 例えばフィボナッチ数列を表現するコードは以下のようになる.
(use gauche.generator) ; for generate
(define fibs
(generator->lseq
(generate (^(yield) (let loop ((a 0) (b 1))
(yield a) (loop b ( a b)))))))
(take fibs 10) ;=> (0 1 1 2 3 5 8 13 21 34)
これを使うと, 例えばProject EulerのProblem 2 (400万以下のフィボナッチ数列について, 偶数項の合計を求めよ) は,
(use srfi-1) ; for take-while
(define (e002)
($ apply
$ filter (cut even? )
$ take-while (cut < 4000000) fibs))
と書くことができる.
注意
※ 以下の引用部分とコードは, Gauche ユーザリファレンスから抜粋したもの.
遅延シーケンスを, 繰り返しによる怠惰なアルゴリズムから構築する際に, 遅延ペアのcdr側のみが遅延評価の対象となります. ペアのcar側は直ちに評価されます.
Gaucheの遅延シーケンスは, 常にひとつ余分に評価します. 遅延ペアを手にした段階で, その中身にアクセスするかしないかにかかわらず, 既にそのcarは評価済みであるということです. {中略} 自分自身を参照する遅延データ構造, つまり, 遅延シーケンスの次の要素を計算するために そのシーケンスの前の方の要素を参照する必要がある場合は注意が必要です.
上記の2.が問題となる具体的な例は以下のようなもの.
(use gauche.lazy) ;; for lmap
(define *fibs* (lcons* 0 1 (lmap *fibs* (cdr *fibs*)))) ;; BUGGY
(car *fibs*)
⇒ 0
(cadr *fibs*)
⇒ *** ERROR: Attempt to recursively force a lazy pair.
_fibs_の二番目の要素(cadr)にアクセスするということは, _fibs_の二番目のペアのcarを取るということです. _fibs_の 二番目のペアは1と(lmap …)の遅延ペアになっています. carを取ろうとした時点でこの遅延ペアはforceされ, そのcdrが計算されます. lmapが最初に返さなければならないのは, _fibs_の一番目と二番目の 要素の和です. しかし_fibs_の二番目の要素は, 今まさにアクセスしようと している値です!
この問題は, ある要素を計算するために直前の要素を参照しなければ回避できます. フィボナッチ数はF(n) = F(n-1) F(n-2) = 2*F(n-2) F(n-3)と変形できるので, 遅延フィボナッチシーケンスはこう定義できます.
(define *fibs*
(lcons* 0 1 1 (lmap (^[a b] ( a (* b 2))) *fibs* (cdr *fibs*))))
(take *fibs* 20)
⇒ (0 1 1 2 3 5 8 13 21 34 55 89 144 233
377 610 987 1597 2584 4181)