How does object ordering work?

at first I should say that I have never seen any Haskell code. Now I have an algorithm which I have to implement in another language. Unfortunately, this algorithm relies on some Haskell characteristics and features so I would like to ask you for help, how does this work to be able to implement it correctly?

There is the code:

data Utree = Tree[Utree]

instance Eq Utree where
    Tree(p) == Tree(q) = p == q
instance Ord Utree where
    Tree(p) <= Tree(q) = p <= q

norm(Tree(p)) = Tree(sort(map norm p))


iso p q = (norm p) == (norm q)

sort[] = []
sort(a:开发者_如何学编程x) = ins a (sort x)

ins a [] = [a]
ins a (b:x)
   | a <= b = a:b:x
   | a > b = b:(ins a x)

Now, how I take it. UTree is some kind of tree structure which uses list to hold subtrees. ( Resp. It should be ) Defined sort is insert sort, that is clear.

But there is used ordering Eq a Ord but I absolutely don't know how this works. There is some definition of TreeA < TreeB and I don't know how it is compared.

Can you explain it, please?

Your code is giving the definitions of what it means to compare two trees. For example, for equality:

instance Eq Utree where
    Tree(p) == Tree(q) = p == q

It says that the equality of two trees is the same as the equality of their lists of subtrees. So in this code, p and q are lists. Equality on lists is pre-defined in Haskell as that two trees are equal if they are the same length and the elements are pairwise equal. Since the elements of p and q are trees, this recursively calls the equality comparison on trees.

Intuitively this means that two trees are equal if they have the same shape.

Similarly, the ordering of two trees is defined in terms of the ordering of the list of subtrees.

instance Ord Utree where
    Tree(p) <= Tree(q) = p <= q

The ordering on lists in Haskell is pre-defined as a lexicographic ordering based on the ordering of the elements, i.e. you compare the two first elements. Again, this calls the comparison on trees recursively. If they are different, use that as the answer, otherwise compare the next two elements etc. If you run out of one list before the other, the shortest list comes first in the ordering.

In this case, this means that the ordering of these trees is roughly that we look at the leftmost point at which they differ. At this point, the "smallest" tree comes first in the ordering.

For example, let's say we have two trees:

*Main> let a = Tree [Tree [], Tree [Tree []]]
*Main> let b = Tree [Tree [Tree []], Tree []] 
*Main> compare a b
LT

The trees in this example look like this:

         *               *
a =     / \        b =  / \
       x   *           x   *
          /           /
         *           *

So a is less than b because when we look at the leftmost point where they differ, x, a has an empty subtree, whereas b has a single node there.

UTrees are compared by comparing their element lists, this is what can be seen from the instance definitions. Lists are compared in the usual way by comparing their elements pairwise. For example, the implementation of == for lists looks like this:

[] == [] = True
(a:as) == (b:bs) = a == b && as == bs
_ == _ = False

All information regarding the Eq and Ord classes can be found in the relevant Haskell report, which I am sure you have handy.

Comparison function for lists could look like this (actually, it is a bit different, but this is not relevant here):

[] > _ = False     -- the empty list is not greater than any other list
(a:as) > [] = True -- nonempty is greater than empty
(a:as) > (b:bs)
   | a < b = False
   | a > b = True
   | otherwise = as > bs