Ord instance comparing tree height freezes with >= or >-CodePudding

It is not possible to compare trees in height with signs greater than (>) and greater than or equal to (>=). Here is my code. It just freezes at the command 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]

CodePudding user response：

The documentation for the Ord class includes a section on the "minimal definition":

Minimal complete definition
compare | (<=)

This means that you must define at least one of compare or (<=). Otherwise, there is a danger that the default definitions provided by the class will either crash or loop.

In addition, even though it's less clearly documented, it's important that the definitions of Eq and Ord be compatible. If tree3 <= tree4 and tree3 >= tree4, then you'd better have tree3 == tree4. Your definition doesn't satisfy this, because your Ord instance ignores the contents of the nodes, but the automatically derived Eq instance will compare them.

You should instead write your own Eq instance and your own minimal Ord instance:

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

After this, all comparison operators should work correctly:

λ> 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

FYI, the reason your original definition loops is a little obscure. With your original incorrect definition:

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)

you'll find that the following works:

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

but the following hangs:

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

The problem is that the definition of Ord for lists is defined in terms of compare, so even though it looks like your definition is only using >= and >, it's also using compare behind the scenes when it compares lists of child nodes. Since the default definition of compare is defined in terms of <= and the default definition of <= is defined in terms of compare, you get a loop in the default definitions.

CodePudding user response：

TL;DR: define <=.

Enable warnings, it will say:

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

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

For Ord, you must implement at least one of these: <= or compare.

This is due to the standard implementation for these two functions of Ord which is available on 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 | (<=) #-}

As you can see, these two functions are defined in terms of one another, so it will freeze / loop endlessly. And the minimal pragma is used for the warning and can be seen in the documentation as

Minimal complete definition
compare | (<=)