haskell - 如何创建两个复杂数据结构的差异？

Question

问题说明:

我目前正在寻找一个优雅和/但有效的解决方案来解决我认为很常见的问题。考虑以下情况:

我定义了一个基于 BTree 的文件格式是这样定义的(以简化的方式):

data FileTree = FileNode [Key] [FileOffset]
              | FileLeaf [Key] [Data]

从文件中读取并将其写入惰性数据结构已实现并且工作正常。这将导致以下实例:

data MemTree = MemNode [Key] [MemTree]
             | MemLeaf [Key] [Data]

现在我的目标是拥有一个通用函数 updateFile :: FilePath -> (MemTree -> MemTree) -> IO ()将在 FileTree 中读取并将其转换为 MemTree，应用 MemTree -> MemTree函数并将更改写回树结构。问题是必须以某种方式保存 FileOffsets。

我有两种方法来解决这个问题。他们都缺乏优雅和/或效率:

方法 1:扩展 MemTree 以包含偏移量

这种方法扩展了 MemTree 以包含偏移量:

data MemTree = MemNode [Key] [(MemTree, Maybe FileOffset)]
             | MemNode [Key] [Data]

然后读取函数将读取 FileTree并存储 FileOffset旁边的 MemTree引用。写入将检查引用是否已经具有关联的偏移量，如果有，则仅使用它。

优点:易于实现，无需开销即可找到偏移量

缺点:向负责将偏移量设置为 Nothing 的用户公开内部信息。

方法 2:在二级结构中存储偏移量

解决此问题的另一种方法是阅读 FileTree并创建一个 StableName.Map坚持 FileOffsets .这样(如果我正确理解 StableName 的语义)应该可以采用最终的 MemTree并查找 StableName StableName.Map 中的每个节点.如果有条目，则节点是干净的，不必再次写入。

优点:不向用户公开内部结构

缺点:涉及在 map 中查找的开销

结论

这是我能想到的两种方法。第一个应该更有效，第二个更悦目。我希望您对我的想法发表评论，也许有人甚至有更好的方法？

[编辑] 合理

我正在寻找这样的解决方案有两个原因:

一方面，您应该尝试使用类型系统在错误出现之前对其进行处理。前面提到的用户当然是系统下一层的设计者(即我)。通过处理纯树表示，某些类型的错误将不会发生。对文件中树的所有更改都应该在一个地方。这应该使推理更容易。

另一方面，我可以实现类似 insert :: FilePath -> Key -> Value -> IO ()并完成它。但是，当我通过更新树来保留(一种)日志时，我将失去一个非常好的特征。事务(即合并多个插入)只是在内存中的同一棵树上工作并将差异写回文件的问题。

Answer 1

我认为包Data.Generic.Diff可能会做你想做的事。它引用了某人的论文来了解它是如何工作的。