Jak przedstawiasz wykres w Haskell?

Bardzo łatwo jest przedstawić drzewo lub listę w haskell przy użyciu algebraicznych typów danych. Ale jak zabrałbyś się do typograficznego przedstawienia wykresu? Wygląda na to, że potrzebujesz wskazówek. Domyślam się, że możesz mieć coś takiego

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

I to byłoby wykonalne. Jednak wydaje się nieco oddzielony; Powiązania między różnymi węzłami w strukturze tak naprawdę nie są tak solidne, jak łącza między bieżącymi poprzednimi i następnymi elementami na liście lub rodzicami i dziećmi węzła w drzewie. Mam przeczucie, że wykonywanie operacji algebraicznych na wykresie, tak jak to zdefiniowałem, byłoby nieco utrudnione przez poziom pośredni wprowadzony przez system tagów.

To przede wszystkim poczucie wątpliwości i poczucie nieelegancji powoduje, że zadaję to pytanie. Czy istnieje lepszy / bardziej matematycznie elegancki sposób definiowania wykresów w Haskellu? A może natknąłem się na coś z natury trudnego / fundamentalnego? Rekurencyjne struktury danych są fajne, ale wydaje się, że to coś innego. Struktura danych odnosząca się do siebie w innym sensie niż drzewa i listy odwołujące się do siebie. To tak, jakby listy i drzewa odwoływały się do siebie na poziomie typu, ale wykresy odwołują się do siebie na poziomie wartości.

Więc co się naprawdę dzieje?

Uważam również, że niewygodne jest przedstawienie struktur danych za pomocą cykli w czystym języku. Naprawdę problemem są cykle; ponieważ wartości mogą być współużytkowane, każdy ADT, który może zawierać element członkowski typu (w tym listy i drzewa) jest w rzeczywistości DAG (Directed Acyclic Graph). Podstawową kwestią jest to, że jeśli masz wartości A i B, gdzie A zawiera B, a B zawiera A, to żadna z nich nie może zostać utworzona, zanim istnieje druga. Ponieważ Haskell jest leniwy, możesz użyć sztuczki znanej jako Wiązanie węzła aby to obejść, ale to sprawia, że ​​boli mnie mózg (ponieważ jeszcze tego nie zrobiłem). Do tej pory zrobiłem więcej mojego zasadniczego programowania w Mercury niż Haskell, a Mercury jest surowy, więc wiązanie węzłów nie pomaga.

Zwykle, gdy napotykam to wcześniej, uciekam się do dodatkowych wskazówek, jak sugerujesz; często przy użyciu mapy od identyfikatorów do rzeczywistych elementów, a elementy zawierają odniesienia do identyfikatorów zamiast do innych elementów. Najważniejsze, że nie podobało mi się to robienie tego (poza oczywistą nieefektywnością), to to, że wydawało się to bardziej kruche, wprowadzając możliwe błędy wyszukiwania identyfikatora, który nie istnieje, lub próbując przypisać ten sam identyfikator do więcej niż jednego element. Możesz napisać kod, aby te błędy oczywiście się nie pojawiały, a nawet ukryć go za abstrakcjami, aby jedyne miejsca, w których takie błędy mogły wystąpić, były ograniczone. Ale to jeszcze jedna rzecz do popełnienia błędu.

Jednak szybkie wygooglowanie „wykresu Haskella” zaprowadziło mnie do http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Practical_Graph_Handling , który wygląda na wartościową lekturę.

W odpowiedzi shang możesz zobaczyć, jak przedstawić wykres za pomocą lenistwa. Problem z tymi reprezentacjami polega na tym, że bardzo trudno je zmienić. Sztuczka z wiązaniem węzłów jest przydatna tylko wtedy, gdy masz zamiar zbudować wykres raz, a potem on nigdy się nie zmienia.

W praktyce, jeśli rzeczywiście chcę coś zrobić z moim wykresem, używam bardziej reprezentacji pieszych:

• Lista krawędzi
• Lista sąsiedztwa
• Nadaj unikalną etykietę każdemu węzłowi, użyj etykiety zamiast wskaźnika i zachowaj skończoną mapę od etykiet do węzłów

