使用翻轉操作符對二叉樹進行後序遍歷。左邊評估右邊？

Question

鑑於二叉樹

data BinaryTree a = 
    Leaf 
    | Node (BinaryTree a) a (BinaryTree a) 
    deriving (Show) 

我的解決方案，以預購/序使用:

preorder :: BinaryTree a -> [a] 
preorder Leaf = [] 
preorder (Node left x right) = x : preorder left ++ preorder right 

inorder :: BinaryTree a -> [a] 
inorder Leaf = [] 
inorder (Node left x right) = inorder left ++ (x : inorder right) 

但對後序完成的，這並不工作：

postorder :: BinaryTree a -> [a] 
postorder Leaf = [] 
postorder (Node left x right) = (postorder left ++ postorder right) : x 

是理所當然的因爲我想出了這種類型的簽名是

(:) :: a -> [a] -> [a] 

我以爲我可以這樣做解決這個問題：

append :: [a] -> a -> [a] 
append = flip (:) 

postorder :: BinaryTree a -> [a] 
postorder Leaf = [] 
postorder (Node left x right) = (postorder left ++ postorder right) `append` x 

但最終它給我相同的答案preorder。我很困惑，因爲我認爲左手邊會在右手邊進行評估。

我以爲這是因爲我知道後序也可以這樣解決（這個方法不是一個球迷，因爲它意味着使XA列表無故，但追加）：

postorder (Node left x right) = postorder left ++ postorder right ++ [x] 

是否有人可以告訴我我出錯的地方，也許爲什麼後序與前序有相同的結果？

Answer 1

讓我們使用等式推理來查看您的postorder與append失敗的位置。

append = flip (:) 

(postorder left ++ postorder right) `append` x 
-- bring append to front 
append (postorder left ++ postorder right) x 
-- substitute append 
flip (:) (postorder left ++ postorder right) x 
-- expand flip 
(\f x y -> f y x) (:) (postorder left ++ postorder right) x 
-- partially apply expanded flip 
(\x y -> y : x) (postorder left ++ postorder right) x 
-- finish application 
x : (postorder left ++ postorder right) 

現在，因爲我們知道一般(x : y) ++ z === x : (y ++ z)我們可以看到你的「後序」的方法其實就相當於你的預購方法！

您所犯的錯誤是試圖考慮評估的順序，以及諸如「左手邊將在右手邊之前評估」等理念的原因。正如你從這個等式方法中可以看到的那樣，在一個純懶惰的功能設置中，評估的順序可能大體上被忽略。重要的是通過替換和簡化功能本身。

如果你不喜歡把x在列表中只是將其追加，這裏的練習，寫一個函數

consEnd :: [a] -> a -> [a] 

是插入到直接在列表的最後的東西。