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

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.

于 2011-05-23T09:38:15.487 に答える