你如何在 Haskell 中表示一个图形？

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

在实践中，如果我真的想对我的图表做点什么，我会使用更多的行人表示：

边缘列表

邻接表

给每个节点一个唯一的标签，使用标签而不是指针，并保持从标签到节点的有限映射

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

基于Huet's Zipper的应用控制流图

Hoopl：用于数据流分析和转换的模块化、可重用库

---

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

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

但是，“Haskell 图”的快速 google 使我找到了 http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Practical_Graph_Handling，这看起来值得一读。

---

正如 Ben 提到的，Haskell 中的循环数据是通过一种称为“打结”的机制构建的。在实践中，这意味着我们使用 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 构造的，它反过来又引用 nodeLookupList 以查找相邻节点。

---

确实，图不是代数的。要解决此问题，您有两种选择：

考虑无限树而不是图。将图中的循环表示为它们的无限展开。在某些情况下，您可以使用称为“打结”的技巧（在此处的其他一些答案中进行了很好的解释），甚至可以通过在堆中创建循环来在有限空间中表示这些无限树；但是，您将无法在 Haskell 中观察或检测这些循环，这使得各种图形操作变得困难或不可能。文献中有各种可用的图代数。首先想到的是双向图形转换的第二节中描述的图形构造函数的集合。这些代数保证的通常性质是任何图都可以用代数表示。然而，至关重要的是，许多图不会有规范的表示。所以从结构上检查相等性是不够的；正确地做到这一点归结为找到图同构——众所周知，这是一个难题。放弃代数数据类型；通过给它们每个唯一值（例如，Ints）并间接而不是代数地引用它们来明确表示节点身份。通过使类型抽象并提供一个为您处理间接的接口，可以使这变得更加方便。这是例如 fgl 和其他关于 Hackage 的实用图形库所采用的方法。提出一种完全适合您的用例的全新方法。这是一件非常困难的事情。 =)

因此，上述每种选择各有利弊。选择一个最适合你的。

---

其他一些人简要提到了 fgl 和 Martin Erwig 的 Inductive Graphs and Functional Graph Algorithms，但可能值得写一个答案，它实际上可以了解归纳表示方法背后的数据类型。

在他的论文中，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) 标记的列表指向 节点的边。然后可以将 Graph 归纳为 Empty 或合并（与 &）到现有 Graph 中的 Context。

正如 Erwig 所指出的，我们不能随意生成带有 Empty 和 & 的 Graph，因为我们可能会生成带有 Cons 和 Nil 构造函数的列表，或者带有 Leaf 的 Tree 和Branch。同样，与列表不同（正如其他人提到的），Graph 不会有任何规范表示。这些是至关重要的区别。

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

此页面上的其他评论很棒。然而，我写这个答案的主要原因是，当我读到诸如“图形不是代数的”之类的短语时，我担心一些读者不可避免地会产生一种（错误的）印象，即没有人找到表示图形的好方法在 Haskell 中，以一种允许对它们进行模式匹配、映射它们、折叠它们的方式，或者通常做我们习惯用列表和树做的那种很酷的、功能性的东西。

---

任何关于在 Haskell 中表示图的讨论都需要提及 Andy Gill 的 data-reify library（这里是 the paper）。

“打结”样式表示可用于制作非常优雅的 DSL（参见下面的示例）。但是，数据结构的用途有限。 Gill 的图书馆可以让您两全其美。您可以使用“打结”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 定义涉及更多。

---

我喜欢这种取自 here 的图表的实现

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

---