我想使用一种行为类似于简单的对列表[(a,b)]作为字典的类型,将类型的键映射到类型a的值b,同时保持"用户指定的",定义键的顺序.(就像普通列表一样 - 我希望能够"附加"一个项目,然后将其识别为"最后一个元素".)但是我希望在键上进行随机访问查找,而不是线性性能,即Data.Map提供什么.除了定义其顺序的键列表之外,一种选择是仅维护普通映射:
data OrderedDict a b = OrderedDict (Map a b) [a]
然后定义append使两个密钥集合保持同步的操作等.虽然维护两个相同密钥的独立集合似乎很难看.是否有现成的数据类型已经将有序键与按键进行有效的随机访问查找相结合？
除非我完全误解你的问题，否则 Data.Map 正是这样做的，使用键类型的Ord实例进行排序。由于它是二叉树，因此实现也使键保持有序。
Data.Map.keys按升序为您提供地图的键；由于 Map 的转换（例如map）纯粹是函数式的，因此遍历的顺序无关紧要，并且从 Map 中获取键序列或键/值对的所有方法都会为您提供一个有序列表。