Simple and Efficient Purely Functional Queues and Dequesを読む

(ここ数日、眠れない。)

• http://citeseer.ist.psu.edu/158610.html

を読んだ。FIFOのキューをリスト二つで実装するというもの。普通のリストでのからlazyリストでのやり方へ。

new = ([], [])

insert e (l, r) = (l, e:r)

remove ([], r) = remove (reverse r, [])
remove (e:l, r) = (e, (l, r))

問題はremove時、reverseのあるなしで時間が変わること。そこでバランスをとるようにしたのが、次のバージョン。

new = ([],[])

insert e (l, r) = makeq (l, e:r)

remove (e:l, r) = (e, makeq (l, r))

makeq (l, r) = if (length r) == (length l) + 1 then
                   (rot (l, r, []), [])
               else
                   (l, r)

rot ([], e:r, a) = e:a
rot (hl:tl, hr:tr, a) = hl:(rot (tl, tr, hr:a))

insert時にlとrの大きさが同じくらいになったとき、lに遅延リストrotとしてまとめている。

その次のは遅延リスト中の各要素の確定を各操作で行う、つまりmakeqのたびに遅延リストrotの1要素をeagerするような実装。3つ目のL'は各makeqでtailしていくためだけにあり、空になったら新たにrotでLをつくりなおし、L'にも入れている。

最後のはそれを前後から挿入削除するのに対応させた実装。