Bạn thể hiện một biểu đồ trong Haskell như thế nào?

Question

Thật dễ dàng, đủ để đại diện cho một cây hoặc danh sách trong haskell sử dụng các loại dữ liệu đại số. Nhưng làm thế nào bạn sẽ đi về typographically đại diện cho một đồ thị? Có vẻ như bạn cần phải có con trỏ. Tôi đoán bạn có thể có một cái gì đó như

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

Và điều đó có thể thực hiện được. Tuy nhiên nó cảm thấy một chút tách rời; Các liên kết giữa các nút khác nhau trong cấu trúc không thực sự "cảm thấy" vững chắc như các liên kết giữa các phần tử trước đó và tiếp theo trong danh sách, hoặc cha mẹ và con của một nút trong cây. Tôi có một linh cảm mà làm các thao tác đại số trên đồ thị như tôi đã xác định nó sẽ có phần bị cản trở bởi mức độ không giới thiệu được giới thiệu thông qua hệ thống thẻ.

Điều này chủ yếu là cảm giác nghi ngờ và nhận thức về sự thiếu chính xác khiến tôi đặt câu hỏi này. Có cách nào tốt hơn/nhiều hơn về mặt toán học để xác định đồ thị trong Haskell? Hay tôi đã vấp phải một cái gì đó vốn có khó khăn/cơ bản? Cấu trúc dữ liệu đệ quy là ngọt ngào, nhưng điều này có vẻ là một cái gì đó khác. Một cấu trúc dữ liệu tự tham chiếu theo nghĩa khác nhau về cách cây và danh sách tự tham chiếu. Nó giống như danh sách và cây là tự tham chiếu ở cấp loại, nhưng đồ thị là tự tham chiếu ở cấp độ giá trị.

Vậy điều gì đang thực sự xảy ra?

Answer 1

Tôi cũng thấy khó xử khi cố gắng biểu diễn cấu trúc dữ liệu bằng các chu kỳ bằng ngôn ngữ thuần túy. Đó là những chu kỳ thực sự là vấn đề; bởi vì các giá trị có thể được chia sẻ bất kỳ ADT nào có thể chứa một thành viên của loại (bao gồm danh sách và cây) thực sự là một DAG (Đồ thị tuần hoàn hướng). Vấn đề cơ bản là nếu bạn có các giá trị A và B, với A chứa B và B chứa A, thì không thể tạo ra trước khi giá trị còn lại tồn tại. Bởi vì Haskell là lười biếng, bạn có thể sử dụng một thủ thuật được gọi là Tying the Knot để có được xung quanh này, nhưng điều đó làm cho bộ não của tôi bị tổn thương (vì tôi đã không thực hiện nhiều của nó chưa). Tôi đã thực hiện nhiều chương trình quan trọng của tôi trong Mercury hơn Haskell cho đến nay, và Mercury là nghiêm ngặt để hôn-buộc không giúp đỡ.

Thông thường khi tôi đã tham gia vào điều này trước khi tôi vừa mới sử dụng thêm tính không giới hạn, như bạn đang đề xuất; thường bằng cách sử dụng bản đồ từ các id đến các phần tử thực tế và có các phần tử chứa tham chiếu đến các id thay vì các phần tử khác. Điều chính tôi không thích làm điều đó (ngoài sự thiếu hiệu quả rõ ràng) là nó cảm thấy mong manh hơn, giới thiệu các lỗi có thể có khi tìm kiếm một id không tồn tại hoặc cố gán cùng một id cho nhiều hơn một thành phần. Bạn có thể viết mã để những lỗi này sẽ không xảy ra, tất nhiên, và thậm chí ẩn nó đằng sau abstractions để những nơi duy nhất mà các lỗi như vậy có thể xảy ra được giới hạn. Nhưng nó vẫn còn một điều nữa để có được sai.

Tuy nhiên, một google nhanh cho "biểu đồ Haskell" đã dẫn tôi đến http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Practical_Graph_Handling, trông giống như một giá trị đọc.

Answer 2

Như Ben đã đề cập, dữ liệu tuần hoàn trong Haskell được xây dựng bằng cơ chế được gọi là "buộc nút thắt". Trong thực tế, điều đó có nghĩa là chúng tôi viết các khai báo đệ quy lẫn nhau sử dụng các mệnh đề let hoặc where, hoạt động vì các phần đệ quy lẫn nhau được đánh giá lazily.

Dưới đây là một ví dụ loại biểu đồ:

import Data.Maybe (fromJust) 

data Node a = Node 
    { label :: a 
    , adjacent :: [Node a] 
    } 

