3 
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補足として、インスタンス宣言で置き換えると、最初のペアではハングしないが、2 番目のペアではハングすることは興味深いことです。

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

Eq instance標準では、 が または のいずれか$compare$であるという最小限の宣言が述べられていますが$(>=)$。

ここで何が問題になる可能性がありますか？(>=) リストでは問題なく動作するようです。

4

2 に答える 2

6

のデフォルトのインスタンスを見てみましょう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

したがって、上記のように>=and==のみを指定すると、問題が発生します。

  • >の観点から定義されていますcompare

しかし

  • compareの観点から定義されています<=
  • <=の観点から定義されていますcompare

つまり、無限ループが発生します。

最小限の定義は、'>=` ではなく<=orを定義する必要があります。compare

于 2012-05-05T18:46:34.837 に答える