你如何在哈斯克尔表示一个图表？

使用代数数据类型在 haskell 中表示树或列表非常简单。但是如何进行排版来表示一个图形呢？看起来你需要一些指导。我猜你可能会有

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

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

主要是这种怀疑的感觉和对不雅的看法使我提出这个问题。在哈斯克尔，有没有一种更好、更精确的定义图形的数学方法？还是我偶然发现了某些本质上很难/基本的东西？递归数据结构很好，但这似乎是另一回事。一种自引用数据结构，在不同的意义上，树和列表是如何自引用的。就像列表和树在类型级别上是自引用的，但图在值级别上是自引用的。

到底怎么回事？

37822 次浏览
小开
最佳答案

我还发现尝试用纯语言表示带有循环的数据结构很困难。周期才是真正的问题所在，因为值可以被共享，任何包含类型成员(包括列表和树)的 ADT 实际上都是一个 DAG (有向无环图)。最根本的问题是，如果有值 A 和 B，其中 A 包含 B，B 包含 A，那么两个值都不能在另一个存在之前创建。因为 Haskell 很懒，所以你可以使用一个称为 结婚的技巧来解决这个问题，但是这会让我头疼(因为我还没有做过很多这样的事情)。到目前为止，我在 Mercury 上做的实质性编程比 Haskell 多，而 Mercury 是严格的，所以打结没有帮助。

通常，当我遇到这种情况之前，我会像您所建议的那样，采用附加的间接方式; 通常使用从 id 到实际元素的映射，并让元素包含对 id 的引用，而不是对其他元素的引用。我不喜欢这么做的主要原因(除了明显的低效之外)是它让人感觉更加脆弱，因为它可能会导致查找不存在的 id 或者试图将相同的 id 分配给多个元素的错误。当然，您可以编写代码使这些错误不会发生，甚至可以将其隐藏在抽象之后，以便这些错误发生的唯一位置 可以是有界的。但还是有一件事不对。

然而，快速搜索一下“ Haskell 图表”，我找到了 http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Practical_Graph_Handling，它看起来值得一读。

小开

正如本所提到的，哈斯克尔的循环数据是由一种名为“打结”的机制构建的。在实践中，这意味着我们使用 let或 where子句编写相互递归的声明，这样可以工作，因为相互递归的部分是延迟计算的。

下面是一个图形类型的例子:

import Data.Maybe (fromJust)


data Node a = Node
{ label    :: a
, adjacent :: [Node a]
}


data Graph a = Graph [Node a]

如您所见，我们使用实际的 Node引用而不是间接引用。下面是如何实现一个从标签关联列表构造图的函数。

mkGraph :: Eq a => [(a, [a])] -> Graph a
mkGraph links = Graph $ map snd nodeLookupList where


mkNode (lbl, adj) = (lbl, Node lbl $ map lookupNode adj)


nodeLookupList = map mkNode links


lookupNode lbl = fromJust $ lookup lbl nodeLookupList

我们获取一个 (nodeLabel, [adjacentLabel])对列表，并通过一个中间查找列表(执行实际的打结)构造实际的 Node值。诀窍在于，nodeLookupList(具有类型 [(a, Node a)])是使用 mkNode构造的，mkNode反过来引用 nodeLookupList来查找相邻节点。

小开

在李翔的回答中，您可以看到如何使用惰性来表示图形。这些表示的问题在于它们很难改变。只有当你打算构建一个图表一次，之后它永远不会改变时，打结技巧才有用。

实际上，如果我真的想用我的图表来表示 做什么的话，我会使用比较平常的表示法:

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

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

小开

没错，图表不是代数，要解决这个问题，你有两个选择:

  1. 考虑无限的树，而不是图。将图中的循环表示为它们的无限展开。在某些情况下，你可以使用“打结”的技巧(在这里的其他一些答案中解释得很好) ，甚至在有限的空间中通过在堆中创建一个循环来表示这些无限的树; 然而，你将无法在 Haskell 中观察或检测这些循环，这使得各种图表操作变得困难或不可能。
  2. 在文献中有各种各样的图代数。首先映入脑海的是 双向图变换第二部分中描述的图构造函数的集合。这些代数保证的通常性质是任何图都可以用代数表示; 然而，关键的是，许多图将不具有 规范表示。因此，仅仅从结构上检查等式是不够的; 正确地进行检查可以归结为寻找图的同构——这是一个众所周知的难题。
  3. 放弃代数数据类型; 通过给它们每个唯一值(比如 Ints)并间接引用它们而不是通过代数来显式表示节点标识。通过使类型变得抽象并提供一个为您处理间接操作的接口，可以使这一点变得非常方便。这是例如 FGL和其他 Hackage 上的实用图库所采用的方法。
  4. 提出一种全新的方法，完全适合您的用例。这是一件非常困难的事情。=)

