『純粋関数型データ構造』

章ごとのテーマ

6章

キーワード:

7章

償却計算量だと、最悪ケースではけっこう計算量かかってしまうこともあるので、最悪ケースでもある程度いい計算量にしよう

キーワード: スケジュール

8章

いままでやってきたことに名前をつけた感じ？

キーワード: 一括再構築、全域再構築、遅延再構築、両端キュー

用語メモ

物理学者法

ポテンシャルの差分を考えるやつ

ポテンシャルの決め方が重要

銀行家法

累積貯蓄・累積負債を考えるやつ

負債の決め方が重要

直接そのノードを操作するときにはそのノードの負債は0になっている必要がある

負債不変条件を破らないようにする (一定以上負債がたまらないようにする)

$(...)

このなかの計算はすぐには計算しません、というやつ

$f x

$(f x) の構文糖衣

x は直ちには評価されない

停止リスト

遅延リストのこと (not ストリーム)

停止計算

後回しされた計算。サンク？

非共有コスト

入力に残っている停止計算を全部やってしまったと仮定して、その操作の実行にかかる実際の時間

共有コスト

入力に残っている停止計算を全部やってしまったと仮定して、その操作が生成した停止計算のコスト

完全コスト

入力に残っている停止計算を全部やってしまったと仮定して、その操作を停止計算も全部計算したときのコスト

遅延評価を正格評価に置き換えたときに、その操作の実コスト

完全コスト = 共有コスト + 非共有コスト

進行させる

停止計算を計算すること

償却コスト

銀行家法: 償却コスト = 非共有コスト + 返済した負債

物理学者法: 償却コスト = 完全コスト - ポテンシャルの差

償却データ構造

最悪時データ構造

本質的コスト

非共有コストと似ている

スケジュール

遅延されているデータのポインタ

操作毎に計算を進めることで、メモ化しておく

一括再構築

一気に再構築する (木であれば平衡状態にする)

全域再構築

計算途中の状態をデータ構造の中に持っておいて、操作毎に少しずつ再構築の計算を進めていく

遅延再構築

全域再構築と似ているが、遅延評価を使って少しずつ再構築の計算を進めていく

6

6.4

6.4.2

フロント側をキャッシュしている感じ

定理6.2

2と4の単位は？

snoc の完全コスト、1なの？比較とか関数呼び出しとかしてるけど？実ステップ数じゃないのだろうか

結果的なキューのポテンシャルは2mである

がわからない。2m+1では？

=> 2m は 2|w| のことだった。2|w| (= 2m) のほうが |f| - |r| (=2m+1) よりも必ず小さくなるため。

演習6.6

(b)

check の force f のところで、tl を k 回する (いままで tl をしていなかった分、一気にやる)

こうすると、非共有コストが 1 + k とかになり、償却コストも k とかそのへんになってしまう

6.4.3

型が変わるポテンシャルの差の計算が謎

7

償却データ構造だと、均したらいいけど最悪ケースはめっちゃ時間かかることもある

リアルタイムシステムみたいなデッドラインがあるようなやつだと適さない

債務を返済するときに実際にも計算を進めたったらいいんじゃね？ということでそういうことをする

スケジュールという

このようなデータ構造を最悪時データ構造という

償却データ構造を最悪時データ構造に変換する

第一のステップ

すべての停止計算の本質的コストを所望の上限以下に抑えること

O(1) にしたいなら O(1) 以下、O(log n) にしたいなら O(log n) 以下にする

第二のステップ

進行の連鎖を避けること (一気に計算が走って最悪ケースが)

スケジュールという停止計算をデータ構造に足して、操作するたびその計算をいくつか進めていく

再帰の Acc みたいなイメージを持った

データ保持部分にもスケジュールと同じポインタを指すようなものを入れているので、スケジュールの計算を進行させると、本来のデータの計算も進んでメモ化されることになる

7.2

7.3

数字: Digit 型の値のこと

長さは exec するごとに減っていく

完成ゼロ: ストリーム中の評価済みの Zero (範囲中のゼロではないので注意。というか範囲外のゼロを完成ゼロと言う)

定理7.1

range が2つできるまでのことが書かれていないがこれも証明する必要がある気がする

基本的には m=0, m=1, m=2以上 の場合分けで OK なはず

range なし

m=0:

8

再構築

いい状態に構築し直す

二分木であれば平衡にし直す、とか

一括再構築

何回かの操作につき一回再構築する

再構築しないとどんどん各操作のコストが増えてしまうけど、操作の度に再構築するのもコストがかかるので、何回かに一回やって均せばOKというやつ

全域再構築

内部状態を表す代数的データ型を作って、正格に評価しつつ操作毎に内部状態の計算 (再構築) を少しずつ進めていく

遅延再構築

遅延評価を使ってちょっとずつ進める。6章。でも償却計算量でしかはかれない。

最悪計算量に対しても使うなら、7章でやったスケジュール化を使う。

8.4.3

ゆえに、最初の rotateRev の呼び出しの時点では |r| = c|f| + 1 + k − (j mod c) となっている。

紛らわしいので rotateRev の呼び出しの時点での front 側を f', rear側を r' とする。rotateDrop の最初は f と r とする。

check の条件から |r| = c|f| + 1 + k で、 |r| - |r'| - j mod c = c(|f| - |f'|) なので、整理すると上の式になる

|r| ≥ c|f| だと決め打ってしまえると話が簡単 になる

なんで簡単なのかわからないけど、|r| >= c|f| だと rotateRev で r が Nil になるパターンを考えなくていい (省ける) というだけなのかもしれない

head とか考えると、f のほうが早く終わっていてほしい？

これは c < 4 のときにしか保証されない

1 + k − ( j mod c) ≥ 0 で、任意の k について成り立たせたいので、正の部分 (1 + k) が一番小さくなるときだけ考えればよく、1 <= k であるため k = 1 のときだけ考える。このとき、j mod c は 2以下になれば全体で0以上になるので、そのためには c <= 3 になればいい

今や drop や reverse の引数のサイズには上限があり、

rotateRev で reverse r してるじゃん、と思ったけど、この時点では r は 1 + k - (j mod c) しか残っておらず、これは定数