什么构成了除列表之外的types的折叠？
考虑一个单链表。 它看起来像
data List x = Node x (List x) | End 定义折叠函数是很自然的
reduce :: (x -> y -> y) -> y -> List x -> y
从某种意义上说， reduce f x0用reduce f x0代替每个Node用reduce f x0代替每个Node 。 这是前奏曲所指的折叠 。
现在考虑一个简单的二叉树：
data Tree x = Leaf x | Branch (Tree x) (Tree x)
定义一个函数，如
reduce :: (y -> y -> y) -> (x -> y) -> Tree x -> y
请注意， 这种减less具有完全不同的性质; 而基于名单的是一种固有的顺序，这种新的基于树的分类更具有分而治之的感觉。 你甚至可以想象在那里扔几个组合器。 （你会把这样的东西放在列表版本中？）
我的问题：这个function是否仍然被归类为“折叠”，还是别的？ （如果是这样，那是什么？）
基本上每当有人谈论折叠，他们总是谈论折叠列表 ，这本质上是连续的。 我想知道“顺序”是否是折叠定义的一部分，或者这是否是最常用的折叠例子的巧合属性。
Tikhon的技术水平下降了 我想我会尽量简化他所说的话。
不幸的是，“折叠”一词多年来变得模棱两可，意味着两件事之一：
- 按顺序依次减less集合。 在Haskell中，这就是“折叠”在
Foldable类中的意义，这是larsmans带来的。 - 你所要求的概念是：根据结构 “破坏”（与构造相反），“观察”或“消除”代数数据types。 也称为变质 。
一般可以定义这两个概念，以便一个参数化的函数能够处理各种types的函数。 第二种情况，吉洪展示了怎么做。
但是大多数情况下， Fix和代数都是如此，这是过度的。 让我们为任何代数数据types编写一个更简单的方法。 我们将使用Maybe ，pairs，lists和trees作为例子：
data Maybe a = Nothing | Just a data Pair ab = Pair ab data List a = Nil | Cons a (List a) data Tree x = Leaf x | Branch (Tree x) (Tree x) data BTree a = Empty | Node a (BTree a) (BTree a)
请注意， Pair不是recursion的; 我要展示的过程并不假定“fold”types是recursion的。 人们通常不会把这种情况称为“折叠”，但它确实是同一概念的非recursion情况。
第一步：给定types的折叠将消耗折叠types，并产生一些参数types作为结果。 我喜欢称后者r （“结果”）。 所以：
foldMaybe :: ... -> Maybe a -> r foldPair :: ... -> Pair ab -> r foldList :: ... -> List a -> r foldTree :: ... -> Tree a -> r foldBTree :: ... -> BTree a -> r
第二步：除了最后一个参数（结构的参数）之外，折叠需要的参数与types具有构造函数的参数一样多。 Pair有一个构造函数，我们其他的例子有两个，所以：
foldMaybe :: nothing -> just -> Maybe a -> r foldPair :: pair -> Pair ab -> r foldList :: nil -> cons -> List a -> r foldTree :: leaf -> branch -> Tree a -> r foldBTree :: empty -> node -> BTree a -> r
第三步：这些参数中的每一个都与它所对应的构造函数具有相同的元素。 让我们把构造函数作为函数，写出它们的types（确保typesvariables与我们写的签名中的typesvariables匹配）：
Nothing :: Maybe a Just :: a -> Maybe a Pair :: a -> b -> Pair ab Nil :: List a Cons :: a -> List a -> List a Leaf :: a -> Tree a Branch :: Tree a -> Tree a -> Tree a Empty :: BTree a Node :: a -> BTree a -> BTree a -> BTree a
第4步：在每个构造函数的签名中，我们将用我们的typesvariablesr （我们在折叠签名中使用的）replace它构造的所有数据types：
nothing := r just := a -> r pair := a -> b -> r nil := r cons := a -> r -> r leaf := a -> r branch := r -> r -> r empty := r node := a -> r -> r -> r
正如你所看到的，我已经从第二步中将结果签名“分配”给了我的虚拟typesvariables。 现在第5步：填入早期的草图折叠签名：
foldMaybe :: r -> (a -> r) -> Maybe a -> r foldPair :: (a -> b -> r) -> Pair ab -> r foldList :: r -> (a -> r -> r) -> List a -> r foldTree :: (a -> r) -> (r -> r -> r) -> Tree a -> r foldBTree :: r -> (a -> r -> r -> r) -> BTree a -> r
现在，这些是这些types折叠的签名。 他们有一个有趣的参数顺序，因为我通过从data声明和构造函数types中读取折叠types来机械地做到这一点，但由于某些原因，在函数式编程中，通常先将基本情况放在data定义中，然后recursion处理第一次定义fold定义。 没问题！ 让他们重新洗牌，让他们更传统：
foldMaybe :: (a -> r) -> r -> Maybe a -> r foldPair :: (a -> b -> r) -> Pair ab -> r foldList :: (a -> r -> r) -> r -> List a -> r foldTree :: (r -> r -> r) -> (a -> r) -> Tree a -> r foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r
这些定义也可以用机械方式填写。 让我们selectfoldBTree并逐步实现它。 给定types的折叠是我们想出来的types的一个函数，它满足这个条件：用types的构造函数进行折叠就是这个types的一个标识函数（与获得的值相同）。
我们将像这样开始：
foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r foldBTree = ???
我们知道它有三个参数，所以我们可以添加variables来反映它们。 我会用很长的描述性名字：
foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r foldBTree branch empty tree = ???
看data声明，我们知道BTree有两个可能的构造函数。 我们可以把这个定义分解成每一个的情况，并且为它们的元素填充variables：
foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r foldBTree branch empty Empty = ??? foldBTree branch empty (Branch alr) = ??? -- Let's use comments to keep track of the types: -- a :: a -- l, r :: BTree a
现在，缺less像undefined的东西，填补第一个等式的唯一方法是empty ：
foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r foldBTree branch empty Empty = empty foldBTree branch empty (Branch alr) = ??? -- a :: a -- l, r :: BTree a
我们如何填写第二个等式？ 再次，缺乏undefined ，我们有这样的：
branch :: a -> r -> r -> r a :: a l, r :: BTree a
如果我们有一个子subfold :: BTree a -> r ，我们可以做branch a (subfold l) (subfold r) :: r 。 但是，当然，我们可以很容易地写下“subfold”
foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r foldBTree branch empty Empty = empty foldBTree branch empty (Branch alr) = branch a (subfold l) (subfold r) where subfold = foldBTree branch empty
这是BTree的折叠，因为foldBTree Branch Empty anyTree == anyTree 。 请注意， foldBTree不是这种types的唯一function; 还有这个：
mangleBTree :: (a -> r -> r -> r) -> r -> BTree a -> r mangleBTree branch empty Empty = empty mangleBTree branch empty (Branch alr) = branch a (submangle r) (submangle l) where submangle = mangleBTree branch empty
但总的来说， mangleBTree没有所需的属性; 例如，如果我们有foo = Branch 1 (Branch 2 Empty Empty) Empty ，那么mangleBTree Branch Empty foo /= foo 。 所以mangleBTree ，虽然它有正确的types，但不是折叠。
现在让我们退一步从细节mangleTree ，把mangleTree集中在mangleTree示例的最后一点上。 折叠（从结构的意义上说，在我的答案的顶部＃2）只不过是代数types的最简单，非平凡的函数，以至于当你在types的构造函数中传递作为其参数时，它成为这种types的身份function。 （不平凡的意思是说像foo fz xs = xs这样的东西是不允许的）
这是非常重要的。 我喜欢想两个方法如下：
- 给定types的折叠可以“查看”该types的任何值所包含的所有信息。 （这就是为什么它能够使用types的构造函数完全“重构”该types的任何值）。
- 折叠是这种types中最普遍的“消费者”function。 任何消耗相关types的值的函数都可以这样写，使得从该types使用的唯一操作是fold和构造函数。 （尽pipe某些函数的折叠版本很难编写和执行，但尝试使用
foldr，(:)和[]来编写tail :: [a] -> [a][]是一个痛苦的练习。
第二点更进一步，因为你甚至不需要构造函数。 您可以实现任何代数types，而不使用data声明或构造函数，只使用折叠：
{-# LANGUAGE RankNTypes #-} -- | A Church-encoded list is a function that takes the two 'foldr' arguments -- and produces a result from them. newtype ChurchList a = ChurchList { runList :: forall r. (a -> r -> r) -- ^ first arg of 'foldr' -> r -- ^ second arg of 'foldr' -> r -- ^ 'foldr' result } -- | Convenience function: make a ChurchList out of a regular list toChurchList :: [a] -> ChurchList a toChurchList xs = ChurchList (\kons knil -> foldr kons knil xs) -- | 'toChurchList' isn't actually needed, however, we can make do without '[]' -- completely. cons :: a -> ChurchList a -> ChurchList a cons x xs = ChurchList (\fz -> fx (runlist xs fz)) nil :: ChurchList a nil = ChurchList (\fz -> z) foldr' :: (a -> r -> r) -> r -> ChurchList a -> r foldr' fz xs = runList xs fz head :: ChurchList a -> Maybe a head = foldr' ((Just .) . const) Nothing append :: ChurchList a -> ChurchList a -> ChurchList a append xs ys = foldr' cons ys xs -- | Convert a 'ChurchList' to a regular list. fromChurchList :: ChurchList a -> [a] fromChurchList xs = runList xs (:) []
作为一个练习，你可以尝试以这种方式写其他types（使用RankNTypes扩展 – 读这个 RankNTypes ）。 这种技术被称为教会编码 ，有时在实际编程中很有用 – 例如，GHC使用一种叫做foldr / build fusion的东西来优化列表代码来移除中间列表; 看到这个Haskell Wiki页面 ，并注意build的types：
build :: (forall b. (a -> b -> b) -> b -> b) -> [a] build g = g (:) []
除了newtype ，这和我上面的fromChurchList是一样的。 基本上，GHC用来优化列表处理代码的规则之一是这样的：
-- Don't materialize the list if all we're going to do with it is -- fold it right away: foldr kons knil (fromChurchList xs) ==> runChurchList xs kons knil
通过实现基本的列表function，在内部使用教会编码，积极地引用他们的定义，并将这个规则应用到内联代码中，像map这样的函数的嵌套使用可以融合成一个紧密的循环。
每一次的折叠
我们实际上可以想出一个可以适用于大量不同types的通用折叠概念。 也就是说，我们可以系统地定义列表，树和更多的fold函数。
这种普遍的fold概念对应于他在评论中提到的变形论者@pelotom。
recursiontypes
关键的见解是这些fold函数是在recursiontypes上定义的。 尤其是：
data List a = Cons a (List a) | Nil data Tree a = Branch (Tree a) (Tree a) | Leaf a
这两种types都是明确recursion的 – List Cons格式和Tree格式的Branch案例。
固定点
就像函数一样，我们可以使用固定点来重写这些types。 记住fix的定义：
fix f = f (fix f)
我们实际上可以为types写一些非常相似的东西，除了它必须有一个额外的构造器包装器：
newtype Fix f = Roll (f (Fix f))
就像fix定义函数的固定点一样，这定义了函子的固定点。 我们可以使用这个新的Fixtypes来expression我们所有的recursiontypes。
这允许我们重写Listtypes如下：
data ListContainer a rest = Cons a rest | Nil type List a = Fix (ListContainer a)
本质上， Fix允许我们将ListContainer s嵌套到任意深度。 所以我们可以有：
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的映射是非常自然的：不是明确地recursion，而是使recursion部分变成一个variables。 然后，我们只需使用Fix来适当填充该variables。
我们也可以为Tree编写一个类似的types。
“解开”固定点
那为什么我们在乎呢？ 我们可以为使用Fix编写的任意types定义fold 。 尤其是：
fold :: Functor f => (fa -> a) -> (Fix f -> a) fold h = h . fmap (fold h) . unRoll where unRoll (Roll a) = a
本质上，折叠所做的每次都是展开“滚动”types的一个图层，每次对结果应用一个函数。 这个“展开”让我们为任何recursiontypes定义一个折叠，并且整齐自然地概括这个概念。
对于列表示例，它的工作原理是这样的：
- 在每一步，我们解开
Roll来得到一个Cons或Nil - 我们使用
fmap对列表的其余部分进行recursion。- 在
Nil情况下，fmap (fold h) Nil = Nil，所以我们只返回Nil。 - 在
Cons情况下，fmap只是继续在列表的其余部分。
- 在
- 最后，我们得到一堆嵌套的调用，以
fold结束，就像标准的foldr。
比较types
现在让我们看看两个折叠函数的types。 首先，
foldr :: (a -> b -> b) -> b -> [a] -> b
现在，专用于ListContainer ：
fold :: (ListContainer ab -> b) -> (Fix (ListContainer a) -> b)
起初，这些看起来完全不同。 但是，通过一些按摩，我们可以看出它们是一样的。 foldr的前两个参数是a -> b -> b和b 。 我们有一个function和一个常数。 我们可以把b看作() -> b 。 现在我们有两个函数_ -> b ，其中_是()和a -> b 。 为了让生活更简单，让我们来看看给予我们的第二个函数(a, b) -> b 。 现在我们可以把它们写成一个单独的函数：
Either (a, b) () -> b
这是真的，因为给定f :: a -> c和g :: b -> c ，我们总是可以写如下：
h :: Either ab -> c h (Left a) = fa h (Right b) = gb
所以现在我们可以把foldr看成是：
foldr :: (Either (a, b) () -> b) -> ([a] -> b)
（我们总是可以随意添加括号->只要他们是正确联合的就可以。
现在让我们看看ListContainer 。 这种types有两种情况： Nil ，没有信息和Cons ，既有a又有b 。 换句话说， Nil就像() ， Cons就像(a, b) ，所以我们可以这样写：
type ListContainer a rest = Either (a, rest) ()
显然这和我在上面使用的一样。 所以现在我们有：
foldr :: (Either (a, b) () -> b) -> ([a] -> b) fold :: (Either (a, b) () -> b) -> (List a -> b)
所以，实际上，这些types是同构的 – 只是写同一个东西的不同方式！ 我觉得这很酷。
（作为一个侧面说明，如果你想知道更多关于这种types的推理，看看代数数据types的代数 ，一个很好的系列博客文章关于这一点。）
回树
所以，我们已经看到了我们如何定义一个types为固定点的genericsfold 。 我们也看到了这是如何直接对应于列表的。 现在让我们看看你的第二个例子，二叉树。 我们有这样的types：
data Tree a = Branch a (Tree a) (Tree a) | Leaf a
我们可以按照上面的规则使用Fix来重写：我们用一个typesvariablesreplacerecursion部分：
data TreeContainer a rest = Branch rest rest | Leaf a type Tree a = Fix (TreeContainer a)
现在我们有一个树fold ：
fold :: (TreeContainer ab -> 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 ab 。 树容器有两种情况： Branch ，包含两个b和Leaf ，包含一个a 。
所以这些折叠types与列表示例是同构的。
泛化
有一个清晰的模式出现。 给定一个正常的recursion数据types，我们可以系统地创build一个types的非recursion版本，让我们把types表示为一个函数的一个固定点。 这意味着我们可以机械地为所有这些不同的types提供fold函数 – 事实上，我们可以使用GHCgenerics或类似的东西来自动化整个过程。
从某种意义上说，这意味着我们对于不同的types并没有真正的foldfunction。 相反，我们有一个非常多态的单一fold函数。
更多
我首先从Conal Elliott 的讲话中完全理解了这些想法。 这更详细，也谈到unfold ，这是双fold 。
如果您想更深入地研究这类事情，请阅读“香蕉，镜头，信封和带刺线function编程”一文 。 除此之外，这引入了与变形和展开相对应的“变形”和“变形”的概念。
代数（和Coalgebras）
另外，我无法拒绝为自己添加一个插件：P。 你可以看到我们在这里使用的方式和我在另一个SO答案中谈论代数时使用它的方式之间的一些有趣的相似之处。
事实上， fold和代数之间有着深刻的联系。 此外， unfold – fold上述双重 – 连接到代数的双重余代数。 重要的思想是，代数数据types对应于“初始代数”，它也定义了折叠，如我的答案的其余部分所述。
您可以在一般types的fold看到这个连接：
fold :: Functor f => (fa -> a) -> (Fix f -> a)
fa -> a术语看起来很熟悉！ 请记住，一个f-代数被定义为如下的东西：
class Functor f => Algebra fa where op :: fa -> a
所以我们可以把fold看作是：
fold :: Algebra fa => Fix f -> a
本质上， fold只是让我们“概括”使用代数定义的结构。
折叠用一个函数replace每个构造函数。
例如， foldr cons nil将每个(:)与cons和[]replacenil ：
foldr cons nil ((:) 1 ((:) 2 [])) = cons 1 (cons 2 nil)
对于树， foldTree branch leaf用branch和每foldTree branch leafreplace每个branch ：
foldTree branch leaf (Branch (Branch (Leaf 1) (leaf 2)) (Leaf 3)) = branch (branch (leaf 1) (leaf 2)) (leaf 2)
这就是为什么每个fold都接受与构造函数具有完全相同types的参数：
foldr :: (a -> list -> list) -> list -> [a] -> list foldTree :: (tree -> tree -> tree) -> (a -> tree) -> Tree a -> tree
我会把这称为一个折叠，并宣布Tree是Foldable 。 请参阅GHC文档中的Foldable示例 。
