换句话说，我们能否有效地对持久数据结构中的多对多关系进行建模？
建议使用一对单向多图。但是，我不确定这对于在持久数据结构中的删除效果如何。假设我们有键 1..4 到值“1”..“4”，假设它们每个都引用所有其他的，所以我们有两个在两个方向上看起来都非常相似的映射：
{1 => ["2","3","4"], 2 => ["1","3","4"], ...} {"1" => [2,3, 4], "2" => [1,3,4], ...}
现在我们要从系统中完全删除项目 1。这需要在第一个映射中更改一个节点，但它需要在第二个映射中更改 n-1 个节点。对于成千上万的 n （这可能在我正在考虑的情况下），那不是相当昂贵吗？或者多图是否针对处理这种类型的更改进行了优化？这是一个病态的案例，但仍然...
四叉树似乎是一个迷人的想法。我要多考虑一下。
最简单的方法是使用一对单向地图。它有一些成本，但您不会变得更好（使用专用二叉树可能会变得更好，但是如果您必须自己实现它，则需要付出巨大的复杂性成本）。本质上，查找速度会一样快，但添加和删除速度会慢一倍。这对于对数运算来说还不错。这种技术的另一个优点是，如果您有可用的键或值类型，您可以使用专门的映射类型。对于特定的通用数据结构，您不会获得那么多的灵活性。
一个不同的解决方案是使用四叉树（而不是将 NxN 关系视为一对 1xN 和 Nx1 关系，您将其视为您的类型的笛卡尔积 (Key*Value) 中的一组元素，即空间飞机），但我不清楚时间和内存成本是否比两张地图更好。我想它需要进行测试。
最后，我有一个令人兴奋的非常规递归数据结构可以做到这一点，但我找不到它的英文参考。
编辑：我刚刚为这个神秘的数据结构快速粘贴了原始代码的改编版本。
构造证明：Haskell 的bimap包。
Bimap 本质上是其两种参数类型的子集之间的双射
它是如何实施的？
data Bimap a b = MkBimap !(M.Map a b) !(M.Map b a)
作为一对单向地图。