使用 flipped : 运算符的二叉树的后序遍历。右手侧先于左评估？

Question

给定二叉树

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

我对 preorder/inorder 的解决方案是使用 :

完成的

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 相同的答案。我很困惑，因为我假设左侧会在右侧之前被评估。

我之所以这么认为是因为我知道后序也可以这样解决（不是这种方法的粉丝，因为它意味着将 x 无缘无故地添加到列表中）：

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) 我们可以看到您的 "postorder" 方法实际上等同于您的预购方法！

你犯的错误是试图考虑评估的顺序，并用 "the left hand side would be evaluated before the right hand side" 这样的想法进行推理。正如您从这种方程式方法中看到的那样，在纯粹的惰性函数设置中，求值顺序可能大体上会被忽略。重要的是通过功能本身的替代和简化。

如果您不喜欢将 x 放入列表中只是为了追加它，这里有一个练习，编写一个函数

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

直接在列表末尾插入内容。

使用 flipped : 运算符的二叉树的后序遍历。右手侧先于左评估？

Postorder traversal of binary tree using flipped : operator. Right hand side evaluated before left?

binary-tree

haskell