樹遍歷混淆？

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 d s l），但我不明白爲什麼這是使用遞歸。

有沒有人有一個簡單的解釋？

Answer 1

這可能不是您希望的簡單解釋，但它可能有助於嘗試通過一個簡短的示例。閱讀用鉛筆和紙得心應手以下，並嘗試以確保一切自己：

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

我想你會的分支，然後同意這應該左轉進入節點「B」直接進入節點「 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 =空，r =（Node'C'Empty Empty））。在RHS這種模式是：

Node x l (changeNode ds r) 

成爲（與適當的subtitutions）：

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 =空和r =空給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 =所有節點'B'分支，r =所有節點'D'分支，但不是第（1）行，我們將使用非遞歸右側「節點xlr」以獲得以下代替行（1）：

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

請參閱？沒有遞歸調用，在changeNode'消耗'L'之後，它完成了。它將返回原始樹，而無需進一步處理。需要遞歸調用來保持進程一直移動，直到方向向量爲空，並且可以將第三個模式（唯一實際更改節點的模式）應用於樹中的正確位置。

所以，簡短的解釋（直到你已經完成上面的例子纔有意義）是前兩個changeNode的遞歸模式被用來將changeNode調用通過樹結構移動到最終目標節點應用最終模式來更改節點值。