Niektóre prace Conora McBride'a, Diff , Dissect , wiążą pochodną typów danych z ich „typem jednootworowych kontekstów”. Oznacza to, że jeśli weźmiesz pochodną typu, pozostanie ci typ danych, który pokazuje, jak typ danych wygląda od wewnątrz w danym punkcie.

Na przykład, jeśli masz listę (w Haskell)

data List a = [] | a : List a

to odpowiada

data List a = 1 + a * List a

a poprzez małą matematyczną magię pochodną jest

data ListDeriv a = List a * List a

co jest interpretowane w ten sposób, że w dowolnym punkcie listy będzie lista po lewej stronie i lista po prawej stronie. Możemy spakować oryginalną listę za pomocą pochodnej struktury danych.

Teraz jestem zainteresowany zrobieniem czegoś podobnego z wykresami. Wspólną reprezentacją wykresów jest zestaw wierzchołków i krawędzi, który można naiwnie implementować za pomocą typu danych, takiego jak:

data Gr a b i = Gr [(i,a)] [(i,i,b)]

Jeśli dobrze to rozumiem, pochodna tego typu danych w odniesieniu do indeksu graficznego ipowinna być podobna.

data GrDeriv a b i = d/di (Gr a b i)
     = d\di ( [a*i] * [b*i^2] )
     = (d\di [a*i]) * [b*i^2] ) + [a*i]*(d/di [b*i^2])
     = (a* [a*i] * [a*i]) * [b*i^2] ) 
       + [a*i] * (2*b*i) *[b*i^2]*[b*i^2])
     = InNodes { nodesLeft :: [(a,i)]
               , nodeLbl :: a
               , nodesRight :: [(a,i)]
               , edges :: [(b,i,i)] }
     | InEdges { nodes :: [(a,i)]
               , adjNode :: Either (b,i) (b,i)
               , edgesLeft :: [(b,i,i)]
               , edgesRight :: [(b,i,i)] }

Osiągnąłem to dzięki zastosowaniu reguły produktu i reguł łańcucha dla instrumentów pochodnych i chociaż możliwe, że są pewne błędy, wydaje się, że są zgodne z ogólnym schematem. W tej strukturze będziesz się skupiał na Węzłach (konstruktor InNodes) lub Krawędziach (na krawędziach) i biorąc pod uwagę miejsce, w którym zobaczysz odpowiednie dane.

Ale nie na to liczyłem. Miałem nadzieję na konstrukcję bliższą interfejsowi funkcjonalnej biblioteki grafów Martina Erwigsa. W szczególności chcę zobaczyć w węźle kontekst reprezentujący etykietę węzła i dwie listy przyległości, jedną dla poczty wychodzącej, drugą dla poczty przychodzącej.

Node a b = ([(i,b)],a,[(i,b)])

Widzę jednak nadzieję, ponieważ reprezentacja przylegania ma pewne terminy wspólne z pochodną, ​​samotną etykietą a, w każdym miejscu otworu, reprezentacją / rozcięciem przyległości każdej krawędzi.

Ponieważ pochodna nie jest taką samą funkcją jak oryginał, ale całkowanie pochodnej jest (kindof), czy istnieje jakiś analog analogowy, który posłuży do przekształcenia pochodnej w zbiór kontekstów węzłów? Pamiętaj, że nie jest to bezpośrednia integracja w celu odzyskania oryginalnej struktury, ale struktura równoważna oryginałowi, ale w bardziej przyjaznej algorytmowi reprezentacji.

Jeśli tak, mam nadzieję, że struktury typów relacji mogą być określone przez jakiś łatwy język „zestaw wierzchołków i krawędzi” i mogę uzyskać wydajną bibliotekę do pracy z tą strukturą. Taka implementacja może być wykorzystana do badania struktur „poza teorią grafów”: hiper grafy, proste kompleksy ...

Więc. Czy ten pomysł wydaje się wykonalny? Przydatny? Czy są jakieś badania dotyczące tego rodzaju rzeczy, o których mógłbym przeczytać więcej?

Uzupełnienie

$G=(V,E)$

$G=(V,E)$$I$$V$$E$

$$G = I \to (V * I \to E)$$

Jestem pewien, że można to wyrazić (teoria kategorii?) Jako

$$G = (V * E^{I})^{I} \tag{1}$$

lub

$$G = V^I * E^{I*I}$$

$(1)$

$$G' = \ln(V * E^{I}) * (V * E^{I})^{I} * (\ln(E) * V * E^{I})$$

Z jednej strony wydaje mi się, że to obiecuje, ale brakuje mi wyrafinowania, aby pójść dalej. Wiem, że musi być trochę pracy nad dalszym badaniem połączenia.

* W przypadku gdy link kiedykolwiek się zepsuje, cytowanie: Rhee, Injong i in. „DRAND: rozproszone losowe planowanie TDMA dla bezprzewodowych sieci ad hoc.” Transakcje IEEE na urządzeniach mobilnych 8.10 (2009): 1384–1396.

