Пользовательский экземпляр Ord зависает по спискам

Question

import Data.Function (on) 
import Data.List (sort) 

data Monomial = Monomial 
    { m_coeff :: Coefficient 
    , m_powers :: [(Variable, Power)] 
    } 
    deriving() 

instance Ord Monomial where 
    (>=) = on (>=) m_powers 

instance Eq Monomial where 
    (==) = on (==) m_powers 

Это выдержка из моего кода, сокращенного до основного размера. Давайте попробуем сравнения:

*Main> (Monomial 1 [("x",2)]) > (Monomial (-1) []) 
/* Computation hangs here */ 
*Main> (Monomial 1 [("x",2)]) < (Monomial (-1) []) 
/* Computation hangs here */ 

На стороне записки, это интересно, что если я заменю s/(>=)/(>)/g в объявлении экземпляра, он не будет висеть на паре кулак, но по-прежнему будет на второй:

*Main> (Monomial 1 [("x",2)]) > (Monomial (-1) []) 
True 
*Main> (Monomial 1 [("x",2)]) < (Monomial (-1) []) 
/* Computation hangs here */ 

Хотя в стандарте указано минимальное объявление Eq instance либо $compare$, либо $(>=)$.

В чем может быть проблема? (> =) по спискам, похоже, работает нормально.

Answer 1

Короткий ответ:
Вы должны предоставить либо (<=) или compare иметь полное определение для Ord, не (>=).

Longer объяснение:
Это характерно для классов типов в Haskell, чтобы иметь реализацию по умолчанию некоторых методов, реализованных в терминах других методов. Затем вы можете выбрать, какие из них вы хотите реализовать. Например, Eq выглядит следующим образом:

class Eq a where 
    (==), (/=) :: a -> a -> Bool 

    x /= y = not (x == y) 
    x == y = not (x /= y) 

Здесь вы должны либо реализовать (==) или (/=), иначе пытаются использовать любой из них может привести к бесконечному циклу. Какие методы вам необходимо предоставить, как правило, перечислены как минимальное полное определение в документации.

Минимальное полное определение для Ord экземпляров, as listed in the documentation, либо (<=), либо compare. Поскольку вы предоставили только (>=), вы не указали полное определение, и поэтому некоторые из методов будут циклическими. Вы можете исправить это, например. изменив ваш экземпляр, чтобы вместо этого указать compare.

instance Ord Monomial where 
    compare = compare `on` m_powers 

Answer 2

Давайте посмотрим, например, по умолчанию для Ord:

class (Eq a) => Ord a where 
    compare    :: a -> a -> Ordering 
    (<), (<=), (>), (>=) :: a -> a -> Bool 
    max, min    :: a -> a -> a 

    compare x y = if x == y then EQ 
        -- NB: must be '<=' not '<' to validate the 
        -- above claim about the minimal things that 
        -- can be defined for an instance of Ord: 
        else if x <= y then LT 
        else GT 

    x < y = case compare x y of { LT -> True; _ -> False } 
    x <= y = case compare x y of { GT -> False; _ -> True } 
    x > y = case compare x y of { GT -> True; _ -> False } 
    x >= y = case compare x y of { LT -> False; _ -> True } 

     -- These two default methods use '<=' rather than 'compare' 
     -- because the latter is often more expensive 
    max x y = if x <= y then y else x 
    min x y = if x <= y then x else y 

Так что, если вы поставляете >= и ==, как указано выше, только тогда вы в беде, так как:

• > определяется в терминах compare

Но

• compare определяется в терминах <=
• <= определяется в терминах compare

Таким образом, у вас есть бесконечный цикл!

Минимальное определение должно быть определено <= или compare, а не '> = `.