8

我想使用一种行为类似于[(a,b)]用作字典的简单对列表的类型，将 type 的键映射到 typea的值b，同时保持“用户指定的”、定义的键顺序。（即就像普通列表一样 - 我希望能够“附加”一个项目，然后将其识别为“最后一个元素”。）但是我希望随机访问查找具有优于线性性能的键，即Data.Map提供什么. 一种选择是除了定义其顺序的键列表之外仅维护一个普通映射：

data OrderedDict a b = OrderedDict (Map a b) [a]

然后定义append使两个密钥集合保持同步的操作等。维护相同键的两个单独集合似乎很难看。是否有现成的数据类型已经将有序键与高效的随机访问键查找相结合？

4

3 回答 3

4

看看ixset库 - 它允许您维护由多个列索引的集合（在您的情况下是按a和按Int）。这比手动保持地图一致更易于维护

于 2012-06-08T09:05:19.357 回答
3

除非我完全误解了您的问题，否则 Data.Map 正是这样做的，它使用键类型的Ord实例进行排序。由于它是二叉树，因此实现也保持键的顺序。

Data.Map.keys按升序为您提供地图的键；由于 Map 的转换（例如 ）map是纯函数式的，因此遍历的顺序是无关紧要的，并且从 Map 中获取一系列键或键/值对的所有方法都会为您提供一个有序列表。

于 2012-06-08T06:50:30.893 回答
3

如果除了 O(log n) 查找/插入之外，您只想保留一些固定顺序（例如插入时间），您可以简单地使用多个映射并同时更新它们：

  1. Map a b用于存储实际数据，以及
  2. Map Int a这为您提供了顺序中的第 i 个键。（如果您还需要查询给定键的索引，您可以添加一个Map a Int）
于 2012-06-08T07:29:02.557 回答