data Graph a = Graph [Node a] 

Như bạn có thể thấy, chúng ta sử dụng tài liệu tham khảo thực tế Node thay vì gián tiếp. Dưới đây là cách triển khai hàm xây dựng biểu đồ từ danh sách các liên kết nhãn.

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 

Chúng tôi có trong danh sách các (nodeLabel, [adjacentLabel]) cặp và xây dựng Node giá trị thực tế thông qua một tra cứu-list trung gian (mà không hôn-buộc thực tế). Bí quyết là nodeLookupList (trong đó có loại [(a, Node a)]) được xây dựng bằng cách sử dụng mkNode, do đó đề cập đến số nodeLookupList để tìm các nút lân cận.

Answer 3

Trong câu trả lời của bạn, bạn có thể thấy cách biểu diễn một biểu đồ bằng cách sử dụng sự lười biếng. Vấn đề với những biểu diễn này là chúng rất khó thay đổi. Thủ thuật buộc hôn chỉ hữu ích nếu bạn định xây dựng biểu đồ một lần và sau đó nó không bao giờ thay đổi.

Trên thực tế, nên tôi thực sự muốn làm gì đó với đồ thị của tôi, tôi sử dụng nhiều cơ quan đại diện cho người đi bộ:

• danh sách Cạnh
• danh sách kề
• tặng một nhãn duy nhất cho mỗi nút , sử dụng nhãn thay vì con trỏ và giữ bản đồ hữu hạn từ nhãn đến các nút

Nếu bạn sắp thay đổi hoặc chỉnh sửa biểu đồ thường xuyên, tôi khuyên bạn nên sử dụng một biểu diễn dựa trên dây kéo của Huet. Đây là biểu diễn được sử dụng trong nội bộ trong GHC cho các biểu đồ dòng điều khiển. Bạn có thể đọc về nó ở đây:

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

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

Answer 4

Đó là sự thật, đồ thị không phải là đại số. Để giải quyết vấn đề này, bạn có một vài tùy chọn:

1. Thay vì đồ thị, hãy xem xét các cây vô hạn. Biểu diễn các chu kỳ trong biểu đồ dưới dạng các khoảng hở vô hạn của chúng. Trong một số trường hợp, bạn có thể sử dụng thủ thuật được gọi là "buộc nút thắt" (được giải thích tốt trong một số câu trả lời khác ở đây) để thậm chí đại diện cho những cây vô hạn này trong không gian hữu hạn bằng cách tạo chu trình trong heap; tuy nhiên, bạn sẽ không thể quan sát hoặc phát hiện các chu kỳ này từ bên trong Haskell, điều này làm cho nhiều hoạt động biểu đồ trở nên khó khăn hoặc không thể.
2. Có nhiều đại số đồ thị có sẵn trong tài liệu. Một ý nghĩ đến đầu tiên là tập hợp các nhà xây dựng đồ thị được mô tả trong phần hai của Bidirectionalizing Graph Transformations. Thuộc tính thông thường được đảm bảo bởi các đại số này là bất kỳ biểu đồ nào có thể được biểu diễn đại số; tuy nhiên, xét về mặt chi tiết, nhiều đồ thị sẽ không có đại diện canonical. Vì vậy, kiểm tra bình đẳng cấu trúc là không đủ; làm cho nó một cách chính xác nhọt xuống để tìm đồ thị đẳng cấu - được biết đến là một cái gì đó của một vấn đề khó khăn.
3. Hãy từ bỏ các kiểu dữ liệu đại số; đại diện rõ ràng nhận dạng nút bằng cách cho chúng mỗi giá trị duy nhất (giả sử, Int s) và đề cập đến chúng một cách gián tiếp thay vì đại số. Điều này có thể được thực hiện thuận tiện hơn đáng kể bằng cách làm cho kiểu trừu tượng và cung cấp một giao diện juggles indirection cho bạn. Đây là phương pháp được thực hiện bởi, ví dụ: fgl và các thư viện đồ thị thực tế khác trên Hackage.
4. Hãy đưa ra cách tiếp cận hoàn toàn mới phù hợp với trường hợp sử dụng của bạn một cách chính xác. Đây là một việc rất khó làm.=)

Vì vậy, có những ưu và khuyết điểm đối với từng lựa chọn ở trên. Chọn cái có vẻ tốt nhất cho bạn.

Answer 5

Tôi luôn thích cách tiếp cận của Martin Erwig trong "Đồ thị cảm ứng và thuật toán đồ thị chức năng", bạn có thể đọc here. FWIW, tôi đã từng viết một bản thực hiện Scala, xem https://github.com/nicolast/scalagraphs.

