haskell - 如何在 Haskell 中表示图表？

Question

使用代数数据类型在 haskell 中表示树或列表非常容易。但是您将如何以打印方式表示图表呢？看来还需要高人指点。我猜你可能有类似的东西

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

那是可行的。然而，感觉有点脱钩；结构中不同节点之间的链接实际上并不“感觉”像列表中当前上一个和下一个元素之间的链接或树中节点的父节点和子节点之间的链接一样牢固。我有一种预感，按照我的定义对图进行代数操作会受到通过标签系统引入的间接级别的阻碍。

主要是这种怀疑感和不优雅的感觉导致我问这个问题。在 Haskell 中是否有更好/更数学优雅的方式来定义图？或者我偶然发现了一些本质上困难/基本的东西？递归数据结构很不错，但这似乎是另一回事。与树和列表的自引用方式不同的自引用数据结构。就像列表和树在类型级别上是自引用的一样，但图形在值级别上是自引用的。

那么到底发生了什么？

Answer 1

在 shang 的回答中，您可以看到如何使用惰性来表示图表。这些表示的问题在于它们很难改变。仅当您要构建一次图表并且此后它永远不会改变时，打结技巧才有用。

在实践中，如果我真的想用我的图表做一些事情，我会使用更简单的表示:

• 边缘列表
• 邻接列表
• 为每个节点赋予唯一的标签，使用标签而不是指针，并保持从标签到节点的有限映射

如果您要经常更改或编辑图表，我建议使用基于 Huet zipper 的表示。这是 GHC 内部使用的控制流图表示形式。您可以在这里阅读:

• An Applicative Control-Flow Graph based on Huet's Zipper

• Hoopl: A Modular, Reusable Library for Dataflow Analysis and Transformation