应对各种场合的折叠
我们实际上可以提出一个通用的折叠概念，适用于各种不同类型。也就是说，我们可以系统地定义一个适用于列表、树等类型的fold函数。
这个通用的fold概念对应于@pelotom在评论中提到的“消解”。
递归类型
关键的洞见是，这些fold函数是针对递归类型定义的。特别是：
data List a = Cons a (List a) | Nil
data Tree a = Branch (Tree a) (Tree a) | Leaf a
这两种类型都明显是递归的——在
Cons情况下是
List，而在
Branch情况下是
Tree。
不动点
与函数一样，我们可以使用不动点来重写这些类型。记得
fix的定义：
fix f = f (fix f)
我们实际上可以为类型编写类似的代码，只需添加一个额外的构造函数包装器即可。
newtype Fix f = Roll (f (Fix f))
就像`fix`定义了一个函数的不动点一样，这个定义定义了一个函子的不动点。我们可以使用这个新的`Fix`类型来表示所有递归类型。
这使我们能够将`List`类型重写为以下形式：
data ListContainer a rest = Cons a rest | Nil
type List a = Fix (ListContainer a)
基本上，
Fix 允许我们嵌套任意深度的
ListContainer。因此，我们可以有以下内容：
Roll Nil
Roll (Cons 1 (Roll Nil))
Roll (Cons 1 (Roll (Cons 2 (Roll Nil))))
这三个分别对应[], [1]和[1,2]。
看到ListContainer是一个Functor很容易：
instance Functor (ListContainer a) where
fmap f (Cons a rest) = Cons a (f rest)
fmap f Nil = Nil
我认为从
ListContainer到
List的映射非常自然：我们将递归部分变成一个变量，而不是明确地进行递归。然后，我们只需使用
Fix来填充相应的变量即可。
我们也可以为
Tree编写类似的类型。
“展开”固定点
那么我们为什么要关心呢？我们可以为使用
Fix编写的任意类型定义
fold。特别地：
fold :: Functor f => (f a -> a) -> (Fix f -> a)
fold h = h . fmap (fold h) . unRoll
where unRoll (Roll a) = a
基本上，fold 所做的就是一次只展开“卷起”的类型一层，每次对结果应用一个函数。这种“展开”让我们为任何递归类型定义折叠，并将概念整齐自然地推广。
对于列表示例，它的工作方式如下：
1. 在每个步骤中，我们展开 Roll 以获取 Cons 或 Nil。
2. 我们使用 fmap 递归到列表的其余部分。
在 Nil 情况下，fmap (fold h) Nil = Nil，因此我们只返回 Nil。
在 Cons 情况下，fmap 只会继续对列表的其余部分进行折叠。
最后，我们得到了一堆嵌套的 fold 调用，最终以 Nil 结尾——就像标准的 foldr 一样。
比较类型
现在让我们看一下两个 fold 函数的类型。首先是 foldr:
foldr :: (a -> b -> b) -> b -> [a] -> b
现在，
fold专用于
ListContainer:
fold :: (ListContainer a b -> b) -> (Fix (ListContainer a) -> b)
一开始，它们看起来完全不同。然而，稍加调整，我们可以证明它们是相同的。foldr 的前两个参数是 a -> b -> b 和 b。我们有一个函数和一个常量。我们可以将 b 视为 () -> b。现在我们有两个函数 _ -> b，其中 _ 是 ()，和 a -> b。为了简化生活，让我们对第二个函数进行柯里化，得到 (a, b) -> b。现在我们可以使用 Either 将它们写成一个 单独的 函数：
Either (a, b) () -> b
这是真的，因为给定
f :: a -> c 和
g :: b -> c，我们总是可以写出以下内容：
h :: Either a b -> c
h (Left a) = f a
h (Right b) = g b
现在我们可以将foldr视为：
foldr :: (Either (a, b) () -> b) -> ([a] -> b)
(我们总是可以像这样在箭头周围添加括号，只要它们是右结合的。)
现在让我们看一下ListContainer。这种类型有两种情况：Nil，它不携带任何信息，和Cons，它既有a又有b。换句话说，Nil就像()，而Cons就像(a，b)，因此我们可以写成:
type ListContainer a rest = Either (a, rest) ()
显然，这与我在上面使用的foldr相同。因此，现在我们有：
foldr :: (Either (a, b) () -> b) -> ([a] -> b)
fold :: (Either (a, b) () -> b) -> (List a -> b)
实际上，这些类型是同构的——只是写同一件事情的不同方式！我觉得这很酷。
(顺便说一下，如果你想了解更多关于使用类型进行推理的内容，请查看代数数据类型的代数, 这是一系列关于此问题的漂亮博客文章。)
回到树
所以，我们已经看过如何为写成不动点形式的类型定义通用的fold函数。我们也看到了这直接对应于列表的foldr函数。现在让我们来看看你的第二个例子，二叉树。我们有以下类型:
data Tree a = Branch a (Tree a) (Tree a) | Leaf a
我们可以按照我上面的规则，使用
Fix来重写这段内容：我们用一个类型变量替换递归部分。
data TreeContainer a rest = Branch rest rest | Leaf a
type Tree a = Fix (TreeContainer a)
现在我们有一棵树
fold:
fold :: (TreeContainer a b -> b) -> (Tree a -> b)
你原始的foldTree看起来像这样：
foldTree :: (b -> b -> b) -> (a -> b) -> Tree a -> b
foldTree接受两个函数；我们将先进行柯里化，然后使用Either将它们合并为一个函数：
foldTree :: (Either (b, b) a -> b) -> (Tree a -> b)
我们还可以看到
Either (b, b) a 如何同
TreeContainer a b 同构。 Tree container 有两种情况：包含两个
b 的
Branch 和包含一个
a 的
Leaf。
所以这些折叠类型与列表示例的同构方式相同。
通用化
出现了明显的模式。给定一个普通的递归数据类型，我们可以系统地创建该类型的非递归版本，从而让我们将该类型表示为一个 functor 的不动点。这意味着我们可以机械地为所有这些不同类型想出
fold 函数 - 实际上，我们可能可以使用 GHC Generics 或类似工具自动化整个过程。
在某种意义上，这意味着我们实际上并没有不同类型的不同
fold 函数。相反，我们有一个非常多态的单一
fold 函数。
更多
我最初从Conal Elliott的演讲中完全理解了这些概念。该演讲更详细地介绍了unfold，它是fold的对偶。
如果你想更深入地研究这种东西，可以阅读"Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire" paper。除其他外，这还介绍了“catamorphisms”和“anamorphisms”的概念，它们对应于folds和unfolds。
代数（和余代数）
此外，我不能抵制自己的诱惑 :P。你可以看到我们在这里使用Either的方式与我在另一个SO答案中谈论代数时使用它的方式之间存在一些有趣的相似之处。
实际上，
fold和代数之间存在着深刻的联系；此外，
unfold--上述
fold的对偶--与余代数相关联，它是代数的对偶。重要的思想是：代数数据类型对应于“初始代数”，这也定义了我回答中其余部分所概述的折叠。
您可以在
fold的一般类型中看到这种联系：
fold :: Functor f => (f a -> a) -> (Fix f -> a)
f a -> a 这个术语看起来非常熟悉！请记住，f-代数的定义类似于：
class Functor f => Algebra f a where
op :: f a -> a
所以我们可以把fold简单地理解为：
fold :: Algebra f a => Fix f -> a
基本上，
fold 只是让我们“总结”使用代数定义的结构。
