Haskell/Foldable

Foldable 类型类提供对列表折叠 (foldr 及其朋友) 的泛化，以及从它派生到任意数据结构的操作。除了非常有用之外，Foldable 是一个很好的例子，说明 monoid 如何帮助制定良好的抽象。

解构 foldr

本段将介绍 foldMap 作为 foldr 的替代。我们将展示如何用前者实现后者。foldr 是一个非常繁忙的函数 - 在第一个函数箭头两侧有 2 个二元函数，它们类型都使用 2 个变量。

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

如果我们要泛化 foldr，那么使用更简单的东西来处理，或者至少能够将其分解成更简单的组件，会比较方便。这些组件会是什么呢？

对列表折叠的一个粗略描述是，它包括遍历列表元素，并将它们与一个二元函数组合起来。我们碰巧知道一个类型类，它完全是关于组合成对的值：Monoid。如果我们取 foldr f z ...

a `f` (b `f` (c `f` z)) -- foldr f z [a,b,c]

... 并使 f = (<>) 和 z = mempty ...

a <> (b <> (c <> mempty)) -- foldr (<>) mempty [a,b,c]

... 我们得到 mconcat = foldr mappend mempty，它是一个更简单、更专业的 foldr，我们不需要指定组合函数或初始累加器，因为我们只使用 mappend（即 (<>)）和 mempty。

mconcat :: Monoid m => [m] -> m

mconcat 足够好地捕捉了 foldr 的组合所有元素方面，并且涵盖了它的几个用例。

GHCi> mconcat ["Tree", "fingers"] -- concat
"Treefingers"

很不错 - 但我们肯定不想只限于使用 Monoid 实例来折叠。改进这种情况的一种方法是意识到我们可以使用 mconcat 来折叠具有任何类型元素的列表，只要我们有一个函数将它们转换为某些 Monoid 类型。

foldMap :: Monoid m => (a -> m) -> [a] -> m
foldMap g = mconcat . fmap g

这已经让事情变得更有意思了。

GHCi> foldMap Sum [1..10]
Sum {getSum = 55}

到目前为止一切顺利，但似乎我们仍然无法使用任意的组合函数来折叠。然而，事实证明，任何 适合 foldr 签名的二元函数都可以用来将值转换为 Monoid 类型！诀窍是将传递给 foldr 的组合函数看作是单个参数的函数...

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

... 并利用 b -> b 函数在组合下形成 monoid 的事实，以 (.) 作为 mappend，以 id 作为 mempty 。相应的 Monoid 实例可以通过 Data.Monoid 中的 Endo 包装器获得 。

newtype Endo b = Endo { appEndo :: b -> b }

instance Monoid Endo where
    mempty                  = Endo id
    Endo g `mappend` Endo f = Endo (g . f)

我们现在可以定义...

foldComposing :: (a -> (b -> b)) -> [a] -> Endo b
foldComposing f = foldMap (Endo . f)

... 它从每个元素创建一个 b -> b 函数，并将它们全部组合起来。

Endo (f a) <> (Endo (f b) <> (Endo (f c) <> (Endo id))) -- foldComposing f [a,b,c]
Endo (f a . (f b . (f c . id))) 
-- (<>) and (.) are associative, so we don't actually need the parentheses.

-- As an example, here is a step-by-step evaluation:
foldComposing (+) [1, 2, 3]
foldMap (Endo . (+)) [1, 2, 3]
mconcat (fmap (Endo . (+)) [1, 2, 3]) 
mconcat (fmap Endo [(+1), (+2), (+3)])
mconcat [Endo (+1), Endo (+2), Endo (+3)]
Endo ((+1) . (+2) . (+3))
Endo (+6)

如果我们将该函数应用于某个 b 值...

foldr :: (a -> (b -> b)) -> b -> [a] -> b
foldr f z xs = appEndo (foldComposing f xs) z

... 我们最终会恢复 foldr。这意味着我们可以用 foldMap 来定义 foldr，foldMap 是一个更简单，因此更容易推理的函数。因此，foldMap 是 Foldable 的概念核心，Foldable 类将 foldr 泛化到任意数据结构。

