Bagaimana Anda merepresentasikan grafik di Haskell?

Cukup mudah untuk merepresentasikan pohon atau daftar di haskell menggunakan tipe data aljabar. Tapi bagaimana Anda akan merepresentasikan grafik secara tipografis? Sepertinya Anda perlu memiliki petunjuk. Saya menduga Anda bisa mendapatkan sesuatu seperti

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

Dan itu bisa diterapkan. Namun itu terasa agak terpisah; Hubungan antara node yang berbeda dalam struktur tidak benar-benar "terasa" sekokoh link antara elemen sebelumnya dan selanjutnya dalam daftar, atau orang tua dan turunan dari node dalam pohon. Saya memiliki firasat bahwa melakukan manipulasi aljabar pada grafik seperti yang saya definisikan akan terhalang oleh tingkat tipuan yang diperkenalkan melalui sistem tag.

Perasaan ragu-ragu dan persepsi tentang ketidaksengajaan inilah yang menyebabkan saya mengajukan pertanyaan ini. Apakah ada cara yang lebih baik / lebih elegan secara matematis untuk mendefinisikan grafik di Haskell? Atau apakah saya tersandung pada sesuatu yang secara inheren keras / mendasar? Struktur data rekursif memang bagus, tetapi tampaknya ini adalah sesuatu yang lain. Struktur data referensi mandiri dalam arti yang berbeda tentang bagaimana pohon dan daftar merujuk pada diri sendiri. Ini seperti daftar dan pohon yang merujuk pada diri sendiri pada tingkat jenis, tetapi grafik merujuk pada diri sendiri pada tingkat nilai.

Jadi apa yang sebenarnya terjadi?

Saya juga merasa canggung untuk mencoba merepresentasikan struktur data dengan siklus dalam bahasa murni. Siklus itulah yang menjadi masalah; karena nilai dapat dibagi ADT apa pun yang dapat berisi anggota jenis (termasuk daftar dan pohon) benar-benar DAG (Grafik Acyclic Terarah). Masalah mendasar adalah jika Anda memiliki nilai A dan B, dengan A berisi B dan B berisi A, maka tidak ada yang dapat dibuat sebelum yang lain ada. Karena Haskell malas, Anda bisa menggunakan trik yang dikenal sebagai Tying the Knot untuk menyiasatinya, tetapi itu membuat otak saya sakit (karena saya belum melakukan banyak hal). Sejauh ini, saya telah melakukan lebih banyak pemrograman substansial saya di Mercury daripada Haskell, dan Mercury sangat ketat sehingga mengikat simpul tidak membantu.

Biasanya ketika saya mengalami hal ini sebelumnya, saya baru saja menggunakan tipuan tambahan, seperti yang Anda sarankan; seringkali dengan menggunakan peta dari id ke elemen sebenarnya, dan memiliki elemen yang berisi referensi ke id, bukan ke elemen lain. Hal utama yang saya tidak suka melakukan itu (selain dari ketidakefisienan yang jelas) adalah rasanya lebih rapuh, memperkenalkan kemungkinan kesalahan mencari id yang tidak ada atau mencoba menetapkan id yang sama ke lebih dari satu elemen. Anda dapat menulis kode sehingga kesalahan ini tidak akan terjadi, tentu saja, dan bahkan menyembunyikannya di balik abstraksi sehingga satu-satunya tempat di mana kesalahan dapat terjadi dibatasi. Tapi masih ada satu hal lagi yang salah.

Namun, Google cepat untuk "grafik Haskell" membawa saya ke http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Practical_Graph_Handling , yang terlihat seperti bacaan yang bermanfaat.

Dalam jawaban shang Anda dapat melihat bagaimana merepresentasikan grafik menggunakan kemalasan. Masalah dengan representasi ini adalah bahwa mereka sangat sulit untuk diubah. Trik mengikat simpul hanya berguna jika Anda akan membuat grafik sekali, dan setelah itu tidak pernah berubah.

Dalam praktiknya, jika saya benar-benar ingin melakukan sesuatu dengan grafik saya, saya menggunakan representasi pejalan kaki yang lebih banyak:

