不一致的Eq和Ord实例？ [英] Inconsistent Eq and Ord instances?

问题描述

我有一个很大的Haskell程序，运行速度非常慢。分析和测试表明，很大一部分时间花费在比较平等和特定大数据类型的排序上，而这些非常重要。平等是一种有用的操作（这是状态空间搜索，并且图搜索比树搜索更好），但我只需要此类的Ord实例即可使用地图。所以我想要做的是说

 实例Eq BigThing其中
（==）b b'=名称b ==名字b'&& 
 firstPart b == firstPart b'&& 
 secondPart b == secondPart b'&& 
 { -  ...等等...  - } 
 
实例Ord BigThing其中
比较b b'=比较（名称b）（名称b'）
  

但是由于名称对于不同的对象而言可能并不总是不同，所以这可能会导致两个BigThings可能会出现的奇怪情况不等于==，但比较它们会得到EQ。

这是否会导致Haskell库问题？有另外一种方法可以满足详细平等操作的要求，但价格便宜吗？首先，使用 Text 或 ByteString 而不是字符串可以帮助很多而不会改变其他任何东西。

通常我不建议创建 Eq 与 Ord 不一致的实例。图书馆可以正确地依赖它，而且你永远不会知道它会造成什么样的奇怪问题。 （例如，你肯定 Map 不使用 Eq 之间的关系。和 Ord ？）

---

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

 实例Eq BigThing其中
x == y =比较xy == EQ 
  

然后等号将与比较一致。如果你需要一个 Eq的话，那么就不需要相同的值必须等于所有的字段。



比较所有字段的实例，然后通过将 BigThing 包装成 newtype ，为它定义上面的 Eq 和 Ord ，并且当你需要根据 name ：

  newtype BigThing'abc = BigThing'（BigThing abc）
 instance Eq BigThing'where 
x == y = compare xy == EQ 
 instance Ord BigThing'where 
 compare（BigThing b）（BigThing b'）= compare（name b）（名称b'）
  

---

更新：既然你说任何排序都是可以接受的，你可以使用散列来获得优势。为此，您可以使用哈希包。这个想法是，您可以预先计算数据创建时的哈希值，并在比较值时使用它们。如果两个值不同，那么几乎可以确定它们的哈希值会有所不同，并且只比较它们的哈希值（两个整数），仅此而已。它可能看起来像这样：

  module BigThing 
（BigThing（）
，bigThing 
 ，btHash，btName，btSurname 
）
其中
 
导入Data.Hashable 
 
数据BigThing = BigThing {btHash :: Int，
 btName :: String，
 btSurname :: String}  -  etc 
导出（Eq，Ord）
  - 由于派生的Eq / Ord实例按字典顺序和
比较字段， btHash是第一个，它们会首先比较哈希值，并且只有在哈希值相等的情况下才会继续使用
  -  other字段。 
  - 请参阅http://www.haskell.org/onlinereport/derived.html#sect10.1 
  -  
  - 另外，您可以自己创建类似的Eq / Ord实例，如果对于任何
  - 原因，您不希望哈希成为第一个字段。 
 
  - 创建实例的智能构造函数。您的模块不会导出
  -  BigThing构造函数，它会导出此函数：
 bigThing :: String  - >字符串 - > BigThing 
 bigThing nm snm = BigThing（hash（nm，snm））nm snm 
  

注使用这种解决方案，排序看起来是随机的，与字段没有明显的关系。

您也可以将此解决方案与以前的解决方案结合使用。或者，您可以创建一个小模块，用它的预计算哈希包装任何类型（包装值必须包含 Eq 实例与它们的 Hashable
$ p $ module HashOrd
（Hashed（）
，getHashed
，hashedHash
）
其中

导入Data.Hashable

数据哈希值a =哈希值{hashedHash :: Int，getHashed :: a}
deriving（Ord，Eq，Show，Read，Bounded）

hashed ::（Hashable a）=> a - >散列a
散列x =散列（散列x）x

实例Hashable a => Hashable（Hashed a）其中
hashWithSalt salt（Hashed _ x）= hashWithSalt salt x





I have a large Haskell program which is running dismayingly slow. Profiling and testing has revealed that a large fraction of the time is spend comparing equality and ordering of a particular large datatype that is very important. Equality is a useful operation (this is state-space search, and graph search is much preferable to tree search), but I only need an Ord instance for this class in order to use Maps. So what I want to do is say

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')

But since the names may not always be different for different objects, this risks the curious case where two BigThings may be inequal according to ==, but comparing them yields EQ.

Is this going to cause problems with Haskell libraries? Is there another way I could satisfy the requirement for a detailed equality operation but a cheap ordering?

解决方案

First, using Text or ByteString instead of String could help a lot without changing anything else.

Generally I wouldn't recommend creating an instance of Eq inconsistent with Ord. Libraries can rightfully depend on it, and you never know what kind of strange problems it can cause. (For example, are you sure that Map doesn't use the relationship between Eq and Ord?)

---

If you don't need the Eq instance at all, you can simply define

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

Then equality will be consistent with comparison. There is no requirement that equal values must have all fields equal.

---

If you need an Eq instance that compares all fields, then you can stay consistent by wrapping BigThing into a newtype, define the above Eq and Ord for it, and use it in your algorithm whenever you need ordering according to 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: Since you say any ordering is acceptable, you can use hashing to your advantage. For this, you can use the hashable package. The idea is that you pre-compute hash values on data creation and use them when comparing values. If two values are different, it's almost sure that their hashes will differ and you the compare only their hashes (two integers), nothing more. It could look like this:

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

Note that with this solution, the ordering will be seemingly random with no apparent relation to the fields.

You can also combine this solution with the previous ones. Or, you can create a small module for wrapping any type with its precomputed hash (wrapped values must have Eq instances consistent with their Hashable instances).

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

这篇关于不一致的Eq和Ord实例？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！