是否存在有用的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-containers

unordered-containers包含类型的严格和惰性变体HashMap.两者HashMap都有函数记录的O(log n)查询lookup.此查询访问时间似乎是由于HashMap类型的构造,其具有允许O(log n) insert功能的内部树结构.对于许多用例而言,可理解的设计权衡,但由于我不需要可变,HashMap这种权衡妨碍了我的用例.

hashtables

hashtables包含一个HashTable类型类和三个具有不同表构造策略的实例类型.这个库的类型类定义了一个常量时间O(1) lookup函数定义,但它永远嵌入在STmonad中.没有办法"冻结"有状态HashTable实现lookup,并且没有嵌入有状态monad 的函数.当整个计算以状态monad包装时,库的类型类接口设计得很好,但这种设计不适合我的用例.

---

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

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

Answer 1

你想要的库是... unordered-containers.或者只是普通的旧Data.Map的containers,如果你愿意.

中记unordered-containers文档解释了为什么你不应该担心Ø(日志ñ)时间查找的复杂性:

许多操作的平均情况复杂度为O(log n).实现使用大的基数(即16),因此在实践中这些操作是恒定的时间.

这是某些类型的功能数据结构的常见做法,因为它允许良好的共享属性,同时还具有良好的时间复杂性.即使对于非常大的n,log ₁₆仍然会产生非常小的数字,因此您几乎总能将这些复杂性视为"有效的恒定时间".

如果这对您的应用程序来说是一个瓶颈,请务必使用其他内容,但我发现这种可能性极小.毕竟,log ₁₆(1,000,000)略低于5,因此您的查找时间不会很快增长.处理所有数据将比查找的开销花费更多的时间.

一如既往:简介第一.如果你以某种方式遇到一个绝对需要世界上最快的哈希映射的问题,你可能需要一个命令式哈希映射,但是对于我曾经遇到的每一个案例,功能都可以正常工作.

Answer 2

您应该遵循Alexis的建议并使用unordered-containers.如果你真的想要的东西,都保证有?(1) lookupS,你可以定义任何从哈希表类型的自己的冻结版本hashtables使用unsafePerformIO,但是这是不是很优雅.例如:

module HT
    ( HT
    , fromList
    , lookup
    ) where

import qualified Data.HashTable.IO as H
import Data.Hashable (Hashable)
import Data.Foldable (toList)
import System.IO.Unsafe (unsafePerformIO)
import Prelude hiding (lookup)

newtype HT k v = HT (H.BasicHashTable k v)

fromList :: (Foldable t, Eq k, Hashable k) => t (k, v) -> HT k v
fromList = HT . unsafePerformIO . H.fromList . toList

lookup :: (Eq k, Hashable k) => HT k v -> k -> Maybe v
lookup (HT h) k = unsafePerformIO $ H.lookup h k

unsafePerformIO上述两种用途都应该是安全的.因此,将HT其导出为抽象类型至关重要.