6

有没有人写过一个通用函数，以便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"

编辑 2

使用 ghc，乘以随机素数比编辑 1 中的元组效果好得多。与 Data.HashTable 的冲突从 95%（非常糟糕）到 36%。代码在这里：[ http://pastebin.com/WD0Xp0T1 ] [ http://pastebin.com/Nd6cBy6G ]。

4

1 回答 1

2

你需要多少速度？您可以使用使用模板 haskell 的包之一生成序列化代码以将值转换为二进制，然后使用hashable 散列二进制数组。

于 2011-05-23T09:38:15.487 回答