什么构成了除列表之外的types的折叠?

考虑一个单链表。 它看起来像

data List x = Node x (List x) | End 

定义折叠函数是很自然的

 reduce :: (x -> y -> y) -> y -> List x -> y 

从某种意义上说, reduce f x0reduce f x0代替每个Nodereduce 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的技术水平下降了 我想我会尽量简化他所说的话。

不幸的是,“折叠”一词多年来变得模棱两可,意味着两件事之一:

  1. 按顺序依次减less集合。 在Haskell中,这就是“折叠”在Foldable类中的意义,这是larsmans带来的。
  2. 你所要求的概念是:根据结构 “破坏”(与构造相反),“观察”或“消除”代数数据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这样的东西是不允许的)

这是非常重要的。 我喜欢想两个方法如下:

  1. 给定types的折叠可以“查看”该types的任何值所包含的所有信息。 (这就是为什么它能够使用types的构造函数完全“重构”该types的任何值)。
  2. 折叠是这种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 

我认为从ListContainerList的映射是非常自然的:不是明确地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定义一个折叠,并且整齐自然地概括这个概念。

对于列表示例,它的工作原理是这样的:

  1. 在每一步,我们解开Roll来得到一个ConsNil
  2. 我们使用fmap对列表的其余部分进行recursion。
    1. Nil情况下, fmap (fold h) Nil = Nil ,所以我们只返回Nil
    2. Cons情况下, fmap只是继续在列表的其余部分。
  3. 最后,我们得到一堆嵌套的调用,以fold结束,就像标准的foldr

比较types

现在让我们看看两个折叠函数的types。 首先,

 foldr :: (a -> b -> b) -> b -> [a] -> b 

现在,专用于ListContainer

 fold :: (ListContainer ab -> b) -> (Fix (ListContainer a) -> b) 

起初,这些看起来完全不同。 但是,通过一些按摩,我们可以看出它们是一样的。 foldr的前两个参数是a -> b -> bb 。 我们有一个function和一个常数。 我们可以把b看作() -> b 。 现在我们有两个函数_ -> b ,其中_()a -> b 。 为了让生活更简单,让我们来看看给予我们的第二个函数(a, b) -> b 。 现在我们可以把它们写成一个单独的函数:

 Either (a, b) () -> b 

这是真的,因为给定f :: a -> cg :: 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 ,包含两个bLeaf ,包含一个a

所以这些折叠types与列表示例是同构的。

泛化

有一个清晰的模式出现。 给定一个正常的recursion数据types,我们可以系统地创build一个types的非recursion版本,让我们把types表示为一个函数的一个固定点。 这意味着我们可以机械地为所有这些不同的types提供fold函数 – 事实上,我们可以使用GHCgenerics或类似的东西来自动化整个过程。

从某种意义上说,这意味着我们对于不同的types并没有真正的foldfunction。 相反,我们有一个非常多态的单一fold函数。

更多

我首先从Conal Elliott 的讲话中完全理解了这些想法。 这更详细,也谈到unfold ,这是双fold

如果您想更深入地研究这类事情,请阅读“香蕉,镜头,信封和带刺线function编程”一文 。 除此之外,这引入了与变形和展开相对应的“变形”和“变形”的概念。

代数(和Coalgebras)

另外,我无法拒绝为自己添加一个插件:P。 你可以看到我们在这里使用的方式和我在另一个SO答案中谈论代数时使用它的方式之间的一些有趣的相似之处。

事实上, fold和代数之间有着深刻的联系。 此外, unfoldfold上述双重 – 连接到代数的双重余代数。 重要的思想是,代数数据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 leafbranch和每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 

我会把这称为一个折叠,并宣布TreeFoldable 。 请参阅GHC文档中的Foldable示例 。