Niespójne wystąpienia Eq i Ord?

Question

Mam duży program Haskell, który działa nieprzerwanie wolno. Profilowanie i testowanie wykazały, że znaczna część czasu poświęcana jest na porównywanie równości i porządkowania określonego dużego typu danych, co jest bardzo ważne. Równość jest użyteczną operacją (jest to wyszukiwanie w przestrzeni stanów, a wyszukiwanie wykresów jest dużo lepszym rozwiązaniem niż wyszukiwanie w drzewie), ale do korzystania z Map potrzebuję tylko instancji klasy Ord dla tej klasy. Więc to, co chcę zrobić, to powiedzieć

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

Ale od nazw nie zawsze może być różny dla różnych obiektów, to ryzykuje Ciekawy przypadek gdzie dwie BigThings może być inequal według ==, ale porównując je daje EQ.

Czy spowoduje to problemy z bibliotekami Haskell? Czy istnieje inny sposób, w jaki mogę spełnić wymóg szczegółowej operacji równości, ale tanie zamówienie?

Answer 1

pierwsze, stosując Text lub ByteString zamiast String może pomóc dużo bez zmieniania czegokolwiek innego.

Ogólnie nie polecam tworzenia instancji Eq niezgodnej z Ord. Biblioteki mogą na tym polegać i nigdy nie wiadomo, jakie dziwne problemy mogą powodować. (Na przykład, jesteś pewien że Map nie wykorzystuje zależność pomiędzy Eq i Ord?)

---

Jeśli nie potrzebują instancję Eq w ogóle, można po prostu określić

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

Wtedy równość będzie zgodna z porównaniem. Nie ma wymogu, aby równe wartości miały wszystkie pola równe.

---

Jeśli potrzebujesz instancję Eq który porównuje wszystkie pola, a następnie można pozostać spójne owijając BigThing do newtype, definiować powyższy Eq i Ord dla niego i używać go w swoim algorytmie gdy trzeba zamawiania według do 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') 

---

Aktualizacja: Skoro mówisz, każdy zamawiający jest dopuszczalne, to ok n używać hashing na swoją korzyść. W tym celu można użyć pakietu hashable. Pomysł polega na wstępnym obliczeniu wartości mieszania podczas tworzenia danych i wykorzystaniu ich podczas porównywania wartości. Jeśli dwie wartości są różne, to prawie pewne, że ich skróty będą się różnić i porównasz tylko ich skróty (dwie liczby całkowite), nic więcej. To może wyglądać następująco:

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 

Należy zauważyć, że z tego rozwiązania, Zamawiający będzie pozornie przypadkowy bez widocznego związku z pól.

Można również połączyć to rozwiązanie z poprzednimi. Można też utworzyć mały moduł do zawijania dowolnego typu za pomocą jego wstępnie obliczonego skrótu (wartości opakowane muszą mieć instancje Eq zgodne z ich instancjami 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