手を動かしたい気分だったのでだいぶ後回しになっていたPFDS (Purely Functional Data Structure, 純粋関数型データ構造)を読みながらScalaで実装を後追いしてみた。*1 少し時間がかかったがRedBlackTreeやTrieといった有名な物から、HoodMelvilleQueueやそれを利用したCatenableListなどちょっとおしゃれ（？）なデータ構造についての実装・計算量についての考え方を学ぶことができた。 本の前半はストーリーがあって、「永続的なデータ構造だと計算効率が悪い場合が多い！・・・が！償却計算量の考え方を使いながら実装を工夫していくと短命なデータ構造と同じくらいの性能が出る。（全てではないが償却だけでなく最悪計算量についても同じくらいにできるケースも多い）」ことを確認する旅になる。 軽くまとめてみたので興味がある人はちら見しつつ、実際