Geek asks and answers

Custom Ord Instance Hangs on Lists

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

This is an excerpt from my code, reduced to the main size. Try to compare:

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

On the side of the note, it’s interesting that if I replaced the s/(>=)/(>)/ginstance in the declaration, it will not hang on the first pair, but it will still be on the second:

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

Although the standard state, the minimum declaration Eq instanceshould be either $compare$or $(>=)$.

What could be the problem? (> =) on lists seems to work fine.

+3
source share
2 answers

Short answer:
You must specify (<=)or comparein order to have a full definition for Ord, rather than (>=).

:
Haskell , . , . , Eq :

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

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

(==), (/=), . , , .

Ord , (<=) compare. (>=), , . , . , compare.

instance Ord Monomial where
  compare = compare `on` m_powers
+9

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, ' >= `.

+6

More articles:


All Articles