你如何在Haskell中表示图形？ [英] How do you represent a graph in Haskell?

问题描述

使用代数数据类型在haskell中表示树或列表很容易。但是，你将如何去印刷代表图表？看来你需要有指针。我猜你可能有这样的东西：
$ b $

  type Nodetag = String 
类型Neighbors = [Nodetag] 
数据节点a =节点a节点标签邻居
  

这样可行。然而它感觉有点解耦;结构中的不同节点之间的链接并不像真正的感觉那样与列表中当前的前一个元素和下一个元素之间的链接，或者树中节点的父节点和子节点之间的链接。我有一个预感，在图上进行代数操作，因为我定义它会受到标签系统引入的间接级别的阻碍。

怀疑和不雅的感觉，导致我问这个问题。在Haskell中定义图形是否有更好/更好的数学优化方法？还是我偶然发现了一些本质上很难/根本的东西？递归数据结构是甜蜜的，但这似乎是别的。自我参照数据结构与树和列表是如何自我参照的意义不同。这就像列表和树在类型级别上是自引用的，但图表是在值级别上的自引用。

那么究竟发生了什么？

解决方案

我也觉得很难用纯语言来表示循环的数据结构。这是真正的问题的循环;因为值可以共享任何可以包含类型成员（包括列表和树）的ADT实际上是一个DAG（定向非循环图）。根本的问题是，如果你有值A和B，其中A包含B和B包含A，那么在另一个存在之前都不能创建。因为Haskell是懒惰的，所以你可以使用绑结来解决这个问题，但这会让我的大脑受伤（因为我还没有做太多）。到目前为止，我已经在Mercury中完成了比Haskell更多的实质性编程工作，而Mercury非常严格，所以打结无助。

通常当我运行在我刚刚采取额外的间接性之前，如你所暗示的那样;通常通过使用从ID到实际元素的映射，并且元素包含对ID的引用而不是其他元素。我不喜欢这样做的主要原因（除了显而易见的低效率之外）是感觉更加脆弱，引入了查找不存在的id或试图将同一id分配给多个id的可能错误元件。您可以编写代码，以便这些错误不会发生，当然，甚至可以将其隐藏在抽象之后，以便唯一可能发生此类错误的地方受到限制。但是，还有一件事是错的。

然而，一个用于Haskell图的快速谷歌让我转向了 http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Practical_Graph_Handling ，看起来很值得一读。

It's easy enough to represent a tree or list in haskell using algebraic data types. But how would you go about typographically representing a graph? It seems that you need to have pointers. I'm guessing you could have something like

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

And that would be workable. However it feels a bit decoupled; The links between different nodes in the structure don't really "feel" as solid as the links between the current previous and next elements in a list, or the parents and children of a node in a tree. I have a hunch that doing algebraic manipulations on the graph as I defined it would be somewhat hindered by the level of indirection introduced through the tag system.

It is primarily this feeling of doubt and perception of inelegance that causes me to ask this question. Is there a better/more mathematically elegant way of defining graphs in Haskell? Or have I stumbled upon something inherently hard/fundamental? Recursive data structures are sweet, but this seems to be something else. A self referential data structure in a different sense to how trees and lists are self referential. It's like lists and trees are self referential at the type level, but graphs are self referential at the value level.

So what's really going on?

解决方案

I also find it awkward to try to represent data structures with cycles in a pure language. It's the cycles that are really the problem; because values can be shared any ADT that can contain a member of the type (including lists and trees) is really a DAG (Directed Acyclic Graph). The fundamental issue is that if you have values A and B, with A containing B and B containing A, then neither can be created before the other exists. Because Haskell is lazy you can use a trick known as Tying the Knot to get around this, but that makes my brain hurt (because I haven't done much of it yet). I've done more of my substantial programming in Mercury than Haskell so far, and Mercury is strict so knot-tying doesn't help.

Usually when I've run into this before I've just resorted to additional indirection, as you're suggesting; often by using a map from ids to the actual elements, and having elements contain references to the ids instead of to other elements. The main thing I didn't like about doing that (aside from the obvious inefficiency) is that it felt more fragile, introducing the possible errors of looking up an id that doesn't exist or trying to assign the same id to more than one element. You can write code so that these errors won't occur, of course, and even hide it behind abstractions so that the only places where such errors could occur are bounded. But it's still one more thing to get wrong.

However, a quick google for "Haskell graph" led me to http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Practical_Graph_Handling, which looks like a worthwhile read.

这篇关于你如何在Haskell中表示图形？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！