Haskell二叉树函数

Question

我必须在 haskell 中编写一个函数来检查两个二叉树是否是彼此的镜像。这是我到目前为止所拥有的，但我不知道 True && areMirrorImages 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)意味着您需要比较(测试Eq质量)两棵树。您不需要这样做，因为您正在测试树是否是彼此的镜像，而不是它们是否相等。

树木何时互为镜像？当 key 相同且相反的分支互为镜像时。

关键是相同的: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。