[解決済み] Haskellでグラフはどのように表現するのか？

質問

haskellで代数的なデータ型を使ってツリーやリストを表現するのは簡単です。しかし、グラフをタイポグラフィで表現するにはどうしたらよいでしょうか？ポインタが必要なようです。次のようなものが考えられると思います。

type Nodetag = String
type Neighbours = [Nodetag]
data Node a = Node a Nodetag Neighbours

そしてそれは実行可能でしょう。構造内の異なるノード間のリンクは、リスト内の現在の前の要素と次の要素、またはツリー内のノードの親と子の間のリンクのように、実際には "feel" 固体化されていないように感じられます。私が定義したグラフで代数的な操作を行うことは、タグ システムを通じて導入された間接的なレベルによって、いくらか妨げられるだろうと直感しました。

私がこの質問をすることになったのは、主にこの疑問と非屈折の知覚のためです。Haskell でグラフを定義する、より良い、より数学的にエレガントな方法はあるのでしょうか。それとも、何か本質的に難しいこと、基本的なことに出くわしてしまったのだろうか？再帰的なデータ構造は素晴らしいが、これは何か違うような気がする。木やリストが自己言及的であるのとは別の意味で、自己言及的なデータ構造だ。リストとツリーは型レベルで自己言及的ですが、グラフは値レベルで自己言及的であるようなものです。

では、実際のところはどうなのでしょうか？

どうすれば解決するのか？

私はまた、純粋な言語でサイクルを持つデータ構造を表現しようとするのは厄介だと感じています。値は共有できるので、型のメンバーを含むことができる任意の ADT (リストやツリーを含む) は、実際には DAG (Directed Acyclic Graph) です。根本的な問題は、もしAという値とBという値があり、AはBを含み、BはAを含むとしたら、どちらも他方が存在する前に作ることはできない、ということです。Haskell は怠け者なので、次のようなトリックを使うことができます。 結び目 というトリックを使ってこれを回避することができますが、これは私の脳を痛めます（まだあまりやっていないからです）。私はこれまでHaskellよりもMercuryで実質的なプログラミングを行ってきましたが、Mercuryは厳格なのでノットタイイングは役に立ちません。

多くの場合、ID から実際の要素へのマップを使用し、要素に他の要素への参照ではなく ID への参照を持たせることで、提案されているような追加の間接化を行いました。私がこの方法を好まないのは（明らかに非効率であることは別として）、存在しないidを探したり、同じidを複数の要素に割り当てようとするとエラーが発生する可能性があるため、もろさを感じるからです。もちろん、これらのエラーが発生しないようにコードを書くことはできますし、 抽象化されたコードに隠して、このようなエラーが発生する唯一の場所である が発生する可能性があるのは が発生する場所だけが限定されるように抽象化することもできます。しかし、それでも間違うことがもうひとつあるのです。

しかし、"Haskell graph"でググると、以下のように出てきました。 http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Practical_Graph_Handling に行き着きましたが、これは読み応えがありそうです。