Есть ли в Haskell универсальный класс типов Hashable? (a.k.a. "получение (Hashable)") - PullRequest
Новая
       41

Есть ли в Haskell универсальный класс типов Hashable? (a.k.a. "получение (Hashable)")

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

Кто-нибудь написал обобщенную функцию, чтобы функции hash могли генерироваться автоматически для пользовательских типов данных (используя механизм deriving)?Несколько раз я писал следующий пример: 

data LeafExpr = Var Name | Star deriving (Eq, Show)
instance Hashable LeafExpr where
    hash (Var name) = 476743 * hash name
    hash Star = 152857

Это может быть сгенерировано автоматически: основная идея заключается в том, что при добавлении данных вы умножаете на простое число, например, со списками, 

hash (x:xs) = hash x + 193847 * hash xs

По сути, я хотел бы написать: 

data LeafExpr = ... deriving (Hashable)

Редактировать 1

Спасибо всем за очень полезные ответы, всем.Я постараюсь добавить общий метод в качестве упражнения, когда у меня будет время.Пока (возможно, что имел в виду sclv?), Я понял, что могу написать немного лучший код: 

instance Hashable LeafExpr where
    hash (Var name) = hash ("Leaf-Var", name)
    hash Star = hash "Leaf-Star"

Edit 2

Используя ghc, умножение на случайные простые числа работаетнамного лучше, чем кортеж в редактировании 1 .Конфликты с Data.HashTable сократились с 95% (очень плохо) до 36%.Код здесь: [http://pastebin.com/WD0Xp0T1] [http://pastebin.com/Nd6cBy6G].

1 Ответ

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

Сколько вам нужно скорости? Вы можете использовать один из пакетов, которые используют шаблон haskell для генерации кода serialization для преобразования значения в двоичный файл, а затем хешировать двоичный массив с помощью hashable .

...