您如何在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中允許對它們進行模式匹配，對它們進行映射，對它們進行摺疊，或者通常做一些我們習慣使用列表和樹的很酷，功能性的東西。