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

问题描述

使用代数数据类型在 haskell 中表示树或列表很容易.但是，您将如何以排版方式表示图形?看来你需要有指点.我猜你可能有类似的东西

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.

主要是这种怀疑和不优雅的感觉促使我提出这个问题.在 Haskell 中是否有更好/更优雅的定义图形的方法?还是我偶然发现了一些本质上很难/基本的东西?递归数据结构很不错，但这似乎是另一回事.与树和列表如何自引用不同意义上的自引用数据结构.就像列表和树在类型级别上是自引用的，而图在值级别上是自引用的.

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.

到底发生了什么?

推荐答案

我也发现尝试用纯语言表示带有循环的数据结构很尴尬.真正的问题是周期；因为值可以共享任何可以包含类型(包括列表和树)的成员的 ADT 实际上是 DAG(有向无环图).根本问题是，如果您有值 A 和 B，其中 A 包含 B 且 B 包含 A，那么在另一个存在之前，两者都不能被创建.因为 Haskell 很懒，所以你可以使用一种叫做打结的技巧来解决这个问题，但这让我的大脑受伤(因为我还没有做太多).到目前为止，我在 Mercury 中完成的实质性编程比 Haskell 还多，而且 Mercury 很严格，所以打结也无济于事.

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.

通常当我遇到这种情况时，我才刚刚诉诸额外的间接访问，正如您所建议的那样；通常通过使用从 id 到实际元素的映射，并让元素包含对 id 而不是其他元素的引用.我不喜欢这样做的主要事情(除了明显的效率低下)是它感觉更脆弱，引入了查找不存在的 id 或尝试将相同的 id 分配给多个的可能错误元素.当然，您可以编写代码使这些错误不会发生，甚至将其隐藏在抽象之后，以便限制可能发生此类错误的唯一位置.但出错仍然是另一回事.

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.

但是，快速搜索Haskell 图"让我找到了 http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Practical_Graph_Handling，看起来值得一读.

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屋！