■

やっとちょっとやる気が出てきたのでガリガリ進めてるですよ。でも凝り性 *など* (←重要)が災いして進行速度は人並以下ですよ。春休み中に終わるかしら。とりあえず本日の無駄時間:

((a b ...) ...)

というpatternに

((0 1) (2 3 4) (5) (6 7))

というのを食べさせたときのbの束縛を考える。順にmatchしていくに従って

(0        (1))
 ^aの部分 ^bの部分
(2 (3 4))
(5 ())
(6 (7))

とひとつずつsubform mappingが与えられて、それを最終的に

((a b)
 ((0 2 5 6)
  ((1) (3 4) () (7))
  ))

という並行listに収斂することになります。これを馬鹿正直に

step1: ((0 2) ((1) (3 4)))
step2: ((0 2 5) ((1) (3 4) ()))
step3: ((0 2 5 6) ((1) (3 4) () (7)))

としたのでは append 連打で遅く (O(n^2)に) なってしまうので却下です。List を前から作るといえば SigScheme では ScmQueue ですが、それを pattern variable の数だけ用意するのは無駄です。そこでよく使われる常套手段が逆向きに push していって reverse! ですが、最後の reverse! を map していくのも省略できまいかと思って一計を案じました。循環 list を作って尻尾だけ参照しておけば前から list を作りつつ、append は毎回 O(1) ではなかろうか、と。

step1: (#0=(2 0 . #0) #1=((1) (3 4) . #1))
step2: (#0=(5 0 2 . #0) #1=(() (1) (3 4) . #1))
step3: (#0=(6 0 2 5 . #0) #1=((7) (1) (3 4) () . #1))
step4: ((0 2 5 6) ((1) (3 4) () (7)))

で、大体できたあたりでちょっと効率計算をしてみました。Pattern variable の数を , 一つの pattern variable あたりの chain の長さを とすると、reverse! 戦略では memory access 回数は cell 一つあたり append 毎に push の為に一回 + slot 更新に一回、最後に reverse! で二回ずつなので合計 。循環list戦略では append あたり参照変更が二回 + slot 更新、最後に '() 付加、で合計 。

うーむ、きわい…
;; Code complexity の増加と天秤に掛けるとさらに痛い。
1.5 倍速ぐらいの感覚で妄想してたんだが…

ちなみにどの方法でも space complexity は最小 (無駄な cell は一つも消費されず) です。結局 reverse! の code の再利用性を考えて循環 list は没に。

とかこんな調子でやってるから三ヶ月もかかるんだよな…