20分でわかる
Purely Functional
Data Structuresk.inaba (http://www.kmonos.net/)
Apr. 4, 2010

あらすじ
遅デ イ
い ーミ
タュー
構タ造ブ
はル

Immutable Object だけで作るデータ構造

この本の内 容を全速力で布教する

お題：キュー (Queue)• FIFO (First-In First-Out)• pushBack(e) でデータeを入れる• popFront() で取り出せる• 入れた順に出てくる
• 以上

代入

Immutable Object でない
打倒すべき目標

破壊的キュー手続き型でよくあるinterface Queue<E>{void pushBack(E e);E
popFront();}よくある実装
class HakaiQueue<E> implements Queue<E> {class Cell { E e; Cell next; }Cell fst, last;void pushBack(E e){last=last.next=new Cell(e,null);}
E popFront(){E e=fst.e; fst=fst.next; return e;}
}

1

2

3 ・

4 ・

破壊的キューの特徴• Mutable Object を使用– リスト末尾を指すポインタをもっておき末尾のセルを pushBack 時に書換

1

2

3 ・

• Persistent でない– 操作前の状態をとっておくには全コピーしかない

4 ・HakaiQueue<E> q = 略;
HakaiQueue<E> p = q;
q.pushBack(e); //pも変化!

• pushBack, popFront の最悪実行時間は O(1)Ephemeral (儚い)使い方での計算量(比較対象)

計算量

破壊的 2リスト 銀行家

A

儚 W

永O(1)

実時間

Amortized(償却)計算量

O(1)Worst-Case(最悪)計算量

An/a

Persistent (永続的な)使い方での計算量

Wn/a

詳しくはあとで償却計算量！

Immutable な実装

2リストキュー

非破壊的キュー• フィールドの書き換えを使わないキュー• pushBack, popFront は「操作後のキュー」
を別のオブジェクトを作って返す
interface ImuQueue<E>{ImuQueue<E>
pushBack(E e);
Pair<E,ImuQueue<E>> popFront();}

非破壊キュー
• 単純にやると全コピー：計算量 O(n)

1
コピー

13 ・

2

コピー

コピー

24 ・

34 ・

２リストキュー• ちょっと工夫• キューの後ろの方は逆順で持つ– pushBack がリスト先頭への追加なのでO(1)に！
1

2

54 ・data Queue a = Q [a] [a]3 ・--ここからコードはHaskellです

pushBack (Q front rear) e = Q front (e:rear)
popFront (Q []r) = popFront (Q (reverse r) [])popFront (Q (e:f) r) = (e, Q f r)

２リストキューの特徴• front側とrear側の２つのリストで表現• len(front) == 0 になったら rear を reverse
1

2

5

4 ・

3 ・

• Persistent である• 最悪実行時間は、reverseが発生する瞬間 O(n)• でも、償却実行時間は O(1)– なので、トータルの実行時間的に考えると計算時間は O(1) と思って問題ない！

償却計算量とは？
操作列全体でコストを平均化して見たときの計算量• pushBack 1  [] [1]• pushBack 2  [] [2,1]• pushBack 3  [] [3,2,1]• popFront [1,2,3] []  [2,3] []• popFront [3] []
reverseは「たまにしか」• pushBack 4  [3] [4]起きない• popFront [] [4]時間 t かかるreverseが• popFront [4] []  [] [] 発生する前に、必ずt 回 pushBack している

償却計算量とは？
時間 t かかるreverseが発生する前に、必ずt 回 pushBack している
•
•
•
•
•
•
•
•
•

現実の計算量分担をごまかした計算量

pushBack
1
popFront(軽) 1
popFront (重) t+1

pushBack2
popFront(軽) 1
popFront (重) 1

pushBack 1  [] [1]
pushBack 2  [] [2,1]pushBack 3  [] [3,2,1]
popFront [1,2,3] []  [2,3] []popFront
 [3] []
pushBack 4  [3] [4]popFront
 [] [4]popFront
 [4] []  [] []
合計

1
1
13+1
1
1
1
1+1
12

2
2
2
1
12
1
112

こう思えば
全部 O(1) だし
トータル計算量も変わらないので問題ない！

計算量(比較対象)

破壊的 2リスト 銀行家

O(1)

O(1)

O(1)

O(n)

An/aO(n)Wn/aO(n)

A

儚 W

永実時間

!?

キ 2
ュ リース
トブートストラップキュー

実時間
キュー

銀行家キュー

銀行家キュー

２リストキューは本当に• Persistent と言えるのか？？？
–Persistent なら、同じバージョンを取っておいて何回も使えるはず
let q = loadSomeQueue () in… (doHoge q) … (doFuga q) …
(doPiyo q) … (doHige q) …

破滅的な例• reverseが起きる寸前のキューを何回も使う
let q = needReverseQueue () in… (popFront q) … (popFront q) …
(popFront q) … (popFront q) …

ごまかしきれてない• reverseが起きる寸前のキューを何回も使う
let q = pushFront (pushFront (pushFront(Queue [] []) 1) 2) 3

in … (popFront q) … (popFront q) …
(popFront q) … (popFront q) …
実際の計算時間は1*3+4*4 = 19 ！

計算時間は 2*3+4 = 10 です！
現実の計算量分担をごまかした計算量

pushBack
1
popFront(軽) 1
popFront (重) 1+t

pushBack
2
popFront(軽) 1
popFront (重) 1

どうしましょう• Persistent な使い方（同じバージョンを何回も使い回す）をしても償却計算量をO(1)にするには？

さらなる工夫• len(front)==0 になったら reverse• len(front)+1 == len(rear) になったら遅延評価で reverse
fr

1

2

5

4frontの方が短くなったら早めのreverse

3 ・data Queue a = Q [a] Int [a] Int
pushBack(Q f fl r rl) e = chk (Q f fl (e:r) (rl+1))
popFront(Q (e:f) fl r rl)= (e, chk (Q f (fl-1) r rl))さらなる工夫• len(front)+1 == len(rear) になったら遅延評価で reverse
data Queue a = Q [a] Int [a] Int
pushBack(Q f fl r rl) e = chk (Q f fl (e:r) (rl+1))
popFront(Q (e:f) fl r rl)= (e, chk (Q f (fl-1) r rl))chk (Q f fl r rl) =if fl+1 == rl then (Q (f++reverse r) (fl+rl) [] 0)else (Q f fl r rl)
Haskellなのでデフォルト遅延特徴• front側とrear側の２つのリストで表現– len(front)+1 == len(rear) になったら遅延 reverse

fr

1

2

543 ・

• Persistent である• 最悪実行時間は、reverseが発生するとき O(n)• 償却実行時間は (persistentな使い方でも) O(1)

計算量の見積もり方
積み立て金メソッド「時間tかかるreverseの前に必ずt回pushBackしてる」
 「pushBackのコストを 2 にして、先にreverseの負担の分を払っておけばOK」

から借金メソッド へ「早めの遅延評価reverseしておけば、値が本当に必要になるまでに時間がある」
 「本当に必要になる支払期限までに、t 回のpopFrontで負担金を用意できれば問題ない」

償却計算量とは？
長さtのreverse結果が必要となるまでにt回はpopFrontするはず•
•
•
••
•
•
•
•

現実の計算量pushBack
1
popFront(軽) 1popFront (重) x+1

pushBack 1  [] [1]  []r[1] []pushBack 2  []r[1] [2]pushBack 3  []r[1] [3,2]  []r[1]r[3,2] []popFront
 r[1]実行  r[3,2] []popFront
 r[3,2]実行  [3] []pushBack 4  [3] [4]popFront
 [] [4]  []r[4] []popFront
 r[4]実行  [] []合計

分担をごまかした計算量

pushBack
popFront
1
1
1
1+12+1
1
1
1+1
12

1
1122
122
1212

少し大きい例：pushBack 1～15
• [][1]  []r[1] []• []r[1][2]• []r[1][3,2]  []r[1]r[3,2] []• []r[1]r[3,2] [4]• []r[1]r[3,2] [5,4]• []r[1]r[3,2] [6,5,4]• []r[1]r[3,2] [7,6,5,4]  []r[1]r[3,2]r[7..4] []• …
• []r[1]r[3,2]r[7..4] [15..8]  []r[1]r[3,2]r[7..4]r[15..8] []popFront• [] [1]  []r[1] []• []r[1] [3,2]  []r[1]r[3,2] []• []r[1]r[3,2] [7,6,5,4]  []r[1]r[3,2]r[7..4] []• []r[1]r[3,2]r[7..4] [15..8]  []r[1]r[3,2]r[7..4]r[15..8] []• popFront: r[1]実行  r[3,2]r[7..4]r[15..8] 1+1• popFront: r[3,2]実行  [3]r[7..4]r[15..8] 1+1• popFront: r[7..4]r[15..8]
1+1• popFront: r[7..4]実行  [5,6,7]r[15..8]
1+1• popFront: [6,7]r[15..8]
1+1• popFront: [7]r[15..8]
1+1• popFront: r[15..8]
1+1
借金返済• popFront: r[15..8]実行  [9..15]
1+1
間に合ってるなぜ借金メソッド？
• 積立金は一度使うとなくなるけどlet q = pushFront (pushFront (pushFront 3億円貯金(Queue [] []) 1) 2) 3

in … (popFront q) … (popFront q) …
revに(popFront q) … (popFront q) …

3億円使う

revに3億円使う

revに3億円使う

revに3億円使う

なぜ借金メソッド？
• 借金は、一度返せば大丈夫！
– 遅延評価でメモ化されてるから15億円借金

let q = []r[1]r[3,2]r[7..4][15..8] []in … (popFront q) … (popFront q) …
rev実行 (popFront q) … (popFront q) …
返済

メモ化
されてるのでもうrev不要

メモ化
されてるのでもうrev不要

メモ化
されてるのでもうrev不要計算量(比較対象)

破壊的 2リスト 銀行家

O(1)

O(1)

O(1)

O(1)

O(n)

O(n)

A

n/aO(n)O(1)Wn/aO(n)

O(n)

A

儚 W

永実時間

※注釈
• 銀行家キューという名前はなんですか– 償却計算量の評価の方法として（Functional
データ構造に限らず一般の話として）• 銀行家 (Banker) の方法• 物理学者 (Phyisicist) の方法– の二つがあって、その「銀行家の方法」で設計したキューという意味だそうです。

• 本には両方の手法が紹介されています悪計算量

実時間キュー

定数

…
• 償却計算量とはなんだったのか
分担をごまかした計算量

pushBack2
popFront(軽) 1
popFront (重) 1

こう思えば
全部 O(1) だしトータル計算量も変わらないので問題ない！

• 仮想的に「積立金」や「借金」を考え仮想的に返済する

仮想世界を現実にする
popFront で、仮想的にではなく実際に「借金」を返す＝
popFront のたびに、reverse 処理を実際に「ちょっとずつ実行」する

やりかた
１： 借金ポインターを追加（遅延評価サンクを指しておく）
data Queue a = Q [a] Int [a] Int [a]pushBack(Q f fl r rl s) e
= seq chk (Q f fl (e:r) (rl+1) s)
popFront(Q (e:f) fl r rl s)= (e, seq chk (Q f (fl-1) r rl s))

２： chk 関数はreverseチェックのついでに無駄に遅延サンクをちょっとづつ実行（chk自体は遅延しないようにeager実行）やりかた
2.1： 借金ポインタに対してパターンマッチ＝ consセル１個分だけ実行される
chk (Q f fl r rl (_:s)) = (Q f fl r rl s)chk (Q f fl r rl []) =-- 実は fl+1 == rl のときだけこっちに来る
let ff = rotate f r [] in(Q ff (fl+rl) [] 0 ff)

2.2：rotate xs ys zs は xs++rev ys++zs する関数
rotate [] (y:_) zs= y : zs
rotate (x:xs) (y:ys) ff =「セル１個だけ実行」
x : rotate xs ys (y:zs)
しやすいreverse計算量(比較対象)

破壊的 2リスト 銀行家

実時間

O(1)

O(1)

O(1)

O(1)

O(1)

O(n)

O(n)

O(1)

An/a

O(n)

O(1)

O(1)

Wn/aO(n)

O(n)

O(1)

A

儚 W永ニュー
メリ
カル
表現の再帰多相再帰

そのほかの話題ブートス
トデラーッ タプ構造ス
ローダウンが目次（紹介した部分）• 2～3章 :: 簡単な関数型データ構造の紹介– 2リストキュー、赤黒木、二項ヒープ、…

• 4章 :: 遅延評価とは• 5章 :: 償却計算量とは• 6章:: 遅延評価を駆使して、永続性と償却計算量を両立（キュー, ヒープ, …）• 7章:: リアルタイム化（キュー, ヒープ, …）• 8～11章 :: 関数型データ構造汎用技法集– 「n進数表記に学ぶ」「ブートストラップ」「再帰スローダウン」

あとはみんなを読もう！

THANK YOU FOR LISTENING!

※スライド内の漫画はすべて増田こうすけ「増田こうすけ劇場 ギャグマンガ日和 （巻の５） 」 からの引用です。