Guardar gráficos en Haskell

Question

Puedo definir fácilmente un tipo de datos para un nodo de un gráfico dirigido.

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

Puedo guardar el gráfico en un archivo usando la función show, luego restaurarlo usando read. Sin embargo, mostrar no hará frente a un ciclo. ¿Hay alguna manera trivial de guardar y restaurar un gráfico?

Answer 1

No es lo que yo sé. Tienes que escribir una función para atravesar gráficos.

Primero, decida dónde romper la circularidad. En este caso, es trivial: use los nombres de los nodos (suponiendo que sean únicos dentro de un gráfico). Para una estructura más compleja, como un gráfico con nodos y bordes como tipos separados, tendría que decidir si almacenar bordes con nodos, nodos con bordes o mantener los nodos y bordes completamente separados.

A continuación, enumere todos los nodos en el gráfico. En este caso, la forma obvia es atravesar el gráfico que recoge los nodos en un mapa finito (ver Data.Map). A continuación, almacene cada nodo como un nombre seguido de una lista de otros nombres de nodos.

Recuperar el gráfico significa utilizar el patrón "atar el nudo". Lea el gráfico almacenado en una estructura de [(String, [String])]. A continuación, el gráfico original puede ser reconstruido con el siguiente código:

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 

Nota la recursión mutua: mesa de llama makeNode, que llama findNode, que llama a la mesa. Thanks to lazy evaluation this does the Right Thing.

Edit: código ahora probado y ligeramente expandido.

Answer 2

Sí y no. Se puede hacer a través del conocimiento de dominio de la estructura de su tipo de Nodo y definir alguna noción de igualdad que pueda probar, combinada con una lista o mapa de nodos vistos hasta ahora para recuperar el intercambio. En el caso patológico hay una noción de un nombre estable en GHC para construir tal noción.

En otro frente Matt Morrow ha estado haciendo un trabajo para extraer en forma de un archivo ensamblador .S archivo, datos cíclicos arbitrarios utilizando su práctica biblioteca de vacío. Entonces o eso o la aspiradora puede adaptarse a sus necesidades.

En general, evitar el vudú y los nodos de seguimiento vistos hasta ahora en un mapa es probablemente la solución más racional y sostenible.