Несовместимые экземпляры Eq и Ord?

Question

У меня есть большая программа на Haskell, которая работает очень медленно. Профилирование и тестирование показали, что большая часть времени тратится на сравнение равенства и упорядочения определенного большого типа данных, что очень важно. Равенство - это полезная операция (это поиск в пространстве состояний, а поиск в графике гораздо предпочтительнее поиска в дереве), но мне нужен только экземпляр Ord для этого класса, чтобы использовать Maps. Итак, что я хочу сделать, это сказать

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 может помочь, не меняя ничего другого.

Как правило, я бы не рекомендовал создавать экземпляр Eq несовместимо с Ord, Библиотеки могут по праву зависеть от этого, и вы никогда не знаете, какие странные проблемы это может вызвать. (Например, вы уверены, что 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')

---

Обновление: так как вы говорите, что любой заказ приемлем, вы можете использовать хеширование в ваших интересах. Для этого вы можете использовать хэш- пакет. Идея состоит в том, что вы предварительно вычисляете хеш-значения при создании данных и используете их при сравнении значений. Если два значения различны, почти наверняка их хеш-коды будут отличаться, и вы сравните только их хеши (два целых числа), и не более того. Это может выглядеть так:

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

Обратите внимание, что при таком решении порядок будет казаться случайным без видимой связи с полями.

Вы также можете комбинировать это решение с предыдущими. Или вы можете создать небольшой модуль для переноса любого типа с его предварительно вычисленным хешем (обернутые значения должны иметь Eq случаи соответствуют их Hashable экземпляры).

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