一貫性のないEqインスタンスとOrdインスタンス？

Question

私はすごく遅く走っている大きなHaskellプログラムを持っています。プロファイリングとテストでは、時間の大部分が非常に重要な特定の大きなデータ型の等価性と順序性を比較するのに費やされていることが明らかになりました。等価は便利な操作です（これは状態空間検索であり、グラフ検索はツリー検索よりもはるかに好ましい）が、マップを使用するにはこのクラスのOrdインスタンスが必要です。だから、私は何をしたい

instance Eq BigThing where 
(==) b b' = name b == name b' && 
      firstPart b == firstPart b' && 
      secondPart b == secondPart b' && 
      {- ...and so on... -} 

instance Ord BigThing where 
compare b b' = compare (name b) (name b') 

を言っているが、名前は常に異なるオブジェクトに対して異なることはないかもしれないので、これは2 BigThingsは==に応じて不等かもしれ好奇心ケースをリスク、それらを比較することはEQを生成します。

これはHaskellライブラリで問題を引き起こすでしょうか？詳細な等価操作の要件を満たすことができる別の方法がありますが、安価な注文ですか？

Answer 1

まず、代わりにStringのTextやByteStringを使用すると、他に何も変更せずにたくさんを助けることができます。

一般にOrdと一致しないEqのインスタンスを作成することはお勧めしません。図書館は正当にそれに依存することができ、どんな奇妙な問題が起こるかは決して分かりません。 （たとえば、MapがEqとOrdとの間の関係を使用していないことを確認ある？）

---

あなたがすべてでEqインスタンスを必要としない場合、あなたは、単に

instance Eq BigThing where 
    x == y = compare x y == EQ 

を定義することができます

次に、同等性は比較と一致します。等しい値にはすべてのフィールドが等しくなければならないという要件はありません。

---

あなたはすべてのフィールドを比較しEqインスタンスが必要な場合は、その後、あなたはそれのために上記EqとOrdを定義し、newtypeにBigThingをラッピングすることにより、一貫した滞在し、あなたが必要な時はいつでもあなたのアルゴリズムで注文に従ってそれを使用することができますnameへ：

newtype BigThing' a b c = BigThing' (BigThing a b c) 
instance Eq BigThing' where 
    x == y = compare x y == EQ 
instance Ord BigThing' where 
    compare (BigThing b) (BigThing b') = compare (name b) (name b') 

---

更新：あなたが任意の順序が受け入れ可能であると言うので、あなたがCA nあなたの利点にハッシュを使用します。このため、hashableパッケージを使用できます。データの作成時にハッシュ値を事前計算し、値を比較するときにハッシュ値を使用するという考え方です。 2つの値が異なる場合は、ハッシュが異なることがほとんどで、ハッシュ（2つの整数）のみを比較します。

module BigThing 
    (BigThing() 
    , bigThing 
    , btHash, btName, btSurname 
    ) 
where 

import Data.Hashable 

data BigThing = BigThing { btHash :: Int, 
          btName :: String, 
          btSurname :: String } -- etc 
    deriving (Eq, Ord) 
-- Since the derived Eq/Ord instances compare fields lexicographically and 
-- btHash is the first, they'll compare the hash first and continue with the 
-- other fields only if the hashes are equal. 
-- See http://www.haskell.org/onlinereport/derived.html#sect10.1 
-- 
-- Alternativelly, you can create similar Eq/Ord instances yourself, if for any 
-- reason you don't want the hash to be the first field. 

-- A smart constructor for creating instances. Your module will not export the 
-- BigThing constructor, it will export this function instead: 
bigThing :: String -> String -> BigThing 
bigThing nm snm = BigThing (hash (nm, snm)) nm snm 

この解決策では、順序は見た目とは無関係で、フィールドとは明らかに関係がないことに注意してください。

このソリューションを以前のソリューションと組み合わせることもできます。または、事前計算されたハッシュで任意の型をラップするための小さなモジュールを作成することができます（ラップされた値は、Hashableインスタンスと一致するEqインスタンスを持つ必要があります）。

module HashOrd 
    (Hashed() 
    , getHashed 
    , hashedHash 
    ) 
where 

import Data.Hashable 

data Hashed a = Hashed { hashedHash :: Int, getHashed :: a } 
    deriving (Ord, Eq, Show, Read, Bounded) 

hashed :: (Hashable a) => a -> Hashed a 
hashed x = Hashed (hash x) x 

instance Hashable a => Hashable (Hashed a) where 
    hashWithSalt salt (Hashed _ x) = hashWithSalt salt x