No more state monad version of hash maps / sets in Haskell?

Is the monadic interface to hash sets and maps gone in Haskell? What kind of performance model should I have in mind when using the modern versions? (Data.Map, Data.HashMap, Data.HashSet). They do not appear to have any IO code in the version I have (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

---

Data.HashMap and Data.HashSet use Patricia trees to store the hash, so the performance for the operations have the same asymptotic complexity as Data.Map. But that said, the constant factor is much smaller and they perform quite a lot faster in my experience.

---

Is the monadic interface to hash sets and maps gone in Haskell?

No, there's still a monadic hash map, Data.HashTable, which lives in the IO monad. (It's pretty annoying that it doesn't live in the ST monad, but that would make it slightly less portable and slightly less easy to understand I suppose, because ST isn't Haskell 98.) It works pretty much like a hashtable in any imperative language. The performance characteristics should be the same as well.

And of course from any map, including a hashtable, you can create a set, by storing dummy values (e.g. just map every key to itself).

---

There is still a HashTable, living in IO, available. However, that one is deprecated (precisely because it is not living in the ST monad) and will be removed in GHC 7.8.

Yet there is a monadic hashtable available, which is living in ST. See the hashtables package in the hackageDB.