Haskell 中有通用的 Hashable 类型类吗？（又名“派生（可哈希）”）

发布于 2024-11-08 18:19:28 字数 997 浏览 5 评论 0原文

有没有人编写了一个通用函数，以便可以为自定义数据类型自动生成哈希函数（使用派生机制）？有几次，我编写了以下类型的样板，

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"

使用 ghc编辑 2

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

原文

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

分享到QQ

分享到微博