Haskell中处理多重索引集合的最佳方式是什么？

Question

在C++和其他语言中，附加库实现了一个多索引容器，例如Boost.Multiindex。也就是说，它是一个存储一种类型值的集合，但维护了多个不同的索引。这些索引提供了不同的访问方法和排序行为，例如map、multimap、set、multiset、array等等。多索引容器的运行时复杂度通常是各个索引复杂度之和。

在Haskell中是否有相应的库或者人们自己组合呢？具体而言，最符合惯用法的方法是如何实现一个T类型的集合，既包含一个基于set的索引（T是Ord的实例），又包含一个基于map的索引（假设每个T都可以提供类型为K的键值，无论是显式地还是通过函数T -> K）？

- David Joyner

Answer 1

我今天早上上传了IxSet到Hackage，

http://hackage.haskell.org/package/ixset

Ixset提供了具有多个索引的集合。

Ixset作为happstack-ixset已经存在很长时间。这个版本移除了与任何happstack特定内容的依赖，并成为IxSet的新官方版本。

另一个选择是kdtree：

darcs get http://darcs.monoid.at/kdtree

kdtree旨在通过提供更高的类型安全性和更好的时间和空间使用率来改进IxSet。当前版本似乎在这三个方面表现良好 - 但它还没有准备好投入使用。欢迎更多的贡献者加入。

- stepcut

---

kdtree的链接已经失效。 - Matt Joiner

Answer 2

在每个元素都有唯一密钥的简单情况下，您可以使用Map并提取密钥来查找元素。在稍微不那么简单的情况下，每个值仅具有可用的密钥，一个简单的解决方案是像Map K (Set T)这样的东西。直接查找一个元素需要先提取密钥，索引Map以查找共享该密钥的元素集合，然后查找所需的元素。

大多数情况下，如果可以通过上述方式（简单转换和嵌套）轻松完成某些任务，那么最好采用这种方式进行操作。但是，由于明显的原因，这些方法都无法很好地推广到例如具有多个独立键或可能无法使用的键的情况。

此外，我不知道是否存在任何广泛使用的标准实现。例如，来自 happstack 的 IxSet 似乎基本符合要求。我怀疑这里适度适合大多数人的解决方案会导致效益/复杂性比率较低，因此人们倾向于根据特定需求自己开发。

直觉上，这似乎是一个更适合不作为单个实现，而是作为一系列原语的问题，这些原语可以比Data.Map更灵活地组合，以创建特定的专用结构。但这对于短期需求并不是很有帮助。

- C. A. McCann

Answer 3

针对这个特定问题，您可以使用Bimap。但是一般情况下，我不知道是否存在常见的用于多映射或多索引容器的类。

- Daniel Wagner

Answer 4

我认为最简单的方法是使用Data.Map。虽然它被设计为使用单个索引，但当您多次插入相同元素时，大多数编译器（尤其是GHC）会将值放置在同一位置。一个独立的Multimap实现不会那么高效，因为你想要根据它们的索引找到元素，所以你不能简单地将每个元素与多个索引关联起来 - 比如[([key], value)] - 因为这样会非常低效。

然而，我没有查看Boost Multimaps的实现，无法确定是否有优化的方法来实现。

- gereeter

---

“虽然它被设计为使用单个索引，但当您多次插入相同元素时，大多数编译器（特别是GHC）将使值放置在同一位置。”这句话的意思是什么？ - Daniel Wagner

如果您将同一项插入Map 5次，它不会占用插入一次的五倍空间，因为在内部，所有五个值都是指向同一位置的指针。 - gereeter

Answer 5

我是否正确理解了问题？T和K都有一个顺序。有一个函数键:: T-> K，但它不是保序的。希望管理一组Ts，通过T顺序和K顺序进行索引（以便快速访问）。更一般地说，可能希望通过一堆顺序key1 :: T-> K1，.. keyn :: T-> Kn索引T元素，并且恰好在这里key1 = id。这是图片吗？

我认为我同意gereeter的建议，即解决方案的基础只是保持一堆(Map K1 T, .. Map Kn T)同步。在映射中插入键值对既不会复制键也不会复制值，仅分配额外的堆以在索引中的正确位置创建新条目。适当地键入相同的值，插入多个索引不应破坏共享（即使其中一个键是值）。值得包装结构在API中，以确保对值的任何后续修改只计算一次并共享，而不是为索引中的每个条目重新计算。

底线：应该可以维护多个映射，确保值是共享的，即使键顺序是分开的。

- pigworker

---

实现的复杂性在于任意投影函数可能不仅仅截取值的片段，而是从中计算键，键之间可能存在关系，除了作为索引使用外，它们可能还有其他重要的用途，使用多个键进行近似匹配可能很有用，笨拙的类型组合结构包括有效键...我的经验是需要一个没有进一步结构的多键映射有点罕见，而且为此提供的API可能会干扰添加这样的结构。 - C. A. McCann

感谢你们两位提供的有用答案。最终我自己动手实现了（感谢Conor提醒不要共享）。只是想确保我没有错过什么超级酷的Haskell库。我仍然处于每天都被震撼的阶段... - David Joyner