haskell二叉树函数

Question

我必须在haskell中编写一个函数来检查两个二进制树是否是彼此的镜像.这是我到目前为止,但我不知道True && isMirrorImages l1 r2 && areMirrorImages r1 l2是否是正确的方法.我试图用递归调用areMirrorImages函数的结果来逻辑AND True.

-- Tests whether two BinaryTrees are mirror images of one another
areMirrorImages :: (Eq (BinaryTree a), Eq a) => BinaryTree a -> BinaryTree a -> Bool
areMirrorImages Empty Empty = True
areMirrorImages _ Empty = False
areMirrorImages Empty _     = False
areMirrorImages (Node x1 left1 right1) (Node x2 left2 right2) = 
    if (x1 == x2 && left1 == right2 && right1 == left2)
then True && (areMirrorImages left1 right2) && (areMirrorImages right1 left2)
else False 

这是我尝试编译时得到的错误:

A2.hs:2:0:
    Non-type variables, or repeated type variables,
      in the constraint: Eq (BinaryTree a)
    (Use -fglasgow-exts to permit this)
    In the type signature:
      areMirrorImages :: (Eq (BinaryTree a), Eq a) =>
                         BinaryTree a -> BinaryTree a -> Bool

我似乎无法弄清楚什么是错的

Answer 1

要求Eq (BinaryTree a)意味着你需要比较(测试Equality)两棵树.您不需要这样做,因为您正在测试树是否是彼此的镜像,而不是它们是否相等.

什么时候树木相互映射？当键是相同的并且当相对的分支是彼此的镜像时.

关键是一样的: x1 == x2

相反的分支是镜像: areMirrorImages left1 right2 && areMirrorImages right1 left2

把它翻译成Haskell:

areMirrorImages (Node x1 left1 right1) (Node x2 left2 right2) = 
    x1 == x2 && areMirrorImages left1 right2 && areMirrorImages right1 left2

Haskell允许您编写简洁,直接的代码.没有必要使用if then else.