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

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.如果有一个条目,则该节点是干净的,不必再次写入.

优点:不会将内部暴露给用户

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

结论

这是我能想到的两种方法.第一个应该更有效,第二个更令人愉悦.我希望你对我的想法发表评论,也许有人甚至会考虑更好的方法？

[编辑]合理

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

一方面,您应该尝试通过使用类型系统来处理错误.上述用户当然是系统中下一层(即我)的设计者.通过处理纯树表示,将无法发生某些类型的错误.对文件中树的所有更改都应位于一个位置.这应该使推理更容易.

另一方面,我可以实现类似的东西insert :: FilePath -> Key -> Value -> IO ()并完成它.但是当我通过更新树来保存(一种)日志时,我将失去一个非常好的特性.事务(即合并多个插入)只是在内存中处理同一个树并将差异写回文件.

Answer 1

我对 Haskell 很陌生，所以我不会展示代码，但希望我的解释可以帮助解决问题。

首先，为什么不只向用户公开 MemTree，因为这就是他们将更新的内容，并且 FileTree 可以保持完全隐藏。这样，例如，如果您想将其更改为数据库，用户就不会看到任何差异。

因此，既然 FileTree 是隐藏的，为什么不在要更新时读入它，然后就有偏移量，因此进行更新，然后再次关闭文件。

保留偏移量的一个问题是它会阻止另一个程序对文件进行任何更改，在您的情况下这可能没问题，但我认为作为一般规则，这是一个糟糕的设计。

我看到的主要变化是 MemTree 不应该是懒惰的，因为文件不会保持打开状态。