对象排序如何工作？

Question

起初我应该说我从未见过任何Haskell代码.现在我有一个算法,我必须用另一种语言实现.不幸的是,这个算法依赖于一些Haskell特性和功能,所以我想请求你帮忙,这是如何能够正确实现它的？

有代码:

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)

现在,我如何接受它.UTree是某种使用列表来保存子树的树结构.(相应应该是)定义的排序是插入排序,这很清楚.

但是,使用排序Eq一个Ord,但我绝对不知道如何工作的.TreeA <TreeB有一些定义,我不知道它是如何比较的.

你能解释一下吗？

Answer 1

您的代码给出了比较两棵树意味着什么的定义.例如,为了平等:

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

它说两棵树的平等与它们的子树列表的相等性相同.所以在这个代码,p并q都列出.列表中的等式是在Haskell中预定义的,因为如果两个树长度相同且元素成对相等,则它们是相等的.由于要素p和q是树木,这个递归调用树平等的比较.

直观地说,这意味着如果它们具有相同的形状,则两棵树是相同的.

类似地,两个树的排序是根据子树列表的顺序定义的.

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

Haskell中列表的排序是根据元素的排序预定义为词典排序,即您比较两个第一个元素.同样,这会以递归方式调用树上的比较.如果它们不同,则使用它作为答案,否则比较接下来的两个元素等.如果在另一个列表之前用完一个列表,则最短列表在排序中排在第一位.

在这种情况下,这意味着这些树的排序大致是我们看到它们不同的最左边的点.此时,"最小"树在排序中排在第一位.

例如,假设我们有两棵树:

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

这个例子中的树看起来像这样:

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

所以a不到b,因为当我们看一下它们的不同,最左边的点x,a有一个空的子树,而b有一个节点出现.