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在实例声明中替换，它不会挂在第一对上，但仍然会挂在第二对上：

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

Eq instance尽管标准规定了to be$compare$或的最小声明$(>=)$。

这里可能有什么问题？列表上的 (>=) 似乎工作得很好。

4

2 回答 2

10

简短的回答：
您需要提供(<=)或提供compare完整的定义Ord，而不是(>=)。

更长的解释：
Haskell 中的类型类通常会根据其他方法实现某些方法的默认实现。然后，您可以选择要实施的那些。例如，Eq看起来像这样：

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

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

在这里，您必须实现(==)or (/=)，否则尝试使用其中任何一个都会导致无限循环。您需要提供的方法通常在文档中列为最小完整定义。

文档中列出的Ord实例的最小完整定义是或。由于您只提供了，因此您还没有提供完整的定义，因此某些方法会循环。您可以通过例如更改您的实例来提供来修复它。(<=)compare(>=)compare

instance Ord Monomial where
  compare = compare `on` m_powers
于 2012-05-05T18:39:56.593 回答
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

所以，如果你只提供>=和==如上所述，那么你就有麻烦了，因为：

  • >定义为compare

但

  • compare定义为<=
  • <=定义为compare

所以你有一个无限循环！

最小定义必须定义<=or compare，而不是 '>=`。

于 2012-05-05T18:46:34.837 回答