Ord 实例比较树高度冻结与 >= 或 >

Question

无法比较符号大于 (>) 和大于或等于 (>=) 的树的高度。这是我的代码。它只是冻结在命令 tree1 >= tree2:

data Tree a = Node a [Tree a] deriving (Eq,Show)
instance (Ord a) => Ord (Tree a) where
    Node a list1 >= Node b list2 = (list1 > list2) || (list1 == list2)
    (Node a list1) > (Node b list2) = (list1 > list2)

t0 = Node 15 []
t1 = Node 15 []
t2 = Node 120 [t0]
tree1 = Node 130 [t1,t2]

tt0 = Node 155 []
tt1 = Node 112 [t2]
tt2 = Node 128 [t0]
tree2 = Node 110 [tt1,tt2,tt0]

Answer 1

TL;DR: 定义 <=.

启用警告，它会说：

No explicit implementation for either ‘compare’ or ‘<=’

In the instance declaration for ‘Ord (Tree a)’

对于 Ord，您必须至少实现其中之一：<= 或 compare。

这是由于 Ord 这两个函数的标准实现在 hackage 上可用：

 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 }
   -- ...
   {-# MINIMAL compare | (<=) #-}

如您所见，这两个函数是根据彼此定义的，因此它会无休止地冻结/循环。最小编译指示用于警告，可以在 documentation 中看到

Minimal complete definition
compare | (<=)

Answer 2

Ord class 的文档包括关于“最小定义”的部分：

Minimal complete definition
compare | (<=)

这意味着您必须至少定义compare或(<=)之一。否则，class 提供的默认定义存在崩溃或循环的危险。

此外，即使没有明确记录，重要的是 Eq 和 Ord 的定义要兼容。如果 tree3 <= tree4 和 tree3 >= tree4，那么你最好有 tree3 == tree4。您的定义不满足这一点，因为您的 Ord 实例忽略了节点的内容，但自动派生的 Eq 实例将比较它们。

您应该编写自己的 Eq 实例和您自己的最小 Ord 实例：

data Tree a = Node a [Tree a] deriving (Show)
instance (Eq a) => Eq (Tree a) where
  Node _ list1 == Node _ list2 = list1 == list2
instance (Ord a) => Ord (Tree a) where
  Node _ list1 <= Node _ list2 = list1 <= list2

在此之后，所有比较运算符都应该可以正常工作：

λ> compare tree1 tree2
LT
λ> tree1 == tree2
False
λ> tree1 < tree2
True
λ> tree1 <= tree2
True
λ> tree1 >= tree2
False
λ> tree1 > tree2
False
λ> tree1 == tree2
False
λ> tree1 /= tree2
True

仅供参考，您的原始定义循环的原因有点模糊。使用您原来的错误定义：

data Tree a = Node a [Tree a] deriving (Eq,Show)
instance (Ord a) => Ord (Tree a) where
  Node a list1 >= Node b list2 = (list1 > list2) || (list1 == list2)
  (Node a list1) > (Node b list2) = (list1 > list2)

您会发现以下内容有效：

> Node 1 [] >= Node 2 []
True

但以下挂起：

> [Node 1 []] >= [Node 2 []]
Interrupted.

问题是列表的 Ord 定义是根据 compare 定义的，所以即使它 看起来 就像你的定义只是使用 >= 和 >，它在比较子节点列表时也在幕后使用 compare。由于 compare 的默认定义是根据 <= 定义的，而 <= 的默认定义是根据 compare 定义的，因此默认定义中出现了一个循环。

Ord 实例比较树高度冻结与 >= 或 >

Ord instance comparing tree height freezes with >= or >

haskell