在Haskell中保存图表

Question

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

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

我可以使用show函数将图形保存到文件中，然后使用read函数恢复它。但是，如果有一个循环，show函数将无法处理。是否有一种简单的方法来保存和恢复一个图形？

- luntain

Answer 1

据我所知，不行。您需要编写一个遍历图形的函数。

首先，确定断开循环依赖的位置。在这种情况下，它是微不足道的：使用节点名称（假设它们在图中是唯一的）。对于更复杂的结构，例如将节点和边作为单独类型的图形，您必须决定是将边存储在节点中，节点存储在边中，还是完全将节点和边分开存储。

然后枚举图中的所有节点。在这种情况下，明显的方法是遍历图形并收集节点到有限映射中（请参见Data.Map）。然后将每个节点存储为名称，后跟其他节点名称的列表。

恢复图形意味着使用“打结”的模式。读取存储的图形到[(String，[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，makeNode调用findNode，findNode调用表格。由于惰性求值，这样做是正确的。感谢延迟求值实现。

编辑：代码已经测试并略作扩展。

- Paul Johnson

Answer 2

是和否。它可以通过对您的节点类型结构的领域知识进行定义某种等式概念并进行测试，再结合先前看到的节点的列表或映射来恢复共享的方式来完成。在病态情况下，GHC 中有一个 StableName 的概念来构建这样的概念。

在另一个方面，Matt Morrow 一直在使用他方便的 vacuum 库，以 .S 文件的形式提取任意循环数据。因此，无论是那个库都可能满足您的需求。

通常避免使用神秘方法并在映射中跟踪先前看到的节点可能是最合理和可维护的解决方案。

- Edward Kmett