手を動かしたい気分だったのでだいぶ後回しになっていたPFDS (Purely Functional Data Structure, 純粋関数型データ構造)を読みながらScalaで実装を後追いしてみた。*1
少し時間がかかったがRedBlackTreeやTrieといった有名な物から、HoodMelvilleQueueやそれを利用したCatenableListなどちょっとおしゃれ（？）なデータ構造についての実装・計算量についての考え方を学ぶことができた。
本の前半はストーリーがあって、「永続的なデータ構造だと計算効率が悪い場合が多い！・・・が！償却計算量の考え方を使いながら実装を工夫していくと短命なデータ構造と同じくらいの性能が出る。（全てではないが償却だけでなく最悪計算量についても同じくらいにできるケースも多い）」ことを確認する旅になる。 軽くまとめてみたので興味がある人はちら見しつつ、実際に本を購入して読んでみてほしい。 https://gist.github.com/matsu-chara/75dd80e36172569343738153d0123bf2
後半は様々なデータ構造を設計するための考え方がまとまっている。 こちらについても雑多になっているわけではなく、前半の考え方（実装方法・計算量の証明方法）を踏襲しつつ、一個ずつ積み重ねになっているので読み応えがある。
2進数のゼロ無し表現というものが途中に出てくる。 これは以下のように普通の２進数では {0,1}で書くところを {1,2}を使って書く記法のことだ。
1,2,3,4,5 は 1, 2, 11, 21, 12, 22, 111 となる。 - 各桁が2^iを表すのは普通の2進数と同じ。 - 0を使わないのが前提になるので、ある数を表す表現は一位に定まる
一見特に意味のない記法に思えるが、これが記数法表現に基づくデータ構造の計算量の削減に役立つというのはなかなか面白かった。 気になる人は https://gist.github.com/matsu-chara/03fef6b59f60fefd5d052704cd578ac7 に概要をまとめたので読んでみて興味があれば本を買ってみてほしい。（ちなみにgistの内容の正確性については保証できない）
2-3 finger tree
2-3 finger treeといえばHaskellのData.Sequenceにも使われている（償却）計算量の優れたDequeだ。（追加・削除ともに償却定数時間で実行可能）
これはPFDSには載っていないが、ベースとなる 記数法表現 や 暗黙再帰減速 の考え方・実装の勘所はPFDSで学ぶ事ができる。*2
読み終わったあとにwikipediaを開いてみたら、以前なんとなく理解していた物よりはるかに解像度高く理解できたので勢い余って実装してみた。*3
https://github.com/matsu-chara/finger_scala
とはいえ、finger treeの実装は世界に一億個くらいありそうなので特に自慢にもならないし、パフォーマンスやメソッドの豊富さよりはわかりやすさを重視している。(が、やはりこういうのは自分で実装してみると理解度が違うと思う。）
ちなみに実用的なFingerTreeに関してはscalazの物などがおすすめ
wikipediaにあるシナリオ 通りのテストを書いてみたがいい感じな見た目になったので記念スクショを貼って終わりとする
next
本を読むなかでscalaでの実装をいくつかあたっていたところ以下のように、いくつかの実装には論文へのリンクがついていた。
読む予定があるわけじゃないけどscala collectionのコメントにある論文を集めてみた
— まっちゃら (@matsu_chara) 2019年7月14日
ConcurrentTrie https://t.co/OYzQCB4Tjw
HashMap https://t.co/5ppRtytUFP
IntMap https://t.co/4gHFDLyHH4
RedBlackhttps://t.co/p5eEjsp9xD
RedBlack https://t.co/qWa2cqPtkQ
RedBlack https://t.co/FFIBO49Ay1
PFDSでカバーされている物もややありそうだけど面白そうなのでいつか読みたい。（けどパタヘネ読み始めた）
