GHC擅长折叠东西。你的类型结构包含了足够的信息，你想要的按序遍历策略对机器来说是显而易见的。要调用这个魔法咒语，说出 ”deriving Foldable！"，GHC就会为你写函数。

{-# LANGUAGE DeriveFoldable #-}
data BinaryTree a = Leaf
                  | Node (BinaryTree a) a (BinaryTree a)
                  deriving Foldable

现在我们有

foldTree = foldr

这里一个有趣的推论是，您可以通过改变类型的形状来改变遍历顺序。
既然我们在这里，请注意您的需求。您希望使用foldr实现一个函数，它可以完全相同地拆分树并将其重新组合在一起，等效于id。这是不可能的。foldr提供对Foldable结构的元素的 * 顺序 * 访问，删除树中元素的精确位置之类的信息。最好的情况是，您可以构建一个列表形状的树，元素沿着右 Backbone.js 出现：

toListShapedTree = foldr (Node Leaf) Leaf

你想要的是一个 * 退化 *：

cata :: (b -> a -> b -> b) -> b -> BinaryTree a -> b
cata node leaf Leaf = leaf
cata node leaf (Node l x r) = node (cata node leaf l) x (cata node leaf r)

请注意node参数的额外参数！此规范为折叠函数提供了对Node构造函数参数的访问。与Foldable不同，结构的退化类型是特定于该结构的。我们不会因为将所有内容作为列表查看而丢失信息。现在，您可以编写：

cataId = cata Node Leaf

如果你执意使用foldr，一个策略是把位置信息带在身边。首先用位置标记每个元素，然后在折叠中使用这些数据来重建树。对我来说这是一个很难的工作。

我想你是在寻找这种褶皱：

foldTree :: (a -> b -> b) -> b -> BinaryTree a -> b
foldTree _ base Leaf = base
foldTree fn base (Node left a right) = foldTree fn base' left
   where
   base'  = fn a base''
   base'' = foldTree fn base right

这大概就是自动deriving Foldable所生成的内容。
上面是一个顺序折叠，首先折叠左边的部分，然后折叠中间的部分，然后折叠右边的部分。
一个等效但效率较低的变体是将树转换为带有in-visit的列表，然后在结果上应用foldr fn base。可以将foldr“分散”到所有列表生成中，恢复上面的代码。

我在艾伦& Moronuki的 Haskell Programming from first principles 中做了一个练习后来到这里。这个问题听起来像是同一个练习，所以，不管它有什么价值，从一个初学者到另一个初学者，这里是我想到的。
我看到了三种折叠二叉树的方法。当折叠一个序列时，有两种方法：左折和右折。一种方法是将给定的函数应用于（1）列表的头部和（2）应用于列表尾部的递归调用的返回值。这就是右折。
另一种顺序折叠的方法是，首先递归地调用fold：（1）给定函数的返回值应用于列表的头部，（2）应用于列表的尾部，这就是左折叠。
但是在二叉树中，每个值可以有 * 两个 *“后续”值，而不是列表中的一个。因此，必须有两个递归调用fold。因此，对传递函数的调用可以在两个递归调用之外，也可以在两个递归调用之内，或者在它们之间。如果我分别调用左、右和中心fold，我会得到以下结果：

-- Fold Right for BinaryTree

foldTreer :: (a -> b -> b) -> b -> BinaryTree a -> b
foldTreer f z Leaf = z
foldTreer f z (Node left a right) =
    f a (foldTreer f (foldTreer f z left) right)

-- Fold Left for Binary Tree

foldTreel :: (a -> b -> b) -> b -> BinaryTree a -> b
foldTreel f z Leaf = z
foldTreel f z (Node left a right) =
    foldTreel f (foldTreel f (f a z) left) right

-- Fold Center for Binary Tree

foldTreec :: (a -> b -> b) -> b -> BinaryTree a -> b
foldTreec f z Leaf = z
foldTreec f z (Node left a right) =
    foldTreec f (f a (foldTreec f z left)) right

我第一次看到 haskell 是在几周前，所以我可能什么都错了，但在我看来就是这样。

我认为你需要合并中间点，然后再去右边的子树：

foldTree :: (a -> b -> b) -> b -> BinaryTree a -> b
foldTree _ base Leaf = base
foldTree fn base (Node left a right) = foldTree fn middlePoint right
  where leftFold = foldTree fn base left
        middlePoint = fn a leftFold

谢谢你的回答。我想我会让它保持原样，因为这些原因：
1.在问题中给出了类型签名，所以我认为这就是他们想要的。
1.问题提到“任何遍历顺序都可以”。
1.它可以工作，只是不按顺序。例如，foldTree (:) [] tree将创建一个节点列表，但不按顺序。然而，foldTree (+) 0 tree创建一个总数，其中顺序是无关紧要的。

我想你是在找一个

foldl :: (b -> a -> b) -> b -> Tree a -> b
foldl _ e Leaf = e
foldl f e (Node x l r) = foldl f (f (foldl f e x) l) r

这将为您工作
另外，如果您需要foldr;

foldr :: (a -> b -> b) -> b -> Tree a -> b
foldr _ base Leaf = base
foldr fn base (Node left a right) = fn a (foldr fn acc right)
         where acc = foldr fn base left