树遍历混乱？

Question

我有以下数据类型(来源:http://learnyouahaskell.com/zippers):

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show, Eq, Ord)

然后我有以下函数,它遍历树并根据方向指令替换节点:

data Direction = L | R deriving (Show, Eq, Ord)
type Directions = [Direction]

changeNode :: Directions -> Tree Char -> Tree Char
changeNode (L : ds) (Node x l r) = Node x (changeNode ds l) r
changeNode (R : ds) (Node x l r) = Node x l (changeNode ds r)
changeNode [] (Node _ l r) = Node 'P' r l

但是我不明白这方面的功能:

changeNode (L : ds) (Node x l r) = Node x (changeNode ds l) r

我看到这是使用递归(changeNode ds l),但我不明白为什么这是使用递归.

有没有人有一个简单的解释？

Answer 1

这可能不是您希望的简单解释,但它可能有助于尝试通过一个简短的例子.用铅笔和纸阅读以下内容,并尝试自己验证一切:

changeNode [L,R]
  (Node 'A' (Node 'B' Empty (Node 'C' Empty Empty)) (Node 'D' Empty Empty))

我假设你会同意这应该留在Node'B'分支然后直接进入Node'C'分支,最后用'P'代替'C',对吧？

它是如何做到的？好吧,上面的表达式匹配changeNode的第一个模式,即类型声明之后的第一个模式.具体来说,它与变量赋值匹配:ds = [R],x ='A',l =整个节点'B'分支,r =整个节点'D'分支.因此,我们可以使用与该匹配模式相对应的右侧来重写它.该模式的右侧是:

Node x (changeNode ds l) r

并替换匹配的变量给出:

Node 'A' (changeNode [R] (Node 'B' Empty (Node 'C' Empty Empty)))
         (Node 'D' Empty Empty)    -- (1)

现在你看到发生了什么？changeNode的第一个模式通过"消耗"方向列表的第一个字母(已从[L,R]更改为[R])并将changeNode调用向下推入左分支来进行操作.

现在,请专注于此递归changeNode调用的值.这次它匹配changeNode的第二个模式(ds = [],x ='B',l = Empty,r =(Node'C'Emp empty Empty)).该模式的RHS是:

Node x l (changeNode ds r)

成为(适当的减少):

Node 'B' Empty (changeNode [] (Node 'C' Empty Empty))

并将此值替换回第(1)行,我们得到:

Node 'A' (Node 'B' Empty (changeNode [] (Node 'C' Empty Empty)))
         (Node 'D' Empty Empty)   -- (2)

再次,看看第二次调用如何消耗方向向量中的"R"并将changeNode调用推送到节点"B"的右侧分支.最后,这最后一次递归changeNode调用的价值是什么？好吧,它匹配第三个模式,l = Empty,r = Empty,给出RHS值:

Node 'P' Empty Empty

并代入第(2)行,我们得到:

Node 'A' (Node 'B' Empty (Node 'P' Empty Empty)) (Node 'D' Empty Empty)

这正是我们想要的.

将所有这些与如果定义是非递归的将会发生的情况进行对比:

changeNode' :: Directions -> Tree Char -> Tree Char
changeNode' (L : ds) (Node x l r) = Node x l r
changeNode' (R : ds) (Node x l r) = Node x l r
changeNode' [] (Node _ l r) = Node 'P' r l

在这种情况下,我们的简单示例将再次匹配第一个模式,ds = [R],x ='A',l =所有Node'B'分支,r =所有Node'D'分支,但而不是line(1),我们将使用非递归右侧"Node xl r"来代替line(1)得到以下内容:

Node 'A' (Node 'B' Empty (Node 'C' Empty Empty)) (Node 'D' Empty Empty)

看到？没有递归调用,在changeNode'消耗'L'之后,它就完成了.它返回原始树而不进行进一步处理.需要递归调用以保持进程一直移动,直到方向向量为空,并且第三个模式(实际更改节点的唯一模式)可以应用于树中的正确位置.

因此,简短的解释(直到您完成上述示例才真正有意义)是,前两个用于changeNode的递归模式用于将changeNode调用通过树结构移动到最终目标节点,其中应用最终模式来更改节点值.