什么构成除列表以外的类型的折叠？

Question

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

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

定义折叠函数是很自然的

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

从某种意义上说,reduce f x0替代每一个Node有f一位End用x0.这就是Prelude所说的折叠.

现在考虑一个简单的二叉树:

data Tree x = Leaf x | Branch (Tree x) (Tree x)

定义诸如的函数同样很自然

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

请注意,这种减少具有完全不同的特征; 而基于列表的一个本质上是顺序的,这个新的基于树的一个具有更多的分而治之的感觉.你甚至可以想象par在那里扔几个组合器.(你会在列表版本中放置这样的东西？)

我的问题:这个功能是否仍被归类为"折叠",还是其他东西？(如果是的话,它是什么？)

基本上每当有人谈论折叠时,他们总是谈论折叠列表,这本质上是顺序的.我想知道"顺序"是否是折叠定义的一部分,或者这是否仅仅是最常用的折叠示例的巧合属性.

Answer 1

适合各种场合

我们实际上可以提出一种折叠的通用概念,它可以应用于一大堆不同类型.也就是说,我们可以系统地定义fold列表,树等功能.

这个通用概念fold对应于他的评论中提到的catamorphisms @pelotom.

递归类型

关键的见解是这些fold函数是在递归类型上定义的.特别是:

data List a = Cons a (List a) | Nil
data Tree a = Branch (Tree a) (Tree a) | Leaf a

这两种类型都明确recursive-- 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

我认为映射是非常自然的:我们将递归部分ListContainer变为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

基本上,所有折叠都是一次打开"滚动"类型一层,每次都将结果应用于结果.这种"展开"让我们为任何递归类型定义折叠,并巧妙地自然地概括了这个概念.

对于列表示例,它的工作方式如下:

1. 在每一步,我们打开Roll以获得a Cons或aNil
2. 我们使用在列表的其余部分进行递归fmap.
   1. 在这种Nil情况下,fmap (fold h) Nil = Nil我们就这样回来Nil.
   2. 在这种Cons情况下,fmap只是继续折叠列表的其余部分.
3. 最后,我们得到了一堆嵌套调用,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.现在我们有两个功能_ -> 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.树容器有两种情况:Branch包含两个bs Leaf,包含一个a.

所以这些折叠类型与列表示例一样是同构的.

泛化

有一个明显的模式出现.给定一个正常的递归数据类型,我们可以系统地创建该类型的非递归版本,这使我们可以将类型表示为仿函数的固定点.这意味着我们可以机械地fold为所有这些不同的类型提供函数 - 事实上,我们可以使用GHC Generics或类似的东西自动化整个过程.

从某种意义上说,这意味着我们并没有fold为不同类型提供不同的功能.相反,我们有一个非常多态的单一fold函数.

更多

我首先从Conal Elliott 的演讲中充分理解了这些想法.这更详细,也谈到unfold,这是双重的fold.

如果您想深入到这样的事情甚至更加深刻,读了梦幻般的论文"用香蕉,镜头,信封和铁丝网的函数编程".除其他事项外,这引入了"catamorphisms"和"anamorphisms",其对应于折叠和展开的概念.

代数(和代数)

另外,我无法抗拒为自己添加插头:P.你可以看到,我们使用的方式之间的一些有趣的相似之处Either这里谈论,当我用它的方式代数在另一个SO回答.

事实上fold,代数和代数之间存在着深刻的联系; 此外,unfold- 前面提到的双重 - fold与代数相关,这是代数的对偶.重要的想法是代数数据类型对应于"初始代数",它也定义了我在其余答案中概述的折叠.

您可以在以下常规类型中看到此连接fold:

fold :: Functor f => (f a -> a) -> (Fix f -> a)

这个f a -> a词看起来很熟悉!请记住f-algebra被定义为:

class Functor f => Algebra f a where
  op :: f a -> a

所以我们可以想到fold:

fold :: Algebra f a => Fix f -> a

基本上,fold只是让我们"总结"使用代数定义的结构.

Answer 2

Tikhon得到了技术上的东西.我想我会尽量简化他所说的话.

不幸的是,"折叠"一词多年来变得含糊不清,意思是两件事之一:

1. 按顺序依次减少集合.在Haskell中,这就是Foldable课堂上"折叠"的意思,larsmans提出了这个意义.
2. 你要求的概念:"破坏"(与构造相反),根据其结构"观察"或"消除"代数数据类型.也称为catamorphism.

可以一般地定义这两个概念,以便一个参数化函数能够为各种类型执行它.Tikhon在第二种情况下展示了如何做.

但是大多数情况下通常都是这样,Fix代数等都是过度的.让我们找出一种更简单的方法来为任何代数数据类型编写折叠.我们将使用Maybe,对,列表和树作为示例:

data Maybe a = Nothing | Just a
data Pair a b = Pair a b
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不是递归的; 我要展示的程序并不假设"fold"类型是递归的.人们通常不会将此案称为"折叠",但它实际上是同一概念的非递归情况.

第一步:给定类型的折叠将使用折叠类型并生成一些参数类型作为其结果.我喜欢称后者r("结果").所以:

foldMaybe :: ... -> Maybe a -> r
foldPair  :: ... -> Pair a b -> r
foldList  :: ... -> List a -> r
foldTree  :: ... -> Tree a -> r
foldBTree :: ... -> BTree a -> r

第二步:除了最后一个参数(结构的参数)之外,fold还使用与类型具有构造函数一样多的参数. Pair有一个构造函数,我们的其他示例有两个,所以:

