适合各种场合的折叠
我们实际上可以提出一个通用的折叠概念，它可以应用于一大堆不同的类型。也就是说，我们可以系统地fold为列表、树等定义一个函数。
这个通用的概念fold对应于他的评论中提到的@pelotom 的catamorphisms。
递归类型
关键的见解是这些fold函数是在递归类型上定义的。尤其：
data List a = Cons a (List a) | Nil
data Tree a = Branch (Tree a) (Tree a) | Leaf a
这两种类型显然都是递归List的——在这种Cons情况下和Tree在这种Branch情况下。
固定点
就像函数一样，我们可以使用固定点重写这些类型。记住 的定义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允许我们将ListContainers 嵌套到任意深度。所以我们可以有：
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
我认为从ListContainerto的映射List非常自然：我们没有显式递归，而是将递归部分设为变量。然后我们只需要Fix根据需要填写该变量。
我们也可以写一个类似的类型Tree。
“展开”固定点
那么我们为什么要关心呢？我们可以定义fold使用. 尤其：Fix
fold :: Functor f => (f a -> a) -> (Fix f -> a)
fold h = h . fmap (fold h) . unRoll
where unRoll (Roll a) = a
本质上，折叠所做的只是一次展开一层“滚动”类型，每次都对结果应用一个函数。这种“展开”让我们可以为任何递归类型定义折叠，并巧妙而自然地概括这个概念。
对于列表示例，它的工作方式如下：
- 在每一步，我们打开包装
Roll以获得 aCons或 aNil
- 我们使用 对列表的其余部分进行递归
fmap。
- 在这种
Nil情况下，fmap (fold h) Nil = Nil，所以我们只返回Nil。
- 在这种
Cons情况下，fmap只是继续折叠列表的其余部分。
- 最后，我们得到了一堆以 --
fold结尾的嵌套调用，Nil就像标准一样foldr。
比较类型
现在让我们看看两个折叠函数的类型。首先，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。现在我们有两个函数_ -> bwhere _is()和a -> b. 为了让生活更简单，让我们 curry 给我们的第二个函数(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，同时具有 ana和 a b。换句话说，Nilis like()和Consis like (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。树容器有两种情况：Branch，包含两个bs 和Leaf，包含一个a。
所以这些折叠类型是同构的，与列表示例相同。
概括
有一个清晰的模式正在出现。给定一个正常的递归数据类型，我们可以系统地创建该类型的非递归版本，这让我们可以将类型表示为函子的不动点。这意味着我们可以机械地提出fold所有这些不同类型的函数——事实上，我们可能可以使用 GHC 泛型或类似的东西来自动化整个过程。
从某种意义上说，这意味着我们并没有真正fold为不同类型提供不同的功能。相反，我们有一个非常fold多态的函数。
更多的
我首先从Conal Elliott的一次演讲中完全理解了这些想法。这更详细，也谈到了unfold，这是对偶fold。
如果您想更深入地研究这类事情，请阅读精彩的“使用香蕉、镜头、信封和铁丝网进行函数式编程”论文。除其他外，这引入了与折叠和展开相对应的“变形”和“变形”的概念。
代数（和代数）
此外，我无法抗拒为自己添加一个插头：P。您可以看到我们在此处使用的方式与我在另一个 SO 答案中Either谈论代数时使用它的方式之间存在一些有趣的相似之处。
fold代数和代数之间其实有很深的联系；此外，unfold--前面提到的--的对偶fold连接到coalgebras，它是代数的对偶。重要的想法是代数数据类型对应于“初始代数”，它也定义了我在其余答案中概述的折叠。
您可以在以下一般类型中看到此连接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只是让我们“总结”使用代数定义的结构。