Блог

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

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

#haskell #hash #state-monad

#haskell #хэш #состояние-монада

Вопрос:

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

Ответ №1:

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

Ответ №2:

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

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

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

Комментарии:

1. Придирка ко всему обсуждению: называть это «монадической хэш-картой» довольно вводит в заблуждение, и я был смущен этим. Я ожидал MonadHashTable класс или что-то в этомроде. Я бы назвал это «нечистой хэш-таблицей» или даже «хэш-таблицей с операциями в IO «. Слово «монада» на самом деле здесь неуместно.

2. Я не понимаю, почему. Что плохого в вызове чего-то «монадического», если есть куча функций, которые возвращают значения в монаде?

3. Я думаю, что для вызова чего-либо «монадического» эти функции должны возвращать результаты в произвольной монаде или, по крайней мере, любой монаде в классе данного типа. Если они возвращают только значения в IO , хорошо… IO является функтором и конструктором типа, а также монадой; почему бы не назвать это «функториальным» или «конструкторским типом»?

4. @Alexey Я только что погуглил monadic. Использование термина «монадический синтаксический анализ», в том числе в хорошо цитируемой статье Хаттона, не соответствует вашему ограниченному определению слова.

5. Вы бы вызывали функции, которые возвращают списки монадическими? Если функции, возвращающие ввод-вывод, называются монадическими, то функции, возвращающие списки, также должны быть.

Ответ №3:

По-прежнему доступна хэш-таблица, живущая в IO. Однако эта версия устарела (именно потому, что она не используется в ST-монаде) и будет удалена в GHC 7.8.

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