用于双重链接列表和哈希表模式的Haskell替代方案

Question

命令式编程中有一个有用的模式，即，将双链表与哈希表结合使用以在链表中进行恒定时间查找。

这种模式的一种应用是在LRU缓存中。双链表的头部将包含高速缓存中最近最少使用的条目，而双链表的最后一个元素将包含最近使用的条目。哈希表中的关键字是条目的关键字，值是指向与关键字/条目相对应的链表中节点的指针。当在缓存中查询条目时，哈希表将用于指向其在链表中的节点，然后将该节点从其在链表中的当前位置删除，并放置在链表的末尾-list使其成为最近使用的条目。为了驱逐，我们仅从链接列表的开头删除条目，因为它们是最近最少使用的条目。查找和逐出操作都将花费固定时间。

我可以考虑使用两个TreeMap在Haskell中实现此目标，并且我知道时间复杂度将为O（log n）。但是我有点不舒服，因为时间复杂度的恒定因素似乎有点高。具体来说，要执行查找，首先需要检查条目是否存在并保存其值，然后首先需要从LRU映射中删除它，然后使用新的密钥重新插入。这意味着每次查找将导致遍历根节点三遍。

在Haskell中有更好的方法吗？

Answer 1

如评论所示，可变载体在需要时是完全可以接受的。但是，我认为您提出问题的方式存在问题-除非想法是“尽可能紧密地”复制（没有可变结构）命令性代码，为什么要花2个树形图呢？单个优先级搜索队列（请参阅程序包pqueue或PSQueue）将是一个适当的结构，同时保持了纯度。它有效地支持优先级（用于逐出）和搜索（用于对所需的缓存参数进行查找）。

在相关说明中，某些结构支持例如。Data.Map的alterF，可以有效地为您提供延续，使您可以Maybe根据键的值“执行其他操作” ，但可以“记住”您所在的位置，从而避免支付全部费用来重新遍历结构以进行后续修改在这个关键。另见的at镜头。