练习
为列表编写 foldMap 的两种实现：一种用 foldr 实现，另一种用显式递归实现。

Foldable 类

为数据结构实现 Foldable 需要编写一个函数：foldMap 或 foldr。但是，Foldable 还有很多其他方法。

-- Abridged definition, with just the method signatures.
class Foldable t where
    foldMap :: Monoid m => (a -> m) -> t a -> m
    foldr :: (a -> b -> b) -> b -> t a -> b

    -- All of the following have default implementations:
    fold :: Monoid m => t m -> m -- generalised mconcat
    foldr' :: (a -> b -> b) -> b -> t a -> b
    foldl :: (b -> a -> b) -> b -> t a -> b
    foldl' :: (b -> a -> b) -> b -> t a -> b
    foldr1 :: (a -> a -> a) -> t a -> a
    foldl1 :: (a -> a -> a) -> t a -> a
    toList :: t a -> [a]
    null :: t a -> Bool
    length :: t a -> Int
    elem :: Eq a => a -> t a -> Bool
    maximum :: Ord a => t a -> a
    minimum :: Ord a => t a -> a
    sum :: Num a => t a -> a
    product :: Num a => t a -> a

这些额外的方法存在是为了在必要时可以编写更有效的实现。无论如何，只编写 foldMap 或 foldr 就能让你免费获得上面列出的所有非常有用的函数。更棒的是：Data.Foldable 提供了更多泛化到任何 Foldable 的函数，包括，令人惊讶的是，mapM_/traverse_。

以下是如何使用 Data.Map 快速演示 Foldable。

GHCi> import qualified Data.Map as M
GHCi> let testMap = M.fromList $ zip [0..] ["Yesterday","I","woke","up","sucking","a","lemon"]
GHCi> length testMap 
7
GHCi> sum . fmap length $ testMap 
29
GHCi> elem "lemon" testMap 
True
GHCi> foldr1 (\x y -> x ++ (' ' : y)) testMap -- Be careful: foldr1 is partial!
"Yesterday I woke up sucking a lemon"
GHCi> import Data.Foldable
GHCi> traverse_ putStrLn testMap 
Yesterday
I
woke
up
sucking
a
lemon

除了提供有用的泛化之外，Foldable 和 foldMap 还建议了一种更声明性的思考折叠的方式。例如，我们可以说，sum 并不是一个遍历列表（或树，或任何数据结构）并使用 (+) 累积其元素的函数，而是它查询每个元素的值，并使用 Sum monoid 汇总查询结果。虽然差异可能很小，但 monoidal 摘要观点可以通过将我们希望获得的结果类型从被折叠的数据结构的细节中分离出来，帮助澄清涉及折叠的问题。

练习

让我们玩“找出 Monoid”游戏！以下是规则： 对于每个函数，建议一个 mempty、mappend 和（如果需要）一个函数来准备值，这将使它能够使用 fold 或 foldMap 来实现。不需要为 newtype 实例费心（除非你希望使用 foldMap 来测试你的解决方案，当然）- 例如，"mempty 是 0，mappend 是 (+)" 将是 sum 的一个完全可以接受的答案。如果有必要，你可以部分应用函数并在答案中使用提供的参数。不要用 id 和 (.) 来回答所有问题 - 那样就作弊了！ （提示：如果你需要建议，请查看 Data.Monoid 中的 Monoid 实例。） product :: (Foldable t, Num a) => t a -> a concat :: Foldable t => t [a] -> [a] concatMap :: Foldable t => (a -> [b]) -> t a -> [b] all :: Foldable t => (a -> Bool) -> t a -> Bool elem :: (Foldable t, Eq a) => a -> t a -> Bool length :: Foldable t => t a -> Int traverse_ :: (Foldable t, Applicative f) => ‌(a -> f b) -> t a -> f () mapM_ :: (Foldable t, Monad m) => ‌(a -> m b) -> t a -> m () safeMaximum :: (Foldable t, Ord a) => t a -> Maybe a （类似于 maximum，但处理空情况。） find :: Foldable t => (a -> Bool) -> t a -> Maybe a composeL :: Foldable t => ‌(b -> a -> b) -> t a -> b -> b (等同于 foldl.)