• Daftar tepi
• Daftar kedekatan
• Berikan label unik untuk setiap node, gunakan label sebagai ganti pointer, dan simpan peta terbatas dari label ke node

Jika Anda akan sering mengubah atau mengedit grafik, saya sarankan menggunakan representasi berdasarkan ritsleting Huet. Ini adalah representasi yang digunakan secara internal di GHC untuk grafik aliran kontrol. Anda dapat membacanya di sini:

• Grafik Aliran Kontrol Aplikatif berdasarkan Ritsleting Huet

• Hoopl: Perpustakaan Modular, Dapat Digunakan Kembali untuk Analisis Aliran Data dan Transformasi

Seperti yang Ben sebutkan, data siklik di Haskell dibangun oleh mekanisme yang disebut "mengikat simpul". Dalam praktiknya, ini berarti bahwa kita menulis deklarasi yang saling rekursif menggunakan klausa letatau where, yang berfungsi karena bagian yang saling rekursif dievaluasi secara malas.

Berikut adalah contoh jenis grafik:

import Data.Maybe (fromJust)

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

data Graph a = Graph [Node a]

Seperti yang Anda lihat, kami menggunakan Nodereferensi aktual alih-alih tipuan. Berikut cara menerapkan fungsi yang menyusun grafik dari daftar asosiasi label.

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

Kami mengambil daftar (nodeLabel, [adjacentLabel])pasangan dan membangun nilai aktual Nodemelalui daftar pencarian menengah (yang melakukan ikatan simpul yang sebenarnya). Triknya adalah bahwa nodeLookupList(yang memiliki tipe [(a, Node a)]) dibangun menggunakan mkNode, yang pada gilirannya merujuk kembali ke nodeLookupListuntuk menemukan node yang berdekatan.

Memang benar, grafik bukanlah aljabar. Untuk mengatasi masalah ini, Anda memiliki beberapa opsi:

1. Alih-alih grafik, pertimbangkan pohon tak terbatas. Mewakili siklus dalam grafik sebagai pembukanya yang tak terbatas. Dalam beberapa kasus, Anda dapat menggunakan trik yang dikenal sebagai "mengikat simpul" (dijelaskan dengan baik dalam beberapa jawaban lain di sini) untuk bahkan merepresentasikan pohon tak hingga ini dalam ruang terbatas dengan membuat siklus di tumpukan; namun, Anda tidak akan dapat mengamati atau mendeteksi siklus ini dari dalam Haskell, yang membuat berbagai operasi grafik menjadi sulit atau tidak mungkin.
2. Ada berbagai aljabar grafik yang tersedia di literatur. Yang pertama terlintas dalam pikiran adalah kumpulan konstruktor grafik yang dijelaskan di bagian dua Transformasi Grafik Dua Arah . Properti umum yang dijamin oleh aljabar ini adalah bahwa setiap grafik dapat direpresentasikan secara aljabar; namun, secara kritis, banyak grafik tidak akan memiliki representasi kanonik . Jadi memeriksa kesetaraan secara struktural tidaklah cukup; melakukannya dengan benar bermuara pada menemukan isomorfisme grafik - yang dikenal sebagai masalah yang sulit.
3. Menyerah pada tipe data aljabar; secara eksplisit mewakili identitas node dengan memberi mereka setiap nilai unik (katakanlah, Ints) dan merujuknya secara tidak langsung daripada secara aljabar. Ini bisa dibuat jauh lebih nyaman dengan membuat tipe abstrak dan menyediakan antarmuka yang menyulap tipuan untuk Anda. Ini adalah pendekatan yang diambil oleh, misalnya, fgl dan pustaka grafik praktis lainnya di Hackage.
4. Munculkan pendekatan baru yang benar-benar sesuai dengan kasus penggunaan Anda. Ini adalah hal yang sangat sulit dilakukan. =)

Jadi ada pro dan kontra untuk setiap pilihan di atas. Pilih salah satu yang menurut Anda terbaik.

Beberapa orang lain telah secara singkat menyebutkan fgldan Martin Erwig's Inductive Graphs and Functional Graph Algorithms , tetapi mungkin ada baiknya menulis jawaban yang benar-benar memberikan gambaran tentang tipe data di balik pendekatan representasi induktif.