Jeśli zamierzasz często zmieniać lub edytować wykres, polecam użycie reprezentacji opartej na suwaku Hueta. Jest to reprezentacja używana wewnętrznie w GHC dla wykresów przepływu sterowania. Możesz o tym przeczytać tutaj:

• Aplikacyjny wykres przepływu sterowania oparty na suwaku Hueta

• Hoopl: Modułowa biblioteka wielokrotnego użytku do analizy i transformacji przepływu danych

Jak wspomniał Ben, cykliczne dane w Haskell są konstruowane przez mechanizm zwany „wiązaniem węzła”. W praktyce oznacza to, że piszemy wzajemnie rekurencyjne deklaracje, używając klauzul letlub where, co działa, ponieważ wzajemnie rekurencyjne części są leniwie oceniane.

Oto przykładowy typ wykresu:

import Data.Maybe (fromJust)

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

data Graph a = Graph [Node a]

Jak widać, Nodezamiast pośrednich używamy rzeczywistych odniesień. Oto jak zaimplementować funkcję, która tworzy wykres z listy skojarzeń etykiet.

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

Bierzemy listę (nodeLabel, [adjacentLabel])par i konstruujemy rzeczywiste Nodewartości za pomocą pośredniej listy wyszukiwania (która wykonuje rzeczywiste wiązanie węzłów). Sztuczka polega na tym, że nodeLookupList(który ma typ [(a, Node a)]) jest konstruowany przy użyciumkNode , co z kolei odwołuje się do, nodeLookupListaby znaleźć sąsiednie węzły.

To prawda, wykresy nie są algebraiczne. Aby poradzić sobie z tym problemem, masz kilka opcji:

1. Zamiast wykresów rozważ nieskończone drzewa. Przedstaw cykle na wykresie jako ich nieskończone rozwinięcia. W niektórych przypadkach możesz użyć sztuczki znanej jako „wiązanie węzła” (dobrze wyjaśnionej w niektórych innych odpowiedziach tutaj), aby nawet przedstawić te nieskończone drzewa w skończonej przestrzeni, tworząc cykl w stercie; jednakże nie będziesz w stanie obserwować ani wykrywać tych cykli z poziomu Haskell, co utrudnia lub uniemożliwia wykonywanie różnych operacji na wykresach.
2. W literaturze dostępnych jest wiele algebr grafowych. Najpierw przychodzi na myśl zbiór konstruktorów wykresów opisanych w sekcji drugiej dwukierunkowej transformacji wykresów . Typową własnością gwarantowaną przez te algebry jest to, że każdy wykres można przedstawić algebraicznie; jednak, co najważniejsze, wiele wykresów nie będzie miało reprezentacji kanonicznej . Zatem strukturalne sprawdzanie równości nie wystarczy; robienie tego poprawnie sprowadza się do znalezienia izomorfizmu wykresu - znanego jako trudny problem.
3. Porzuć algebraiczne typy danych; jawnie reprezentują tożsamość węzłów, nadając im unikalne wartości (powiedzmy, Ints) i odwołując się do nich pośrednio, a nie algebraicznie. Można to uczynić znacznie wygodniejszymi, czyniąc typ abstrakcyjnym i zapewniając interfejs, który żongluje pośrednim za Ciebie. Jest to podejście przyjęte np. Przez fgl i inne praktyczne biblioteki grafów w Hackage.
4. Wymyśl zupełnie nowe podejście, które dokładnie pasuje do Twojego przypadku użycia. To bardzo trudna rzecz. =)

Tak więc każdy z powyższych wyborów ma swoje wady i zalety. Wybierz ten, który wydaje się najlepszy dla Ciebie.

Kilka innych osób wspomniało krótko o fglgrafach indukcyjnych i algorytmach grafów funkcjonalnych Martina Erwiga , ale prawdopodobnie warto napisać odpowiedź, która faktycznie daje wyobrażenie o typach danych stojących za podejściem do reprezentacji indukcyjnej.

W swoim artykule Erwig przedstawia następujące typy:

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

