Salvando gráficos em Haskell

Question

eu posso facilmente definir um tipo de dados de um nó de um grafo orientado.

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

eu posso salvar o gráfico para um arquivo usando o programa de função, em seguida, restaurá-lo usando leitura. No entanto, show não vai lidar com um ciclo. Existe uma maneira trivial para salvar e restaurar um gráfico?

Answer 1

Não tanto quanto eu sei. Você tem que escrever uma função-percorrendo gráfico.

Em primeiro lugar, decidir onde quebrar a circularidade. Neste caso, é trivial: usar os nomes de nó (assumindo que eles são únicos dentro de um gráfico). Para uma estrutura mais complexa, como um gráfico com nós e arestas como tipos separados, você teria que decidir se deseja armazenar as bordas com nós, nós com bordas, ou mantê nós e arestas completamente separado.

Em seguida, enumerar todos os nós no gráfico. Neste caso, a maneira óbvia é a de atravessar o gráfico coleta de nós em um mapa finito (ver Data.Map ). Em seguida, armazenar cada nó como um nome seguido por uma lista de outros nomes de nós.

Recuperando os meios gráfico usando o "amarrar o nó" padrão. Ler o gráfico armazenado numa estrutura de [(String, [String])]. Em seguida, o gráfico original pode ser reconstruído com o código a seguir:

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

Observe a recursão mútua: mesa chama makeNode, que chama findNode, que chama mesa. para avaliação preguiçosa isso faz o coisa certa.

Editar:. código agora testado e ligeiramente ampliada

Answer 2

Sim e não. Isso pode ser feito através de conhecimento de domínio da estrutura do seu tipo de nó e definir alguma noção de igualdade que você pode testar, combinado com uma lista ou mapa de nós vimos até agora para recuperar partilha. No caso patológico há uma noção de um StableName em GHC para construir tal noção.

Em outra frente Matt Morrow tem vindo a fazer algum trabalho ao extrato na forma de uma linguagem assembly .S arquivo, os dados cíclicos arbitrários usando sua mão biblioteca vácuo. Então isso ou vácuo pode atender às suas necessidades.

Em geral evitando vodu e rastreamento nós vimos até agora em um mapa é provavelmente a solução mais racional e sustentável.