博士

やっほー、ロボ子！今日はHaskellの`fgl`ライブラリで迷路を自動生成する話を見つけたのじゃ。

ロボ子

Haskellで迷路ですか、面白そうですね！`fgl`というのは関数型グラフライブラリのことでしょうか？

博士

そうそう！その`fgl`を使って、グリッド状のグラフからランダム化された深さ優先探索（DFS）で迷路を作るらしいぞ。すべての壁があるグリッドから始めて、セルを選んで未訪問の隣接セルに移動して壁を取り除く、というステップを繰り返すのじゃ。

ロボ子

なるほど、DFSで全域木を生成するんですね。記事によると、グラフを帰納的なデータ型のように扱うとありますが、具体的にはどういうことですか？

博士

`matchAny`関数でグラフをノード、エッジ、残りのグラフに分割するらしいぞ。グラフを分解して処理していくイメージじゃな。

ロボ子

`Gr n e`型を使ってノードとエッジにラベルを付けるんですね。`mapNodes`関数でノードをマッピングしたり、`dfs`関数で深さ優先探索を実行したり…。`edfs`関数でエッジのリストを返すように`dfs`を修正するのもポイントですね。

博士

そう！`MonadRandom`クラスでランダム性を追加するのも忘れちゃいけないぞ。迷路生成にはランダム性が不可欠じゃからな。

ロボ子

エッジに壁の位置と方向のラベルを付けて、`mkGraph`関数で初期グラフを構築し、`edfsR`で壁を削除していくんですね。`Data.List`の`\\`演算子で描画する壁のリストを作成するのも興味深いです。

博士

`cairo`ライブラリで迷路を描画するのもおしゃれじゃな。この記事では、異なる形状のグラフから迷路を生成したり、Prim法やKruskal法などの異なるグラフアルゴリズムを使用したりする拡張も提案されているぞ。

ロボ子

迷路生成アルゴリズムは色々あるんですね。迷路って奥が深いですね！

博士

そうじゃな！ところでロボ子、迷路で道に迷ったらどうする？

ロボ子

えっと…、壁に手を当てて進むとか…ですか？

博士

ブー！正解は…、あきらめて家に帰る！…って、迷路の意味ないじゃん！