Twój typ Grtak naprawdę nie odpowiada grafom, ponieważ zawiera wiele instancji, które wyraźnie nie są grafami, ponieważ indeksy krawędzi nie muszą być rzeczywistymi indeksami wierzchołków.

Na przykład,

$$V = \{A, B\} \;\;\;\; E = \{(C, D, e)\}$$

nie jest wykresem, ale jest dozwolony w twoim typie jako

Gr [(1, A), (2, B)] [(3, 4, e)]

Przeciwnie, twoja Grdosłownie odpowiada liście oznaczonych indeksów i osobnej, niepowiązanej liście oznaczonych par indeksów. Dlatego otrzymujesz taką „dosłowną” pochodną Gr, która nie odpowiada „dziurom” na wykresach.

Istnieje również niefortunny problem dbania o kolejność wierzchołków / krawędzi (widocznych w nodesLeft/Righti edgesLeft/Rightróżnicach), ale można to naprawić za pomocą Setzamiast listy.

---

Oto typ wyrażony w Haskell, który moim zdaniem bardziej odpowiada (niepustym) wykresom:

data Graph v e = Lone v | Joined v (Graph (v, ([e], [e])) e)

Dla uproszczenia rozważę zamiast tego kompletne, proste, bezkierunkowe wykresy:

data Graph v e = Lone v | Joined v (Graph (v, e) e)

(Aby rozluźnić kompletność, e = Boolzaznacz obecność krawędzi)

Zauważ, że Graphjest rekurencyjny (i faktycznie parametrycznie rekurencyjny). To pozwala nam ograniczyć ten typ do samych wykresów, a nie tylko list przyległości w połączeniu z listami wierzchołków.

Napisane bardziej algebraicznie,

$$G(v, e) = v + v * G(v * e, e)$$

$e$$v$$G$

$$G(v) = v + v * G(v * e)$$

Przez wielokrotne rozszerzanie otrzymujemy punkt stały

$$G(v) = v^1 e^{\binom 1 2} + v^2 e^{\binom 2 2} + v^3 e^{\binom 3 2} + v^4 e^{\binom 4 2} + \dots$$

Ma to sens, ponieważ jest (kompletny) wykres

• Jeden wierzchołek i bez krawędzi
• Dwa wierzchołki i jedna krawędź
• Trzy wierzchołki i trzy krawędzie
• Cztery wierzchołki i cztery wybierają 2 = 6 krawędzi
• …

Wywołaj typ wykresów wielkości . Następnie$k$$G_k(v) = v^k e^{\binom k 2}$$G(v) = G_1(v) + G_2(v) + \dots$

który ma pochodną

$$\frac d {dv} G(v) = \sum_{i=1} G_i'(v)$$

Pochodna

$$G_k'(v) = \frac d {dv} \left[ v^k e^{\frac {k(k-1)} 2} \right] = k v^{k-1} e^{\frac {k(k-1)} 2}$$

Zauważ, że , tak więc$G_{k-1}(v) = v^{k-1} e^{\frac {(k-1)(k-2)} 2}$$G_k'(v) = G_{k-1}(v) * k * e^{k-1}$

Oznacza to, że pochodną wykresu węzła jest wykres węzła , w połączeniu z krawędziami od usuniętego węzła do pozostałych węzłów oraz indeksem który węzeł zajmował na liście wierzchołki.$k$$k-1$$k-1$$k-1$$k$

data SimpleGraph v e = Lone v | Joined v (SimpleGraph (v, e) e)

data SimpleGraphHole v e = Empty
                         | InsertLater v (SimpleGraphHole (v, e) e)
                         | InsertHere (SimpleGraph (v, e) e)

Ustalanie kolejności na tym wykresie

Ta wersja struktury danych Wykres jest zasadniczo listą połączoną, dlatego koduje kolejność wierzchołków. Chociaż można to naprawić w wersji z listą przylegania za pomocą zestawu, nie jest to tutaj tak bezpośrednie.

Myślę, że możesz zmodyfikować strukturę danych drzewa, aby wykonać ten sam rodzaj rekurencji parametrycznej, z rdzeniem pełniącym rolę „głowy” SimpleGraph. Dzięki interfejsowi powstałych zestawów drzew, kolejność / podstawowa struktura staje się niewidoczna (lub nawet kanoniczna, jeśli nie jesteś zainteresowany szybkimi aktualizacjami).

Twoja proponowana pochodna

Zaproponowałeś typ pochodnej; Zmienię to, aby połączyć etykiety i indeksy:([(v,e)], [(v,e)])

Można to zintegrować jako czyli , lub po prostu . Nie ma wystarczającej ilości informacji do zrekonstruowania całego wykresu , ponieważ informacje o „krawędzi” identyfikują tylko jeden wierzchołek.$\int \frac 1 {(1 - ve)^2}$$C + \frac v {1 - ve}$(v, [(v, e)])