Chris Okasaki の Purely Functional Data Structures という本を買ってみました。これは、副作用を使わないでいろいろなデータ構造のアルゴリズムを実装するという大変面白い本で、これを読むと、副作用無しで○○が出来るわけがない!という時の○○がだいぶ減ると思います。 サンプルは Standard ML で書かれているのですが、良くわからないのでHaskell で書き直しながら読んでみます(巻末に Haskell での実装例が載ってるけど見ないふり)。 17 ページに Heap というコレクションが紹介されています。これは次の性質をもったコレクションです。 要素は大小関係を持つオブジェクト。 最小の要素だけを取り出す事が出来る。 ようするにあるリストをソートして最小の奴を取り出したいという場合、取り出す物が最小の物だけならばソートするより効率の良い方法
![Leftist Heap - 言語ゲーム](https://cdn-ak-scissors.b.st-hatena.com/image/square/a5d5ae7ee2a305ea4fc295eb0927e0d2d76eec00/height=288;version=1;width=512/http%3A%2F%2Ffarm3.static.flickr.com%2F2598%2F4126550033_c185d04672.jpg)