haskell - 两棵二叉树返回一个布尔值

Question

这个函数返回的值是什么意思？如果你愿意，你可以用图表来解释

data Tree a = Empty_Tree | Node {element :: a, left_tree,right_tree :: Tree a}
gurgle :: Tree a -> Tree a -> Bool
gurgle tree_a tree_b = case (tree_a, tree_b) of
      (Empty_Tree , Empty_Tree ) -> True
      (Empty_Tree , _ ) -> False
      (_ , Empty_Tree ) -> False
      (Node _ left_a right_a, Node _ left_b right_b) -> gurgle left_a right_b
                                                        && gurgle right_a left_b

Answer 1

让我们画出来。首先，我将使用一个小圆圈表示空树，一个圆圈表示节点处的数据，子树有两个分支。left自己也是right树。

OK，让我们一行一行的看代码，把case语句解包成顶层的模式匹配，因为

function x y = case (x,y) of
    (0,1) -> this
    (1,10) -> that

可以写

function 0 1 = this
function 1 10 = that

gurgle Empty_Tree Empty_Tree = True

在这里要注意很多东西 - 如果它们都是空的，那就是肯定的。好的。

汩汩 Empty_Tree _ = False

这意味着我们会得到类似的东西

因为False无论第二个参数是什么，它都会给出。我们已经消除了第二个参数Empty_Tree在最后一行的情况，所以第二个参数必须非空才能在此处给出 False。

下一行很像，只是反其道而行之：

gurgle _ Empty_Tree = False

再说一次，像这样的东西

得到否定的答案。我开始怀疑，一旦我阅读了这两行，它就会检查两棵树的形状是否相同。

递归案例

gurgle xy = gurgle (left_tree x) (right_tree y) && gurgle (right_tree x) (left_tree y)

这是最有趣的一个。注意它正在做的交换方面的事情。这不仅仅是检查两者的子树是否相同，而是比较左右。

还要注意它忽略了节点上的值——这就是我在这个例子中去掉数字的原因。

我们需要什么才能使它成为真实？

为了做到这一点，我们需要一个左边的形状来匹配另一个右边的形状：

你想说什么？

递归情况说一个的左边必须匹配另一个的右边。当您忽略这些值时，这些树必须是彼此的镜像。

模式匹配中发生了什么？

原来的递归案例说

   (Node _ left_a right_a, Node _ left_b right_b) -> gurgle left_a right_b
                                                    && gurgle right_a left_b

让我们为该代码着色以匹配上图：

给它上色是一个很好的视觉线索，因为left_a左边的名字等并不意味着什么特别，它们只是用来指代树的一部分。

哪些位？

这与 Node 的定义相匹配：

第一个（灰色）位是元素。element现在是从树节点到值的函数。

第二个（浅棕色）位是左子树，left_tree. 它可能很大很复杂，也可能只是一个Empty_Tree. （它可以是任何树。）

第三个（淡橙色）位是右子树right_tree。它们与我的图表相匹配，如下所示：

我没有在彩色框中输入任何细节——它可以是任何一棵树，无论大小。

当您的原始代码将其放在左侧时

它为子树命名，以便它可以直接引用它们，而不是使用left-treeandright_tree函数。