Dalam makalahnya, Erwig memaparkan jenis-jenis berikut:

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

(Representasi dalam fgl sedikit berbeda, dan memanfaatkan kelas tipe dengan baik - tetapi idenya pada dasarnya sama.)

Erwig mendeskripsikan multigraph di mana node dan edge memiliki label, dan di mana semua edge diarahkan. A Nodememiliki label dari beberapa jenis a; tepi memiliki label dari beberapa jenis b. A Contexthanyalah (1) daftar tepi berlabel yang menunjuk ke simpul tertentu, (2) simpul yang dimaksud, (3) label simpul, dan (4) daftar tepi berlabel yang menunjuk dari simpul. A Graphkemudian dapat dipahami secara induktif sebagai salah satu Empty, atau sebagai Contextdigabungkan (dengan &) menjadi yang ada Graph.

Sebagai catatan Erwig, kita tidak dapat dengan bebas menghasilkan Graphdengan Emptydan &, karena kita mungkin menghasilkan daftar dengan konstruktor Consdan Nil, atau Treedengan Leafdan Branch. Juga, tidak seperti daftar (seperti yang telah disebutkan orang lain), tidak akan ada representasi kanonik dari a Graph. Ini adalah perbedaan penting.

Meskipun demikian, apa yang membuat representasi ini begitu kuat, dan sangat mirip dengan representasi daftar dan pohon Haskell yang khas, adalah bahwa Graphtipe data di sini didefinisikan secara induktif . Fakta bahwa daftar didefinisikan secara induktif adalah hal yang memungkinkan kita untuk mencocokkan pola dengan begitu ringkas, memproses satu elemen, dan secara rekursif memproses sisa daftar; sama, representasi induktif Erwig memungkinkan kita memproses grafik satu Contextper satu secara rekursif . Representasi grafik ini cocok untuk definisi sederhana tentang cara memetakan di atas grafik ( gmap), serta cara untuk melakukan lipatan tak berurutan di atas grafik (ufold ).

Komentar lain di halaman ini bagus. Namun, alasan utama saya menulis jawaban ini adalah bahwa ketika saya membaca frasa seperti "grafik bukan aljabar", saya khawatir beberapa pembaca pasti akan mendapatkan kesan (keliru) bahwa tidak ada yang menemukan cara yang bagus untuk merepresentasikan grafik di Haskell dengan cara yang memungkinkan pencocokan pola pada mereka, memetakannya, melipatnya, atau secara umum melakukan hal-hal keren dan fungsional yang biasa kita lakukan dengan daftar dan pohon.

Saya selalu menyukai pendekatan Martin Erwig dalam "Grafik Induktif dan Algoritma Grafik Fungsional", yang dapat Anda baca di sini . FWIW, saya pernah menulis implementasi Scala juga, lihat https://github.com/nicolast/scalagraphs .

Setiap diskusi tentang merepresentasikan grafik di Haskell perlu menyebutkan pustaka data-reify Andy Gill (inilah makalahnya ).

Representasi gaya "mengikat-simpul" dapat digunakan untuk membuat DSL yang sangat elegan (lihat contoh di bawah). Namun, struktur datanya masih terbatas penggunaannya. Perpustakaan Gill memberi Anda yang terbaik dari kedua dunia. Anda dapat menggunakan DSL "mengikat simpul", tetapi kemudian mengubah grafik berbasis penunjuk menjadi grafik berbasis label sehingga Anda dapat menjalankan algoritme pilihan Anda di atasnya.

Berikut ini contoh sederhananya:

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

Untuk menjalankan kode di atas, Anda memerlukan definisi berikut:

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

Saya ingin menekankan bahwa ini adalah DSL sederhana, tetapi langit adalah batasnya! Saya merancang DSL yang sangat lengkap, termasuk sintaks mirip pohon yang bagus untuk membuat simpul menyiarkan nilai awal ke beberapa anaknya, dan banyak fungsi praktis untuk membangun tipe simpul tertentu. Tentu saja, tipe data Node dan definisi mapDeRef lebih banyak terlibat.

Saya suka implementasi grafik yang diambil dari sini

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