haskell - 是否存在有用的 Haskell HashMap/HashTable/Dictionary 库？

Question

我正在寻找一个无 monad、常量访问查询 O(1) 关联数组。

考虑假设类型:

data HT k v = ???

我想构建一个不可变的结构一次:

fromList :: Foldable t, Hashable k => t (k,v) -> HT k v

我想随后以恒定时间访问重复查询它::

lookup :: Hashable k => HT k v -> k -> Maybe v

似乎有两个候选库不足:

unordered-containers

hashtables

unordered-containersunordered-containers包含 HashMap 类型的严格变体和惰性变体.两个HashMap s 有 O(log n) 个查询，如 lookup 所述功能。此查询访问时间似乎是由于 HashMap 的构造造成的。类型，具有允许 O(log n) insert 的内部树结构功能。对于许多用例来说，这是一个可以理解的设计权衡，但因为我不需要可变的 HashMap这种权衡阻碍了我的用例。
hashtableshashtables包含 HashTable类型类和三种具有不同表构造策略的实例类型。这个库的类型类定义了一个常数时间 O(1) lookup 函数定义，但它永远嵌入到 ST单子(monad)。没有办法“卡住”有状态的 HashTable实现并具有 lookup没有嵌入有状态单子(monad)的函数。当整个计算包装在一个状态单子(monad)中时，库的类型类接口(interface)设计得很好，但是这种设计不适合我的用例。

是否存在其他一些定义类型和函数的库，这些库可以构造不可变的常量访问查询 O(1) 关联数组，该数组未嵌入有状态的单子(monad)中？

是否存在某种方法来包装或修改这些现有的基于散列的库以生成未嵌入有状态 monad 的不可变常量访问查询 O(1) 关联数组？

Answer 1

你想要的图书馆是……unordered-containers .或者只是普通的旧Data.Map来自 containers ，如果你愿意的话。

unordered-containers documentation 中的注释解释了为什么您不应该担心查找的 O(log n) 时间复杂度:

Many operations have a average-case complexity of O(log n). The implementation uses a large base (i.e. 16) so in practice these operations are constant time.

这是某些功能数据结构的常见做法，因为它允许良好的共享属性，同时也具有良好的时间复杂性。即使对于非常大的 n，log16 仍然会产生非常小的数字，因此您几乎总是可以将这些复杂性视为“有效的恒定时间”。

如果这曾经是您的应用程序的瓶颈，当然，请使用其他方法，但我发现这不太可能。毕竟，log16(1,000,000) 略低于 5，因此您的查找时间不会很快增长。处理所有这些数据将占用比查找开销更多的时间。

一如既往:简介第一。如果你有一个绝对需要世界上最快的哈希映射的问题，你可能需要一个命令式哈希映射，但对于我曾经遇到的每一种情况，功能性的都可以正常工作。