你如何在Haskell中表示图形？

Question

使用代数数据类型表示haskell中的树或列表很容易.但是你会怎么用印刷术来表示图形呢？看来你需要有指针.我猜你可以有类似的东西

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

这是可行的.然而感觉有点脱钩; 结构中不同节点之间的链接并不真正"感觉"像列表中当前上一个和下一个元素之间的链接一样,或者树中节点的父节点和子节点之间的链接.我有一种预感,即在我定义的图形上进行代数操作会受到通过标签系统引入的间接级别的阻碍.

主要是这种怀疑的感觉和不雅的感觉使我提出这个问题.在Haskell中定义图形是否有更好/更优化的方式？或者我偶然发现了本质上坚硬/根本的东西？递归数据结构很好,但这似乎是另一回事.自引用数据结构,与树和列表的自引用方式不同.它就像列表和树在类型级别是自引用的,但是图形在值级别是自引用的.

那真正发生了什么？

Answer 1

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

在实践中,如果我真的想要对我的图表做些什么,我会使用更多的行人表示:

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

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

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

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

Answer 2

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

通常当我遇到这种情况之前,我只是采取了额外的间接方式,正如你所建议的那样; 通常使用从ids到实际元素的映射,并且元素包含对id的引用而不是对其他元素的引用.我不喜欢做的主要事情(除了显而易见的低效率)是它感觉更脆弱,引入了查找不存在的id或尝试将相同的id分配给多个id的可能错误元件.当然,您可以编写代码以便不会发生这些错误,甚至将其隐藏在抽象之后,以便可能发生此类错误的唯一位置是有限的.但是,还有一件事是错误的.

然而,快速google的"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. 放弃代数数据类型; 通过给出每个唯一值(比如Ints)并间接而不是代数地引用它们来明确地表示节点身份.通过使类型抽象并提供一个为您提供间接性的接口,可以使这更加方便.这是通过,例如,所采用的方法FGL和Hackage其他实际图形库.
4. 提出一种全新的方法,完全符合您的使用案例.这是一件非常困难的事情.=)

因此,上述每种选择都有利有弊.选择一个最适合你的.

Answer 5

我一直很喜欢Martin Erwig在"归纳图和功能图算法"中的方法,你可以在这里阅读.FWIW,我曾经写过一个Scala实现,请参阅https://github.com/nicolast/scalagraphs.

Answer 6

其他一些人已经简要地提到了fglMartin 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正在描述一个多图,其中节点和边有标签,其中所有边都是定向的.A Node有某种类型的标签a; 边缘有某种类型的标签b.甲Context只是(1)指向标记边缘的列表,以一个特定的节点,(2)所讨论的节点,(3)的节点的标签,和(4)指向标记边缘的列表从该节点.Graph然后,A 可以被归纳为Empty或者被Context合并(或&)合并为现有的Graph.

正如Erwig所说,我们不能自由生成Graphwith Empty和&,因为我们可能会生成一个包含Cons和Nil构造函数的列表,或者Tree使用Leaf和Branch.与列表不同(正如其他人提到的那样),也不会有任何规范表示Graph.这是至关重要的差异.

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

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

Answer 7

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

“打结”样式表示可用于制作非常优雅的 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 定义涉及更多。