自定义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的完整定义，而不是(>=)。

更长的解释：

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定义的

所以你有一个无限循环！

最低定义必须定义为<=或compare，而不是'>=`。