开发者

Is there any generic Hashable typeclass in Haskell? (a.k.a. "deriving (Hashable)")

Has anyone written a generic function so that hash functions can be generated automatically for custom data types (using the deriving mechanism)? A few times, I've written the following kind of boilerplate,

data LeafExpr = Var Name | Star deriving (Eq, Show)
in开发者_C百科stance Hashable LeafExpr where
    hash (Var name) = 476743 * hash name
    hash Star = 152857

This could be generated automatically: the basic idea is that whenever adding data, you multiply by a prime, for example with lists,

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

Essentially, what I'd like to write is

data LeafExpr = ... deriving (Hashable)

Edit 1

Thanks for all of the very helpful responses, everyone. I'll try to add a generic method as an exercise when I have time. For now (perhaps what sclv was referring to?), I realized I could write the slightly better code,

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

Edit 2

Using ghc, multiplying by random primes works much better than tupling in edit 1. Conflicts with Data.HashTable went from something like 95% (very bad) to 36%. Code is here: [ http://pastebin.com/WD0Xp0T1 ] [ http://pastebin.com/Nd6cBy6G ].


How much speed do you need? You could use one of the packages that use template haskell to generate serialization code to convert the value to binary and then hash the binary array with hashable.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