(Reprezentacja w fgl jest nieco inne i dobrze wykorzystuje typeklasy - ale idea jest zasadniczo taka sama).

Erwig opisuje multigraf, w którym węzły i krawędzie mają etykiety i w którym wszystkie krawędzie są skierowane. A Nodema jakąś etykietę a; krawędź ma jakąś etykietę b. A Contextto po prostu (1) lista oznaczonych krawędzi wskazujących na określony węzeł, (2) dany węzeł, (3) etykieta węzła i (4) lista oznaczonych krawędzi wskazujących od węzła. GraphMoże być pomyślany jako albo indukcyjnie Emptylub jako Contextpołączone (z &) w istniejącym Graph.

Jak zauważa Erwig, nie możemy swobodnie generować a Graphwith Emptyi &, ponieważ możemy wygenerować listę z konstruktorami Consand Nillub Treewith Leafand Branch. W przeciwieństwie do list (jak wspominali inni), nie będzie żadnej kanonicznej reprezentacji pliku Graph. To są kluczowe różnice.

Niemniej jednak to, co sprawia, że ​​ta reprezentacja jest tak potężna i tak podobna do typowych reprezentacji list i drzew przez Haskella, to fakt, że Graphtyp danych jest tutaj zdefiniowany indukcyjnie . Fakt, że lista jest definiowana indukcyjnie, pozwala nam na tak zwięzłe dopasowanie wzorców na niej, przetwarzanie pojedynczego elementu i rekurencyjne przetwarzanie reszty listy; w równym stopniu indukcyjna reprezentacja Erwiga pozwala nam na rekurencyjne przetwarzanie jednego wykresu Contextna raz. Ta reprezentacja wykresu nadaje się do prostej definicji sposobu mapowania na wykresie ( gmap), a także sposobu wykonywania nieuporządkowanych fałd na wykresach ( ufold).

Inne komentarze na tej stronie są świetne. Jednak głównym powodem, dla którego napisałem tę odpowiedź, jest to, że kiedy czytam zwroty takie jak „wykresy nie są algebraiczne”, obawiam się, że niektórzy czytelnicy nieuchronnie odniosą (błędne) wrażenie, że nikt nie znalazł dobrego sposobu na przedstawienie wykresów w Haskell w sposób, który pozwala na dopasowywanie wzorców na nich, mapowanie na nich, zwijanie ich lub ogólnie robienie tego rodzaju fajnych, funkcjonalnych rzeczy, do których przywykliśmy z listami i drzewami.

Zawsze podobało mi się podejście Martina Erwiga w „Grafach indukcyjnych i algorytmach grafów funkcjonalnych”, które możesz przeczytać tutaj . FWIW, kiedyś napisałem również implementację Scali, zobacz https://github.com/nicolast/scalagraphs .

Każda dyskusja na temat przedstawiania wykresów w Haskell wymaga wzmianki o bibliotece danych reify Andy'ego Gilla (tutaj jest artykuł ).

Reprezentacja w stylu „wiązanie węzła” może być używana do tworzenia bardzo eleganckich DSL (patrz przykład poniżej). Jednak struktura danych ma ograniczone zastosowanie. Biblioteka Gilla pozwala na to, co najlepsze z obu światów. Możesz użyć DSL „wiązania węzła”, ale następnie przekonwertować wykres ze wskaźnikami na wykres oparty na etykiecie, aby móc uruchomić na nim wybrane algorytmy.

Oto prosty przykład:

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

Aby uruchomić powyższy kod, będziesz potrzebować następujących definicji:

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

Chcę podkreślić, że jest to uproszczone DSL, ale nie ma ograniczeń! Zaprojektowałem bardzo funkcjonalny DSL, w tym ładną składnię podobną do drzewa, aby węzeł rozgłaszał początkową wartość niektórym swoim dzieciom oraz wiele wygodnych funkcji do konstruowania określonych typów węzłów. Oczywiście typ danych Node i definicje mapDeRef były znacznie bardziej zaangażowane.

Podoba mi się ta implementacja wykresu zaczerpnięta stąd

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