foldMaybe :: nothing -> just -> Maybe a -> r
foldPair  :: pair -> Pair a b -> r 
foldList  :: nil -> cons -> List a -> r
foldTree  :: leaf -> branch -> Tree a -> r
foldBTree :: empty -> node -> BTree a -> r

第三步:每个参数与它对应的构造函数具有相同的元素.让我们将构造函数视为函数,并写出它们的类型(确保类型变量与我们正在编写的签名中的类型变量匹配):

Nothing :: Maybe a
Just    :: a -> Maybe a

Pair    :: a -> b -> Pair a b

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步:在每个构造函数的签名中,我们将使用我们的类型变量r(我们在折叠签名中使用)替换它构造的所有数据类型:

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

如您所见,我已经从第二步"将"结果签名"分配"到我的虚拟类型变量中.现在步骤5:填入早期的草图折叠签名:

foldMaybe :: r -> (a -> r) -> Maybe a -> r
foldPair  :: (a -> b -> r) -> Pair a b -> 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

现在,这些是这些类型的折叠的签名.它们有一个有趣的参数顺序,因为我通过从data声明和构造函数类型中读取折叠类型来机械地完成此操作,但由于某些原因,在函数式编程中,将基本情况首先放在data定义中,然后在定义中首先放置递归案例处理程序fold.没问题!让我们重新调整他们,让他们更传统:

foldMaybe :: (a -> r) -> r -> Maybe a -> r
foldPair  :: (a -> b -> r) -> Pair a b -> 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

定义也可以机械填写.让我们foldBTree一步一步地选择并实施它.给定类型的折叠是我们发现满足这种条件的类型的一个函数:使用类型的构造函数进行折叠是该类型的标识函数(您得到的结果与您开始的值相同).

我们将这样开始:

foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r
foldBTree = ???

我们知道它需要三个参数,所以我们可以添加变量来反映它们.我将使用长描述性名称:

foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r
foldBTree branch empty tree = ???

看一下这个data声明,我们知道BTree有两个可能的构造函数.我们可以将定义拆分为每个的大小写,并为其元素填写变量:

foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r
foldBTree branch empty Empty = ???
foldBTree branch empty (Branch a l r) = ???
    -- Let's use comments to keep track of the types:
    -- a :: a
    -- l, r :: BTree a

现在,没有类似的东西undefined,填写第一个等式的唯一方法是empty:

foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r
foldBTree branch empty Empty = empty
foldBTree branch empty (Branch a l r) = ???
    -- 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 a l r) = branch a (subfold l) (subfold r)
    where subfold = foldBTree branch empty

这是折叠BTree,因为foldBTree Branch Empty anyTree == anyTree.请注意,这foldBTree不是此类型的唯一功能; 还有这个:

mangleBTree :: (a -> r -> r -> r) -> r -> BTree a -> r
mangleBTree branch empty Empty = empty
mangleBTree branch empty (Branch a l r) = 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,虽然它有正确的类型,但不是折叠.

现在,让我们从细节中退一步,并通过mangleTree示例专注于最后一点.折叠(在结构意义上,在我的答案的顶部#2)只不过是代数类型的最简单,非平凡的函数,当你将类型的构造函数作为参数传递时,它成为该类型的身份函数.(非常重要,我的意思foo f z xs = xs是不允许这样的事情.)

这非常重要.我想考虑的两种方式如下:

1. 给定类型的折叠可以"看到"该类型的任何值包含的所有信息.(这就是为什么它能够使用类型的构造函数从头开始完美地"重​​建"该类型的任何值.)
2. 折叠是该类型的最普遍的"消费者"功能.可以编写任何消耗有关类型值的函数,以便它从该类型中使用的唯一操作是fold和构造函数.(虽然某些功能的唯一折叠版本是难以编写,表现不佳;尝试写tail :: [a] -> [a]有foldr,(:)和[].作为一个痛苦的锻炼)

第二点更进一步,因为你甚至不需要构造函数.您可以在不使用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 (\f z -> f x (runlist xs f z))

nil :: ChurchList a
nil = ChurchList (\f z -> z)

foldr' :: (a -> r -> r) -> r -> ChurchList a -> r
foldr' f z xs = runList xs f z

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 (:) []

作为练习,您可以尝试以这种方式编写其他类型(使用RankNTypes扩展名 - 阅读本文作为入门读物).这种技术称为Church编码,有时在实际编程中很有用 - 例如,GHC使用称为foldr/ buildfusion的东西来优化列表代码以删除中间列表; 看到这个Haskell Wiki页面,并注意以下类型build:

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

通过实现基本列表函数以在内部使用Church编码,积极地内联其定义,并将此规则应用于内联代码,map可以将函数的嵌套使用融合到紧密循环中.

Answer 3

折叠用函数替换每个构造函数.

例如,foldr cons nil替代每一个(:)具有cons和[]用nil:

foldr cons nil ((:) 1 ((:) 2 [])) = cons 1 (cons 2 nil)

对于一棵树,foldTree branch leaf替代每一个Branch有branch一位Leaf有leaf:

foldTree branch leaf (Branch (Branch (Leaf 1) (Leaf 2)) (Leaf 3))
    = branch (branch (leaf 1) (leaf 2)) (leaf 2)

这就是为什么每个fold都接受与构造函数具有完全相同类型的参数:

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

foldTree :: (tree -> tree -> tree) -> (a -> tree) -> Tree a -> tree

Answer 4

我称之为折叠,并宣布Tree一个Foldable.请参阅FoldableGHC文档中的示例.