你如何在哈斯克尔中表示图形

Question

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

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

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

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

这到底是怎么回事呢？

Answer 1

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

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

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

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

• 基于休特拉链的应用控制流图

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

Answer 2

我也发现尝试用纯语言表示带有循环的数据结构很尴尬。真正的问题是周期;因为值可以共享，任何可以包含该类型成员(包括列表和树(的 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，这看起来值得一读。

Answer 3

正如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来查找相邻的节点。

Answer 4

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

1. 考虑无限树，而不是图形。在图中将周期表示为它们的无限展开。在某些情况下，您可以使用称为"打结"的技巧(在这里的其他一些答案中解释得很好(甚至可以通过在堆中创建循环来表示有限空间中的这些无限树;但是，您将无法从 Haskell 内部观察或检测这些周期，这使得各种图形操作变得困难或不可能。
2. 文献中有多种图代数。首先想到的是双向化图转换第二节中描述的图构造函数集合。这些代数保证的通常性质是任何图都可以代数表示;但是，至关重要的是，许多图形将没有规范表示。因此，从结构上检查平等是不够的;正确地做到这一点可以归结为找到图同构 - 已知是一个难题。
3. 放弃代数数据类型;通过赋予它们每个唯一值(例如，Int s(并间接而不是代数引用它们来显式表示节点标识。通过使类型抽象并提供一个为您处理间接寻址的接口，可以大大方便。例如，fgl 和 Hackage 上其他实用的图形库采用这种方法。
4. 想出一种完全适合您的用例的全新方法。这是一件非常困难的事情。 =(

因此，上述每个选择都有优点和缺点。选择最适合您的一个。

Answer 5

其他一些人简要提到了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( 指向节点的标记边列表。然后，一个Graph可以归纳地想象为Empty，或者被归纳为(与&(合并到现有Graph中的Context。

正如 Erwig 所指出的，我们不能自由地生成一个带有 Empty 和 & 的Graph，因为我们可能会生成一个包含 Cons 和 Nil 构造函数的列表，或者一个包含 Leaf 和 Branch 的Tree。同样，与列表(如其他人所提到的(不同，不会有任何Graph的规范表示。这些是关键差异。

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

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

Answer 6

任何关于在Haskell中表示图形的讨论都需要提到Andy Gill的数据reify库(这是论文(。

"打结"样式表示可用于制作非常优雅的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 定义要复杂得多。

Answer 7

我喜欢从这里获取的图形的实现

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