不一致的Eq和Ord实例

Question

我有一个运行速度慢得令人沮丧的大型Haskell程序。概要分析和测试表明，比较特定大型数据类型的相等性和排序需要花费大量时间，这一点非常重要。相等是一个有用的操作(这是状态空间搜索，图搜索比树搜索更可取)，但是为了使用Maps，我只需要这个类的一个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')

但是，由于不同对象的名称可能并不总是不同的，这就有可能出现奇怪的情况:根据==，两个BigThings可能不相等，但比较它们会产生EQ。

这会导致Haskell库出现问题吗?有没有另一种方法，我可以满足一个详细的相等操作的要求，但便宜的排序?

Answer 1

首先，使用Text或ByteString代替String可以在不改变任何其他内容的情况下对有很大帮助。

一般来说，我不建议创建与Ord不一致的Eq实例。库可以正确地依赖于它，而且您永远不知道它会导致什么样的奇怪问题。(例如，你确定 Map不使用Eq和Ord之间的关系吗?)

---

如果根本不需要Eq实例，可以简单地定义

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

则相等与比较一致。没有要求相等的值必须使所有字段相等。

---

如果你需要一个Eq实例来比较所有字段，那么你可以通过将BigThing包装成newtype来保持一致，为它定义上面的Eq和Ord，并在你需要根据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')

---

Update:既然您说任何排序都是可以接受的，那么您可以使用散列。为此，您可以使用哈希包。其思想是在数据创建时预先计算哈希值，并在比较值时使用它们。如果两个值不同，几乎可以肯定它们的哈希值不同，您只需比较它们的哈希值(两个整数)，仅此而已。它可以像这样:

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