ATS2の依存型を使ってAVL木 | κeenのHappy Hacκing Blogκeenです。少しばかりATS2を触ってみたので成果報告でも。 AVL木は左右のノードの高さが高々1しか違わない平衡二分木です。OCamlやSMLでナイーブに実装すると本当に1しか違わないことを保証するのは難しく、精々テストなどで部分的に検査するだけです。 ところがSMLに似た文法を持つATS2には依存型があり、左右のノードの高さが高々1しか違わないことを型で保証出来ます。 つまり、左右のノードの高さが2以上違う木を作ろうとしてもコンパイルエラーになるのでコンパイルが通れば高さについてはバグがないこと保証されます。 そういうAVL木を使ってTreeSetを作ってみたので紹介します。 私のブログ(のこの記事)の読者ならATS2も依存型もAVL木も知ってそうですが一応説明します。 ATS2って何? 詳しい説明は日本ATSユーザグループに譲るとして、この記事にて重要な点を挙げます。 SMLに似た
