是否存在一个有用的Haskell HashMap/HashTable/Dictionary库？

Question

是否存在一个有用的Haskell HashMap/HashTable/Dictionary库？

haskellhashmaphashtableasymptotic-complexityhackage

15

我希望您能够提供一个不依赖于单子的、具有常数访问时间复杂度 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`

unordered-containers 包含严格和惰性两种类型的 HashMap。这两种 HashMap 都有一个 O(log n) 的查询，正如 lookup 函数所记录的那样。这个查询访问时间似乎是由于 HashMap 类型的构造引起的，它们具有内部树结构，可以实现 O(log n) 的 insert 功能。对于许多用例来说，这是一种可以理解的设计权衡，但由于我不需要可变的 HashMap，因此这种权衡妨碍了我的用例。

`hashtables`

hashtables包含一个HashTable类型类和三个具有不同表构建策略的实例类型。该库的类型类定义了一个常量时间O(1)lookup函数，但它永久嵌入在ST单子中。无法“冻结”有状态的HashTable实现，并且没有办法使lookup函数不嵌入状态单子。当整个计算都被包装在状态单子中时，该库的类型类接口设计得很好，但是这种设计对我的用例不适用。

存在其他库可以定义类型和函数，用于构建不嵌入有状态单子中的不可变常量访问查询O(1)关联数组吗？

存在一些方法可以包装或修改这些现有基于哈希的库，以生成不嵌入有状态单子中的不可变常量访问查询O(1)关联数组吗？

- recursion.ninja

首先：我认为你是正确的。没有纯+O(1)查找键值结构。另一方面，首先出现的问题是必要性问题。避免单子（包括避免使用IO）有点审美选择，通常缺乏技术上的理由-在这种情况下，避免会带来明显的代价。同样，对过早优化的怀疑已经被提出。如果您愿意，请考虑向“hashtables”库添加一个冻结操作和纯查找的补丁。或者尝试使用HashMap并查看性能是否具体。 - Thomas M. DuBuisson

@ThomasM.DuBuisson 我使用了一个 (i,j) 键的矩阵来进行 O(1) 查询，但是矩阵的维度增长得太快了，而且矩阵是一个稀疏的上三角矩阵。内存需求不可扩展。当我找不到合适的哈希表结构来替换查找矩阵时，我感到非常震惊。有一个功能请求来冻结 HashTable，但它没有得到回答，我现在也无法构建一个拉取请求。 - recursion.ninja

3个回答

11

你应该按照Alexis的建议使用unordered-containers。如果你真的想要保证具有Θ(1)lookup的内容，你可以使用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