Answer 6

Tôi thích thực hiện này của một đồ thị lấy từ 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

Bất kỳ cuộc thảo luận về đại diện cho đồ thị trong Haskell cần có một đề cập đến Andy Gill của data-reify library (ở đây là the paper).

Biểu diễn kiểu "thắt nút" có thể được sử dụng để tạo các DSL rất thanh lịch (xem ví dụ bên dưới). Tuy nhiên, cấu trúc dữ liệu bị hạn chế sử dụng. Thư viện của Gill cho phép bạn tốt nhất trong cả hai thế giới. Bạn có thể sử dụng DSL "buộc nút", nhưng sau đó chuyển đổi biểu đồ dựa trên con trỏ thành biểu đồ dựa trên nhãn để bạn có thể chạy các thuật toán lựa chọn của mình trên đó.

Dưới đây là một ví dụ đơn giản:

-- 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 

Để chạy đoạn code trên, bạn sẽ cần các định nghĩa sau đây:

{-# 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) 

Tôi muốn nhấn mạnh rằng đây là một DSL đơn giản, nhưng sự giới hạn của bầu trời! Tôi đã thiết kế một DSL rất đặc trưng, ​​bao gồm một cú pháp giống cây đẹp để có một nút phát một giá trị ban đầu cho một số con của nó, và nhiều chức năng tiện lợi để xây dựng các kiểu nút cụ thể. Tất nhiên, kiểu dữ liệu Node và các định nghĩa mapDeRef có liên quan nhiều hơn.

Answer 8

Một vài người khác đã đề cập ngắn gọn fgl và Martin Erwig's Inductive Graphs and Functional Graph Algorithms, nhưng có lẽ đáng để viết câu trả lời thực sự mang lại cảm giác về các loại dữ liệu đằng sau cách tiếp cận đại diện quy nạp.

Trong bài báo của mình, Erwig trình bày các loại sau đây:

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 

(Các đại diện trong fgl là hơi khác nhau, và tận dụng tốt của typeclasses - nhưng ý tưởng cơ bản là như nhau.)

Erwig mô tả một multigraph trong đó các nút và cạnh có nhãn, và trong đó tất cả các cạnh được hướng. A Node có nhãn của một số loại a; cạnh có nhãn của một số loại b. Một Context chỉ đơn giản là (1) danh sách các cạnh được gắn nhãn trỏ đến một nút cụ thể, (2) nút được đề cập, (3) nhãn của nút và (4) danh sách các cạnh được gắn nhãn trỏ từ nút . Sau đó, Graph có thể được hình thành theo cách tự cảm dưới dạng Empty hoặc dưới dạng Context được hợp nhất (với &) vào số Graph hiện có.

Như ghi chú Erwig, chúng ta không thể tự do tạo ra một Graph với Empty và &, như chúng ta có thể tạo ra một danh sách với các Cons và Nil nhà thầu, hoặc một Tree với Leaf và Branch. Quá, không giống như danh sách (như những người khác đã đề cập), sẽ không có bất kỳ đại diện kinh điển của một Graph. Đây là những khác biệt quan trọng.

Tuy nhiên, điều làm cho biểu diễn này trở nên mạnh mẽ và tương tự với biểu diễn danh sách và cây Haskell điển hình, là kiểu dữ liệu Graph ở đây là được xác định theo cách tự động. Thực tế là một danh sách được định nghĩa tự do là những gì cho phép chúng ta mô hình rất ngắn gọn khớp với nó, xử lý một phần tử duy nhất, và đệ quy xử lý phần còn lại của danh sách; bằng nhau, biểu diễn quy nạp của Erwig cho phép chúng ta đệ quy đệ quy một đồ thị một Context cùng một lúc. Biểu diễn này của biểu đồ cho chính nó với định nghĩa đơn giản về cách ánh xạ trên biểu đồ (gmap), cũng như cách để thực hiện các nếp gấp không theo thứ tự trên biểu đồ (ufold).

Các nhận xét khác trên trang này thật tuyệt vời. Lý do chính tôi viết câu trả lời này là khi tôi đọc các cụm từ như "đồ thị không đại số", tôi sợ rằng một số độc giả chắc chắn sẽ biến mất với ấn tượng (sai lầm) mà không ai tìm thấy cách tốt để đại diện cho đồ thị trong Haskell theo cách cho phép khớp mẫu trên chúng, ánh xạ lên chúng, gấp chúng, hoặc thường làm các loại công cụ chức năng, mát mẻ mà chúng ta thường làm với danh sách và cây cối.