应对各种场合的折叠
我们实际上可以提出一个通用的折叠概念,适用于各种不同类型。也就是说,我们可以系统地定义一个适用于列表、树等类型的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
只是让我们“总结”使用代数定义的结构。