在Haskell中没有更多状态monad版本的哈希映射/集合？

Question

散列集和映射的monadic接口是否在Haskell中消失了？在使用现代版本时,我应该考虑什么样的性能模型？(Data.Map,Data.HashMap,Data.HashSet).它们在我的版本中似乎没有任何IO代码(ghc 7.0.2),

> :browse Data.HashSet
type HashSet a = Set a
newtype Set a
  = Data.HashSet.Set (Data.IntMap.IntMap (Data.HashSet.Some a))
(\\) :: Ord a => Set a -> Set a -> Set a
delete :: (Data.Hashable.Hashable a, Ord a) => a -> Set a -> Set a
difference :: Ord a => Set a -> Set a -> Set a
elems :: Set a -> [a]
empty :: Set a
Data.HashSet.filter :: Ord a => (a -> Bool) -> Set a -> Set a
fold :: (a -> b -> b) -> b -> Set a -> b
fromList :: (Data.Hashable.Hashable a, Ord a) => [a] -> Set a
insert :: (Data.Hashable.Hashable a, Ord a) => a -> Set a -> Set a
intersection :: Ord a => Set a -> Set a -> Set a
isProperSubsetOf :: Ord a => Set a -> Set a -> Bool
isSubsetOf :: Ord a => Set a -> Set a -> Bool
Data.HashSet.map ::
  (Data.Hashable.Hashable b, Ord b) => (a -> b) -> Set a -> Set b
member :: (Data.Hashable.Hashable a, Ord a) => a -> Set a -> Bool
notMember ::
  (Data.Hashable.Hashable a, Ord a) => a -> Set a -> Bool
Data.HashSet.null :: Set a -> Bool
partition :: Ord a => (a -> Bool) -> Set a -> (Set a, Set a)
singleton :: Data.Hashable.Hashable a => a -> Set a
size :: Set a -> Int
toList :: Set a -> [a]
union :: Ord a => Set a -> Set a -> Set a
unions :: Ord a => [Set a] -> Set a

Answer 1

Data.HashMap和Data.HashSet使用Patricia树来存储哈希值,因此操作的性能与Data.Map具有相同的渐近复杂度.但话虽如此,常数因素要小得多,而且我的经验表现得相当快.

Answer 2

散列集和映射的monadic接口是否在Haskell中消失了？

不,还有一个monadic哈希映射Data.HashTable,它存在于IOmonad中.(它非常令人讨厌,因为它不会存在于STmonad中,但这会使它稍微不那么便携,而且我认为它不太容易理解,因为ST它不是Haskell 98.)它的工作方式非常类似于任何命令式语言的哈希表.性能特征也应该相同.

当然,从任何地图(包括哈希表)中,您都可以通过存储虚拟值来创建一个集合(例如,只需将每个键映射到自身).