Levelsモナドを使った幅優先探索の仕組み

Haskellは関数型プログラミング言語と呼ばれますが、関数だけでなく型も重要な役割を担っています。アルゴリズムを考える時、手続きの最適化だけでなく、正しいデータ型を選択することがシンプルなアルゴリズムを導き、実装をコンパクトにできるというのはよくある話です。今回は非常に単純な型でありながら幅優先探索というアルゴリズムのエッセンスを詰め込んだ Levelsというデータ型 について紹介したいと思います。 ピタゴラス数を列挙する ピタゴラス数とはピタゴラスの定理における関係式 a^2 + b^2 = c^2 を満たす自然数の三つ組です。 Haskellのリストは遅延評価なので 全ての自然数の三つ組を列挙する 列挙した自然数の中から関係式を満たすものだけ抽出する という手順でピタゴラス数を列挙することを考えてみましょう。 実際この方法は有限な探索範囲ではうまく機能します。 pyth :: [(I

[tackman]

“通常、幅優先探索を実装するためにはキューを使用する必要があり、手続き的な処理が多くなってしまうので簡潔に実装するのは難しい印象がありました”