对派生树进行有效比较的搜索树

Question

我正在寻找Haskell中的搜索树实现，它为共享结构的树提供了一个有效的差异函数。例如，如果我有一个很大的树x (例如，有数百万个元素)，我在其中插入了三个新元素来生成x'，我希望能够调用difference x x'来获取这些元素，其中difference的实现使得只需访问两个树之间没有共享的节点就可以找到感兴趣的元素。

我脑海中的场景类似于版本控制系统，其中每个新版本都是从前一个版本派生出来的，我们可能需要找出任何两个版本之间的差异。

数据结构还应支持有效的插入、删除和查找操作(例如O(log ))。

这样的实现将依赖于System.Mem.StableName或Data.Unique.Id之类的东西来唯一地标记树中的每个节点，从而允许difference函数有效地识别共享结构并避免陷入其中。

像这样的东西已经存在了吗？如果没有，什么是实现它的好策略？我正在考虑修改一些东西，比如吴兴波的RBTree实现，以便为每个节点添加唯一的标签，但我对其他选择持开放态度。

Answer 1

如果您想知道单个大树x的差异，那么您可以显式跟踪更改，而不是计算差异：

-- extend a map with some insertions and deletions
data ExtMap k v = ExtMap { baseMap :: Map k v, changes :: Map k (Maybe v) }

fromMap :: Map k v -> ExtMap k v
fromMap x = ExtMap x Map.empty

toMap :: Ord k => ExtMap k v -> Map k v
toMap (ExtMap x y) = Map.mergeWithKey (\_ _ u -> u) id id x y

lookup :: Ord k => k -> ExtMap k v -> Maybe v
lookup k (ExtMap x y) = case Map.lookup k y of
  Just mv -> mv             -- if there is a change for this key, return that
  Nothing -> Map.lookup k x -- otherwise look in the base map

insert :: Ord k => k -> v -> ExtMap k v -> ExtMap k v
insert k v (ExtMap x y) = ExtMap x (Map.insert k (Just v) y)

delete :: Ord k => k -> ExtMap k v -> ExtMap k v
delete k (ExtMap x y) = ExtMap x (Map.insert k Nothing y)

Answer 2

我自己进行了implemented this，修改了吴兴波的RBTree，以支持用版本信息注释的值，然后可以使用diffVersion有效地计算差异。