K.Maebashi's BBS

土曜はとあるイベントにて大阪で飲んだくれておりまして、ずいぶん返事が遅くなりまして すみません。 それプラス、私自身、クロージャに慣れておらず継続もわかっておらず、今回のNykRさんの サンプルはずいぶん荷が重いものでした。とはいえ放り出していては勉強にならんので、 私なりに解釈してみました。間違い等ありましたらご指摘ください。 さて、単に木をイテレートするだけなら、 tree.each(closure(item) { # このitemについてなんかする }); という形のeachメソッドをツリーに装備するのは簡単で、ツリーの中で再帰して、 要素ごとに、渡されたクロージャを呼び出せばよいのですが、こういう形式(内部イテレータ) だと、あるツリーについて、「ここまで走査した」という状態を保存しておけないのが 問題になるわけですよね。その点、NykRさんの提示されたイテレータでは、こういう 書き方も許される。 # ふたつのイテレータでツリーを並列に走査する。 for (ite1 = iterator_GoF(foreachTree_CPS(tr)), ite2 = iterator_GoF(foreachTree_CPS(tr)); !ite1.isDone() && !ite2.isDone(); ite1.next(), ite2.next()) { print(" " + ite1.currentItem()); print(" " + ite2.currentItem()); } これができるのが外部イテレータの強みです。 Cなどで、再帰を使ってツリーを辿る場合、「ここまで走査した」という情報がスタック上に ありますから、スタックが1本しかない以上、ふたつのイテレータを並行して使うことは できないわけです(片方が片方の繰り返しに完全に含まれるなら可能)。 tr = {13,{5,{3,{},{}},{13,{12,{},{}},{}}},{16,{16,{15,{},{}},{}},{17,{},{}}}}; この例では、nodeの[0]にそのノードの値が、[1]に左の子が、[2]に右の子が 入っていますから、再帰で間順で走査するなら以下のようになります。 function internalIterate(node) { if (node.size() == 0) { } else { internalIterate(node[1]); # ...(a) print(" " + node[0]); # とりあえず表示しておく internalIterate(node[2]); } } (a)の箇所で左の子について再帰呼び出しを行い、それが戻ってきてから続きの処理を やっています。「戻ってきてから続きの処理をやる」ことができるのが再帰の嬉しい ところですが、それを期待していては、外部イテレータは作れない。 そこで、「戻ってきてから続きの処理をする」のではなく、「戻ってきてから やってほしい続きの処理をクロージャとして渡す」とすれば、関数から戻ってこなくても よくなる。その変換をしたのがこれ。 function internalIterate(node, cont) { if (node.size() == 0) { cont(); } else { internalIterate(node[1], closure () { # 続きをクロージャで渡す。 print(" " + node[0]); internalIterate(node[2], cont); }); } } # 第2引数には「処理の続きを渡す」のだから、最後に「おしまい」と表示される。 internalIterate(tr, closure() {print("おしまい");}); さて、この状態では、要素ごとに行う処理がprint()に固定されていますから 汎用性がありません。では引数でなにか関数を渡せば、とこうしても、 internalIterate(node[1], closure () { # 続きをクロージャで渡す。 proc(node[0]); # 処理を引数procで渡す internalIterate(node[2], cont); }); これでは内部イテレータと同じですから意味がありません。 そこで、このproc()にも、続きの処理をクロージャで渡してやることにします。 function foreachTree_CPS(proc) { return closure internalIterate(node, cont) { if (node.size() == 0) { cont(); } else { internalIterate(node[1], closure () { proc(node[0], closure() { internalIterate(node[2], cont); }); }); } }; } 外部イテレータの場合、このprocの第2引数をnext()の際に呼び出せばよいわけですね。 なぜならそれが「処理の続き」だから。 イテレータはこうなります。 function iterator_GoF(foreach_CPS, collection) { this = new_object(); this.first = closure () { this.isDone = closure () { return false; }; foreach_CPS(closure (item, cont) { this.currentItem = closure () { return item; }; this.next = closure () { cont(); }; })(collection, closure(){ # ..(b) this.isDone = closure () { return true; }; }); }; this.first(); return this; } イテレータのfirst()が呼び出されたときに、foreach_CPS()を呼び出して、 internalIetrate()を取得し、それに対しcollectionとクロージャを渡しています(b)。 これがつまり元のソースの internalIterate(tr, closure() {print("おしまい");}); に相当するわけですが、「おしまい」と表示する代わりに、isDoneについて、 trueを返すよう関数を差し替えています。 んで、internalIterate()に渡しているproc()では、 this.currentItem = closure () { return item; }; this.next = closure () { cont(); }; currentItemを設定後、nextに対し、contすなわち「処理の続き」をセットしています。 これで、次に利用者がnext()を呼び出したとき、internalIteratorの続きが実行される、と。 NykRさんのソースとは微妙に変わっていますが、こんな解釈でよいでしょうか? # いやあ、実に勉強になりました。