节省图在Haskell

Question

我可以轻松地定义的数据类型为一个节点的一个向图。

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

我可以节省图以一个文件使用的显示功能，然后再恢复它的使用阅读。然而，显示出将无法应付一个周期。有一个微不足道的方式保存和恢复的图表?

Answer 1

不，我知道。你必须要写一个图穿越的功能。

第一，决定在哪里以打破的循环.在这种情况下，它是微不足道的：使用节点名(假定它们是唯一一个图)。对于一个更复杂的结构，例如图有节点和边缘作为单独的类型，你必须决定是否存储边节点，节点与边缘，或者保持的节点和边缘完全分开。

然后列举的所有节点的曲线图。在这种情况下显而易见的方法是历图收集的节点，在一个有限的地图(见 数据。地图).然后储存每个节点的名称随后通过一系列其他节点的名称。

恢复的图表的装置使用的"结婚"的图案。读取所储存的图形成一个结构[(String,[串的])].然后原有的图表可以重建与下列代码：

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

注意相互递归:表呼吁makeNode，其中要求findNode，其中要求表。 由于懒惰的评价该做正确的事.

编辑： 代码现在进行测试和微扩大。

Answer 2

是，也不是。它可以通过你的节点类型的结构的领域知识和定义，你可以测试平等的一些概念，与迄今所看到恢复共享节点列表或地图相结合来完成。在病理情况下，存在在一个GHC StableName的概念来构造这样的概念。

在另一个前马特莫罗已经做了一些工作以汇编语言.S文件的形式来提取，用他方便的真空库任意循环数据。所以，要么或真空可能会满足您的需求。

在一般避免在地图迄今为止看到伏都和跟踪节点可能是最合理的和维护的解决方案。