列表式折叠

Foldable 包含 toList :: Foldable t => t a -> [a] 方法。这意味着任何 Foldable 数据结构都可以转换为列表；此外，折叠生成的列表将产生与直接折叠原始结构相同的结果。根据 foldMap 可能的 toList 实现将是

toList = foldMap (\x -> [x])

toList 反映了这样一个事实，即列表是 Haskell 类型中的 **自由幺半群**。“自由”在这里意味着任何值都可以提升到幺半群，既不添加也不删除任何信息（我们可以将类型为 a 的值转换为具有单个元素的 [a] 列表，并通过 (\x->[x]) 和 head 以无损方式返回）。

toList 突出显示了 Foldable 的一个相关关键特征。由于列表的 toList = id，如果您给定一个定义为... 的函数

-- Given a list xs :: [a] 
xsAsFoldMap :: Monoid m => (a -> m) -> m
xsAsFoldMap = \f -> foldMap f xs

... 始终可以通过向 xsAsFoldMap 提供 (\x->[x]) 来恢复原始列表 xs。从这个意义上讲，**列表等同于其右折叠**。这意味着如果数据结构比列表更复杂，则使用 Foldable 操作进行折叠将不可避免地成为一种有损操作。换句话说，我们可以说 Foldable 提供的列表式折叠不如我们之前在 其他数据结构 中看到的折叠（正式称为 **范畴同态**）通用，后者确实可以重建原始结构。

练习
此练习涉及我们在 其他数据结构 中使用的树类型 data Tree a = Leaf a | Branch (Tree a) (Tree a) 为 Tree 写一个 Foldable 实例。 实现 treeDepth :: Tree a -> Int，它给出从树根到最远叶子的分支数量。使用 Foldable 或 其他数据结构 中定义的 treeFold 范畴同态。这两个建议是否实际上都可行？

关于 Foldable 的更多事实

Foldable 在 Haskell 类中稍微不同寻常，这些类既有原则性又通用，因为它本身没有自己的规律。最接近的是以下属性，严格来说这不是一个规律（因为它保证在无论实例是什么的情况下都成立）：给定一个 幺半群同态 g，

foldMap (g . f) = g . foldMap f

从 foldMap (g . f) 切换到 g . foldMap f 可能是有利的，因为它意味着仅对折叠的结果应用 g，而不是对正在折叠的结构中的可能许多元素应用 g。

如果 Foldable 结构也是 Functor，则它还自动成立...

foldMap f = fold . fmap f

... 因此我们得到，在应用 第二个函子定律 和上面的属性之后

foldMap g . fmap f = foldMap (g . f) = g . foldMap f

尽管存在 foldMap 这样的方法可能表明任何 Foldable 类型也应该具有 Functor 实例，但 Functor 实际上不是 Foldable 的超类。这使得为结构提供 Foldable 实例成为可能，这些结构由于某种原因不能是 Functor。最常见的例子是 集合 来自 Data.Set。这些集合的元素类型必须是 Ord 的实例，因此它们的 map 函数不能用作 fmap，后者没有额外的类约束。但是，这并不否认 Data.Set.Set 一个有用的 Foldable 实例。

GHCi> import qualified Data.Set as S
GHCi> let testSet = S.fromList [1,3,2,5,5,0]
GHCi> testSet 
fromList [0,1,2,3,5]
GHCi> import Data.Foldable
GHCi> toList testSet
[0,1,2,3,5]
GHCi> foldMap show testSet 
"01235"

练习
编写对对的幺半群实例， (Monoid a, Monoid b) => Monoid (a,b) 证明 fst 和 snd 是幺半群同态。 使用上面介绍的 foldMap 的幺半群同态属性证明 foldMap f &&& foldMap g = foldMap (f &&& g) 其中 f &&& g = \x -> (f x, g x) 此练习基于 Edward Kmett 的一条消息 。