Shiro(2010/05/12 01:33:46 PDT): Gaucheに部分継続を入れたので遊んでみた。 まずはオーソドックスなやつ。 for-eachのような内部イテレータから、外部イテレータを生成する。
(use gauche.partcont)
(define (inv walker)
(lambda (coll)
(define (continue)
(reset (walker (lambda (e) (shift k (set! continue k) e)) coll)
(eof-object)))
(lambda () (continue))))
call/ccだといくつも継続を切り替えなくちゃならないのだけれど、部分継続だとすっきり書ける。
(walker f coll)はコレクションcollの各要素に対してfを呼ぶ関数。 戻り値は無視 (副作用目的)。
invはwalkerを取って、外部イテレータ生成子を返す。 例えばwalkerとしてfor-eachを渡すと：
(define inv-for-each (inv for-each))
inv-for-eachは「リストを取って、呼ばれる度にその要素を順に返すジェネレータ」を 作る関数。
gosh> (define iter (inv-for-each '(1 2 3))) iter gosh> (iter) 1 gosh> (iter) 2 gosh> (iter) 3 gosh> (iter) #<eof> gosh> (iter) #<eof>
木をトラバースしてそれぞれの葉に対してfを適用するfor-each-leaf:
(define (for-each-leaf f tree)
(match tree
[(x . y) (for-each-leaf f x) (for-each-leaf f y)]
[x (f x)]))
反転してみる。
gosh> (define iter2 ((inv for-each-leaf) '((1 . 2) . (3 . 4)))) iter2 gosh> (iter2) 1 gosh> (iter2) 2 gosh> (iter2) 3 gosh> (iter2) 4 gosh> (iter2) #<eof>
util.combinationsのpermutations-for-eachの反転なんかは パズルソルバ系で使えるかも?
gosh> (define next-permutation ((inv permutations-for-each) '(a b c))) next-permutation gosh> (next-permutation) (a b c) gosh> (next-permutation) (a c b) gosh> (next-permutation) (b a c) gosh> (next-permutation) (b c a) gosh> (next-permutation) (c a b) gosh> (next-permutation) (c b a) gosh> (next-permutation) #<eof>
び(2010/08/13 02:33:16 PDT): いやーこれ便利ですね。んで、複数の外部イテレータをマージできると便利なんじゃないだろうかと思って書いてみましたので、貼っておきます。でも、もっと効率のいい実装があるんじゃないかなー??
(define (merge-generators cmp . gens)
(define (invoke-generators proc cmp . gens)
(define (value-with-index cmp seq)
(receive (_ v i)
(fold3 (lambda (v idx pred-value pred-idx)
(cond
((eof-object? pred-value) (values (+ 1 idx) v idx))
((eof-object? v) (values (+ 1 idx) pred-value pred-idx))
((cmp v pred-value) (values (+ 1 idx) v idx))
(else (values (+ 1 idx) pred-value pred-idx))))
0 (eof-object) 0
seq)
(values v i)))
(let* ((gens (list->vector gens))
(result (map-to <vector> (lambda (gen) (gen)) gens)))
(let/cc break
(do () (#f)
(receive (v i) (value-with-index cmp result)
(cond ((eof-object? v) (break))
(else
(proc v)
(vector-set! result i ((vector-ref gens i))))))))))
(define (continue)
(reset (apply invoke-generators
(lambda (v) (shift k (set! continue k) v)) cmp gens)
(eof-object)))
(lambda () (continue)))
Tags: 継続, 部分継続, gauche.partcont, ジェネレータ, generator