Больше нет версии монады состояний хэш-карт / наборов в Haskell? - PullRequest
Новая
       12

Больше нет версии монады состояний хэш-карт / наборов в Haskell?

1 голос
/ 23 мая 2011

В Haskell отсутствует монадический интерфейс для хэш-наборов и карт?Какую модель производительности следует иметь в виду при использовании современных версий?(Data.Map, Data.HashMap, Data.HashSet).У них, похоже, нет кода ввода-вывода в версии, которую я имею (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

Ответы [ 3 ]

7 голосов
/ 23 мая 2011

Data.HashMap и Data.HashSet используют деревья Патриции для хранения хэша, поэтому производительность операций имеет ту же асимптотическую сложность, что и Data.Map. Но, тем не менее, постоянный фактор намного меньше, и, по моему опыту, они работают намного быстрее.

5 голосов
/ 23 мая 2011

В Haskell отсутствует монадический интерфейс для хэш-наборов и карт?

Нет, все еще есть монадическая хэш-карта, Data.HashTable , которая живет в монаде IO. (Довольно досадно, что он не живет в монаде ST, но это сделает его немного менее портативным и немного менее понятным, я полагаю, потому что ST - это не Haskell 98.) Hashtable на любом императивном языке. Рабочие характеристики должны быть такими же.

И, конечно, из любой карты, включая хеш-таблицу, вы можете создать набор, сохраняя фиктивные значения (например, просто сопоставьте каждый ключ себе).

0 голосов
/ 01 февраля 2013

Есть еще HashTable, живущий в IO , доступный. Тем не менее, этот объект устарел (именно потому, что он не живет в монаде ST) и будет удален в GHC 7.8.

Тем не менее, существует монадическая хеш-таблица, которая равна , живущей в ST. Смотрите пакет hashtables в hackageDB.

...