您如何在Haskell中表示图表？

Question

使用代数数据类型很容易在haskell中表示树或列表。但是，你将如何去印刷代表图表？看来你需要有指针。我猜你可能有类似

​​

而且这是可行的。然而它感觉有点解耦;结构中的不同节点之间的链接并不像真正的“感觉”那样与列表中当前的前一个元素和下一个元素之间的链接，或者树中节点的父节点和子节点之间的链接。我有一个直觉，就是对图形进行代数操作，因为我定义它会受到标签系统引入的间接级别的阻碍。

这主要是这种怀疑和不雅的感觉，导致我问这个问题。在Haskell中定义图形是否有更好/更好的数学优化方法？还是我偶然发现了一些本质上很难/根本的东西？递归数据结构是甜蜜的，但这似乎是别的。自我参照数据结构与树和列表如何作为自我参照的意义不同。它就像列表和树木在类型级别上是自引用的，但图形在值级别上是自引用的。

那么究竟发生了什么？

Answer 1

我也发现尝试用纯语言表示循环的数据结构很尴尬。这是真正的问题的循环;因为值可以共享任何可以包含类型成员（包括列表和树）的ADT实际上是一个DAG（定向非循环图）。根本的问题是，如果你有值A和B，其中A包含B和B包含A，那么在另一个存在之前都不能创建。因为Haskell很懒，所以你可以使用一个叫做Tying the Knot的技巧来解决这个问题，但这会让我的大脑受到伤害（因为我还没有做太多工作）。到目前为止，我已经在Mercury中完成了比Haskell更多的实质性编程工作，而Mercury非常严格，所以打结无助于此。

通常当我刚才诉诸另外的间接方法时，如你所暗示的那样，通常通过使用从ID到实际元素的映射，并且元素包含对ID的引用而不是其他元素。我不喜欢这样做的主要原因（除了显而易见的低效率之外）是感觉更加脆弱，介绍了查找不存在的id或试图将同一id分配给多个id的可能错误元件。您可以编写代码，以便当然不会发生这些错误，甚至将其隐藏在抽象之后，以便发生此类错误的唯一地方是有界的。但是还有一件事是错误的。

但是，“Haskell图表”的一个快速谷歌导致我http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Practical_Graph_Handling，这看起来像一个值得阅读。

Answer 2

正如本文提到的，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构建的，而mkNode又指向nodeLookupList以查找相邻节点。

Answer 3

在shang的回答中，您可以看到如何使用懒惰表示图。这些陈述的问题是他们很难改变。打结技巧只有在你打算构建一个图形时才有用，而且之后它不会改变。

在实践中，我居然想做一些与我的图表，我用的是比较平淡的表示：

• 边列表
• 邻接表
• 提供一个独特的标签，每个节点，使用标签而不是指针，并保持从标签到节点的有限映射

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

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

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

Answer 4

这是真的，图不代数。要解决这个问题，你有几个选择：

1. 而不是图表，考虑无限树。将图中的循环表示为其无限展开。在某些情况下，你可以使用被称为“绑结”的技巧（在这里的一些其他答案中很好地解释）甚至通过在堆中创建一个循环来在有限的空间中表示这些无限的树;但是，您将无法从Haskell内部观察或检测这些循环，这使得各种图形操作变得困难或不可能。
2. 在文献中有各种各样的图代数。首先想到的是Bidirectionalizing Graph Transformations第二部分描述的图构造函数的集合。这些代数保证的通常属性是任何图都可以用代数表示;然而，关键的是，许多图表将不具有规范表示。因此，在结构上检查平等是不够的;正确地做它归结为找到图同构 - 已知是一个难题。
3. 放弃代数数据类型;通过给每个唯一值（比如说，Int s）并间接引用它们而不是代数来显式地表示节点标识。通过制作抽象类型并提供一个接口来为你提供间接方法，这可以变得更加方便。这是由例如fgl和Hackage上的其他实用图库所采用的方法。
4. 想出一个完全符合您的使用案例的全新方法。这是一件非常困难的事情。=）

所以每个上述选择都有优点和缺点。选择一个最适合你的人。

Answer 5

我一直很喜欢Martin Erwig在“归纳图和函数图算法”中的方法，您可以阅读here。 FWIW，我也曾经写过一个Scala实现，请参阅https://github.com/nicolast/scalagraphs。

Answer 6

我喜欢这个实现的图形从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 

Answer 7

采取较Haskell中图形的任何讨论需要的安迪·吉尔data-reify library一提的（这里是the paper）。

“打结”风格表示可用于制作非常优雅的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 8

其他一些人已经简要地提到了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描述了一个多图，其中节点和边有标签，并且所有边都是直接指向的。 A Node有某种类型的标签a;边缘有某种类型的标签b。 A Context简单地（1）标记边缘的列表，其指向到特定节点，（2）所讨论的节点，（3）节点的标签，以及（4）标记边缘的列表，指向，从节点。然后可以将Graph作为Empty或作为Context合并（与&）归纳为现有Graph。

由于Erwig指出，我们不能随意生成Graph与Empty和&，因为我们可能会产生与Cons和Nil构造，或Leaf和Branch一个Tree列表。太不像列表（正如其他人所提到的），不会有任何规范的Graph表示。这些是至关重要的差异

然而，是什么让这表示如此强大，所以类似的列表和树的典型哈斯克尔表示，是这里的Graph数据类型是归纳定义。事实上，列表是归纳定义的，它允许我们在它上简洁地匹配模式匹配，处理单个元素，并递归处理列表的其余部分;同样，Erwig的归纳表示允许我们一次递归地处理一个图形Context。这种图形表示方式适用于在图形上绘制图形的简单定义（gmap），以及在图形上执行无序折叠的方法（ufold）。

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