Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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)
instance 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 ].

like image 598
gatoatigrado Avatar asked May 23 '11 08:05

gatoatigrado


1 Answers

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.

like image 181
Chris Kuklewicz Avatar answered Oct 09 '22 11:10

Chris Kuklewicz