Zapisywanie wykresów w Haskell

Question

Mogę łatwo zdefiniować typ danych dla węzła skierowanego wykresu.

data Node = Node String [Node] derving (Show, Read) 

Mogę zapisać wykres do pliku przy użyciu funkcji show, a następnie przywrócić go za pomocą odczytu. Jednak show nie poradzi sobie z cyklem. Czy istnieje prosty sposób na zapisanie i przywrócenie wykresu?

Answer 1

Nie tak daleko, jak wiem. Musisz napisać funkcję przechodzenia przez wykres.

Najpierw zdecyduj, gdzie przerwać cykliczność. W takim przypadku jest to banalne: użyj nazw węzłów (zakładając, że są one unikalne na wykresie). Dla bardziej złożonej struktury, takiej jak wykres z węzłami i krawędziami jako oddzielnymi typami, trzeba by zdecydować, czy przechowywać krawędzie z węzłami, węzłami z krawędziami, czy też utrzymać węzły i krawędzie całkowicie oddzielone.

Następnie należy wyliczyć wszystkie węzły na wykresie. W tym przypadku oczywistym sposobem jest przechodzenie przez wykres zbierający węzły na skończonej mapie (patrz Data.Map). Następnie zapisz każdy węzeł jako nazwę, a następnie listę innych nazw węzłów.

Odzyskiwanie wykresu oznacza użycie wzoru "wiązania węzła". Odczytaj zapisany wykres w strukturze [(String, [String])]. Następnie oryginalny wykres można zrekonstruować z następującego kodu:

import qualified Data.Map as M 

data Node = Node String [Node] 

instance Show Node where 
    show (Node name others) = "Node " ++ show name ++ 
     " " ++ show (map nodeName others) 
     where nodeName (Node n _) = n 

restoreGraph :: [(String, [String])] -> M.Map String Node 
restoreGraph pairs = table 
    where 
     table = M.fromList $ map makeNode pairs 
     makeNode (name, others) = (name, Node name $ map findNode others) 
     findNode str = fromJust $ M.lookup str table 

zanotować wzajemnej rekursji: tabela nazywa makeNode, która wywołuje findNode, która wywołuje tabeli. Thanks to lazy evaluation this does the Right Thing.

Edycja: kod teraz testowany i nieznacznie rozszerzony.

Answer 2

Tak i nie. Można tego dokonać poprzez znajomość struktury domeny typu twojego węzła i zdefiniowanie pojęcia równości, które możesz przetestować, w połączeniu z listą lub mapą węzłów, które do tej pory widziano, aby odzyskać współdzielenie. W patologicznym przypadku istnieje pojęcie StableName w GHC, aby zbudować takie pojęcie.

Na innym froncie Matt Morrow wykonał pewną pracę do wyodrębnienia w formie pliku asem złożonego języka .S, arbitralne cykliczne dane za pomocą podręcznej biblioteki próżniowej. Tak więc albo próżnia może odpowiadać twoim potrzebom.

Generalnie unikanie voodoo i śledzenia węzłów widocznych do tej pory na mapie jest prawdopodobnie najbardziej racjonalnym i możliwym do utrzymania rozwiązaniem.