Inkonsistente Eq- und Ord-Instanzen?

Question

Ich habe ein großes Haskell-Programm, das erschreckend langsam läuft. Profiling und Tests haben ergeben, dass ein großer Teil der Zeit damit verbracht wird, die Gleichheit und Ordnung eines bestimmten großen Datentyps zu vergleichen, was sehr wichtig ist. Gleichheit ist eine nützliche Operation (das ist die Suche nach einem Zustandsraum, und die Diagrammsuche ist der Baumsuche viel vorzuziehen), aber ich brauche nur eine Ord-Instanz für diese Klasse, um Maps zu verwenden. Also, was ich will tun, sagen

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

Aber da die Namen für verschiedene Objekte können nicht immer anders sein, riskiert dies den merkwürdigen Fall, wo zwei BigThings inequal sein kann, nach ==, aber vergleichen sie ergibt EQ.

Wird dies Probleme mit Haskell-Bibliotheken verursachen? Gibt es eine andere Möglichkeit, die Anforderung für eine detaillierte Gleichstellungsoperation zu erfüllen, aber eine billige Bestellung?

Answer 1

Zuerst mit Text oder ByteString statt Stringviel ohne etwas anderes ändern helfen könnte.

Im Allgemeinen würde ich nicht empfehlen, eine Instanz von Eq zu erstellen, die mit Ord inkonsistent ist. Bibliotheken können sich zu Recht darauf verlassen, und Sie wissen nie, welche Art von seltsamen Problemen es verursachen kann. (Zum Beispiel sind Sie sicher dass Map nicht die Beziehung nicht verwendet zwischen Eq und Ord?)

---

Wenn Sie die Eq Instanz nicht brauchen überhaupt, können Sie einfach definieren

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

Dann wird die Gleichheit mit dem Vergleich übereinstimmen. Es ist nicht erforderlich, dass bei gleichen Werten alle Felder gleich sind.

---

Wenn Sie eine Eq Instanz benötigen, der alle Felder vergleicht, dann können Sie konsistent bleiben, indem sie BigThing in eine newtype, definieren die oben Eq und Ord dafür Einwickeln und es in Ihrem Algorithmus verwenden, wann immer Sie benötigen Bestellung nach zu 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: Da sagen Sie jede Bestellung akzeptabel ist, ca Sie Nutzen Sie Hashing zu Ihrem Vorteil. Dazu können Sie das Paket hashable verwenden. Die Idee ist, dass Sie Hashwerte bei der Datenerstellung vorberechnen und beim Vergleichen von Werten verwenden. Wenn zwei Werte unterschiedlich sind, ist es fast sicher, dass ihre Hashes sich unterscheiden und Sie nur ihre Hashes (zwei ganze Zahlen) vergleichen, nichts mehr. Es könnte wie folgt aussehen:

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 

Beachten Sie, dass mit dieser Lösung wird die Bestellung auf die Felder ohne erkennbare Beziehung scheinbar zufällig sein.

Sie können diese Lösung auch mit den vorherigen kombinieren. Oder Sie können ein kleines Modul zum Umbrechen eines beliebigen Typs mit seinem vorberechneten Hash erstellen (umbrochene Werte müssen Eq Instanzen haben, die mit ihren Hashable Instanzen konsistent sind).

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