所以上面的每一个选择都有利有弊。选择一个对你来说最好的。

小开

我喜欢这个取自 给你的图的实现

import Data.Maybe
import Data.Array


class Enum b => Graph a b | a -> b where
vertices ::  a -> [b]
edge :: a -> b -> b -> Maybe Double
fromInt :: a -> Int -> b
小开

任何关于在哈斯克尔表示图形的讨论都需要提到安迪 · 吉尔的 数据具体化库(这里是 报纸)。

“打结”风格的表示可以用来制作非常优雅的 DSL (参见下面的例子)。但是，数据结构的用途有限。吉尔的图书馆可以让你两全其美。您可以使用“打结”DSL，但是然后将基于指针的图转换为基于标签的图，这样您就可以在其上运行所选择的算法。

下面是一个简单的例子:

-- Graph we want to represent:
--    .----> a <----.
--   /               \
--  b <------------.  \
--   \              \ /
--    `----> c ----> d


-- Code for the graph:
a = leaf
b = node2 a c
c = node1 d
d = node2 a b
-- Yes, it's that simple!






-- If you want to convert the graph to a Node-Label format:
main = do
g <- reifyGraph b   --can't use 'a' because not all nodes are reachable
print g

要运行上述代码，您需要以下定义:

{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE TypeFamilies #-}
import Data.Reify
import Control.Applicative
import Data.Traversable


--Pointer-based graph representation
data PtrNode = PtrNode [PtrNode]


--Label-based graph representation
data LblNode lbl = LblNode [lbl] deriving Show


--Convenience functions for our DSL
leaf      = PtrNode []
node1 a   = PtrNode [a]
node2 a b = PtrNode [a, b]




-- This looks scary but we're just telling data-reify where the pointers are
-- in our graph representation so they can be turned to labels
instance MuRef PtrNode where
type DeRef PtrNode = LblNode
mapDeRef f (PtrNode as) = LblNode <$> (traverse f as)

我想强调的是，这是一个简单的 DSL，但 天空是极限！我设计了一个非常有特色的 DSL，包括一个很好的树形语法，让一个节点向它的一些子节点传播一个初始值，以及许多方便的函数，用于构造特定的节点类型。当然，Node 数据类型和 mapDeRef 定义要复杂得多。

小开

其他一些人简要地提到了 fgl和 Martin Erwig 的 归纳图与函数图算法，但是可能值得写一个答案，实际上给出归纳表示方法背后的数据类型的感觉。

在他的论文中，Erwig 提出了以下类型:

type Node = Int
type Adj b = [(b, Node)]
type Context a b = (Adj b, Node, a, Adj b)
data Graph a b = Empty | Context a b & Graph a b

(fgl中的表示略有不同，并充分利用了类型类——但其思想基本上是相同的。)

Erwig 描述了一个多重图，其中的节点和边都有标签，并且所有的边都有方向。Node具有某种类型的 a标签; 边具有某种类型的 b标签。Context是简单的(1)一个标记边列表，它指向 到特定的节点，(2)有问题的节点，(3)节点的标记，(4)一个标记边列表，它指向 a0节点。然后，可以将 Graph归纳为 Empty，或者将 Context(与 &)合并到现有的 Graph中。

正如 Erwig 指出的，我们不能自由地用 Empty和 &生成 Graph，因为我们可能用 Cons和 Nil构造函数生成一个列表，或者用 Leaf和 Branch生成一个 Tree。而且，与列表不同(正如其他人所提到的) ，Graph不会有任何规范表示。这些是至关重要的区别。

尽管如此，使这种表示如此强大，并且与列表和树的典型 Haskell 表示如此相似的是，这里的 Graph数据类型是 归纳定义的。事实上，一个列表是归纳定义的，这使我们能够如此简洁地对它进行模式匹配，处理单个元素，并递归地处理列表的其余部分; 同样，Erwig 的归纳表示允许我们递归地处理一个图，一次一个 Context。图的这种表示形式有助于简单地定义在图上映射的方法(gmap) ，以及在图上执行无序折叠的方法(ufold)。

这个页面上的其他评论都很棒。然而，我写下这个答案的主要原因是，当我读到诸如“图不是代数”这样的短语时，我担心一些读者会不可避免地产生这样的(错误的)印象: 在哈斯克尔，没有人能找到一种很好的方式来表示图形，这种方式允许对图形进行模式匹配、映射、折叠，或者像我们通常对列表和树所做的那样，进行一些很酷的功能性工作。


提交答案