Speichern von Kurven in Haskell

Question

I kann leicht einen Datentyp für einen Knoten eines gerichteten Graphen definieren.

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

ich die Grafik in eine Datei speichern kann Show-Funktion, dann wiederherstellen gelesen werden. Allerdings zeigen nicht mit einem Zyklus bewältigen. Gibt es eine triviale Weise eine Grafik zu speichern und wiederherzustellen?

Answer 1

Nicht so weit ich weiß. Sie haben eine grafische Darstellung verlegenden Funktion zu schreiben.

Als erstes entscheiden, wo die Zirkularität zu brechen. In diesem Fall ist es trivial: die Knotennamen verwenden (vorausgesetzt, sie innerhalb eines Graphen eindeutig ist). Für eine komplexere Struktur, wie zum Beispiel eines Graph mit Knoten und Kanten als getrennte Arten, würden Sie sich entscheiden müssen, ob mit Knoten speichern Kanten, Knoten mit Kanten oder halten Knoten und Kanten vollständig getrennt.

Dann aufzuzählen alle Knoten im Graphen. In diesem Fall ist die offensichtliche Art und Weise der Grafik zu sammeln Knoten in einer endlichen Karte (siehe Data.Map ). Dann speichern Sie jeden Knoten als Name von einer Liste von anderen Knotennamen gefolgt.

, um die grafische Darstellung mittels Wiederherstellen der „den Bund fürs Leben“ Muster. Lesen der gespeicherten Graphen in eine Struktur von [(String, [String])]. Dann kann die ursprüngliche Graph mit dem folgenden Code rekonstruiert werden:

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

Beachten Sie die gegenseitige Rekursion: Tabelle nennt makeNode, die Anrufe FindNode, die Tabelle nennt. Dank lazy evaluation dies das Richtige tut .

Edit: Code nun getestet und leicht erweitert

.

Answer 2

Ja und nein. Es kann über Domain-Wissen über die Struktur Ihres Knotentypen und definiert einen Begriff der Gleichheit, die Sie testen, können mit einer Liste oder Karte von Knoten gesehen so weit zu erholen Sharing kombiniert durchgeführt werden. Im pathologischen Fall gibt es eine Vorstellung von einem StableName in GHC einen solchen Begriff zu konstruieren.

An einem anderen Front Matt Morrow hat einiges an Arbeit zu tun in Form einer Assemblersprache .S-Datei beliebige zyklische Daten mit seiner praktisch Vakuum Bibliothek zu extrahieren. Also entweder das, oder Vakuum könnte Ihre Bedürfnisse anzupassen.

In der Regel vermeiden Voodoo und Tracking-Knoten so weit in einer Karte zu sehen ist wahrscheinlich die vernünftigste und wartbare Lösung.