Scheme:部分継続:イテレータの反転

0.9.3に入ったgeneratorについてはGauche:Generatorにまとめます。

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)))

Scheme:generatorとdoとwhile

Tags: 継続, 部分継続, gauche.partcont, ジェネレータ, generator