Custom Ord instance hangs on lists

haskell, typeclass

Solution

Short answer: You need to provide either `(<=)` or `compare` to have a complete definition for `Ord`, not `(>=)`.

Longer explanation: It is common for type classes in Haskell to have default implementations of some methods implemented in terms of other methods. You can then choose which ones you want to implement. For example, `Eq` looks like this:

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

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

Here, you must either implement `(==)` or `(/=)`, otherwise trying to use either of them will cause an infinite loop. Which methods you need to provide is usually listed as the minimal complete definition in the documentation.

The minimal complete definition for `Ord` instances, as listed in the documentation, is either `(<=)` or `compare`. Since you've only provided `(>=)`, you have not provided a complete definition, and therefore some of the methods will loop. You can fix it by e.g. changing your instance to provide `compare` instead.

instance Ord Monomial where
  compare = compare `on` m_powers

Problem

``` 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 ``` That's an excerpt from my code, cut down to principal size. Let's try comparing: ``` *Main> (Monomial 1 [("x",2)]) > (Monomial (-1) []) /* Computation hangs here */ *Main> (Monomial 1 [("x",2)]) < (Monomial (-1) []) /* Computation hangs here */ ``` On a side note, it's interesting that if I replace `s/(>=)/(>)/g` in instance declaration, it will not hang on the fist pair, but still will on the second: ``` *Main> (Monomial 1 [("x",2)]) > (Monomial (-1) []) True *Main> (Monomial 1 [("x",2)]) < (Monomial (-1) []) /* Computation hangs here */ ``` Although the standard states minimal declaration of `Eq instance` to be either`$compare$` or `$(>=)$`. What might be the problem here? (>=) on lists seems to work just fine.

Original source