haskell - 什么构成了列表以外类型的折叠？

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

Tikhon 搞定了技术问题。我想我会尽量简化他所说的。

不幸的是，多年来，“折叠”一词变得模棱两可，表示以下两件事之一:

按某种顺序依次减少集合。在 Haskell 中，这就是 Foldable 中“折叠”的含义。类，这是拉斯曼斯提出的。

您要求的概念:根据代数数据类型的结构“破坏”(与构建相反)、“观察”或“消除”代数数据类型。也称为变质。

可以通用地定义这两个概念，以便一个参数化函数能够为各种类型执行此操作。 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不是递归的；我要展示的过程并不假设“折叠”类型是递归的。人们通常不称这种情况为“折叠”，但它确实是同一概念的非递归情况。

第一步:给定类型的折叠将消耗折叠类型并产生一些参数类型作为其结果。我喜欢叫后者 r (对于“结果”)。所以:

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

第二步:除了最后一个参数(结构的参数)之外，折叠接受与类型具有构造函数一样多的参数。 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 = ???

我们知道它需要三个参数，所以我们可以添加变量来反射(reflect)它们。我将使用长描述性名称:

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 .但是当然，我们可以轻松地编写“子折叠”:

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没有所需的属性(property)；例如，如果我们有 foo = Branch 1 (Branch 2 Empty Empty) Empty ，由此可知 mangleBTree Branch Empty foo /= foo .所以 mangleBTree ，虽然它有正确的类型，但不是折叠。

现在，让我们从细节上退后一步，专注于 mangleTree 的最后一点。例子。折叠(在结构意义上，我的答案顶部的 #2)无非是代数类型的最简单、非平凡的函数，这样，当您传入类型的构造函数作为其参数时，它成为该类型的恒等函数。 (非平凡我的意思是像 foo f z xs = xs 这样的东西是不允许的。)

这是非常重要的。我喜欢的思考方式有以下两种:

给定类型的折叠可以“看到”该类型的任何值包含的所有信息。 (这就是为什么它能够使用类型的构造函数从头开始完美地“重​​构”该类型的任何值。)

折叠是该类型最通用的“消费者”功能。任何使用所讨论类型的值的函数都可以被编写，以便它从该类型使用的唯一操作是折叠和构造函数。 (尽管某些函数的 fold-only 版本难以编写且性能不佳；尝试将 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 扩展名— read this for a primer)。这种技术被称为 Church encoding ，有时在实际编程中很有用——例如，GHC 使用名为 foldr 的东西。/ build融合优化列表代码以删除中间列表；见 this Haskell Wiki page ，并注意 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 之类的函数。可以融合成一个紧密的循环。