第 14 章：Foldable 及相关抽象（Foldables and friends）
原文：Graham Hutton, Programming in Haskell, Second Edition, Chapter 14。维护者已确认本书可翻译并发布用于学习研究。
本章介绍三种处理数据结构中值的常见模式。我们从幺半群开始，它捕获了使用结合运算符组合值的思想；然后讨论 Foldable，它把列表折叠的概念推广到一系列参数化类型；最后以 Traversable 收尾，它进一步推广了映射这一概念。
14.1 幺半群（Monoids）
在数学中，幺半群是一个集合，加上一个把集合中两个元素组合起来的结合运算符，以及这个运算符的单位元。例如，整数集合在加法运算下构成幺半群，其单位元是零。在 Haskell 中，幺半群概念由下面的内置类声明捕获：
class Monoid a where
mempty :: a
mappend :: a -> a -> a
mconcat :: [a] -> a
mconcat = foldr mappend mempty
也就是说，要让类型 a 成为 Monoid 类的实例，它必须支持指定类型的值 mempty 和函数 mappend，二者分别扮演幺半群单位元和运算符的角色。在实践中，函数 mappend 经常通过把名字放在反引号中写成中缀运算符，例如 x mappend y。
除了两个原语之外，上面的类还提供函数 mconcat，用于组合一个列表中的幺半群值。它的默认定义会把列表中的每个 cons 替换为 mappend，把空列表替换为 mempty。例如，把 mconcat 应用于形如 [x,y,z] 的列表，会得到：
x `mappend` (y `mappend` (z `mappend` mempty))
与数学中一样，Monoid 类中的两个原语要求满足下面的单位律和结合律：
mempty `mappend` x = x
x `mappend` mempty = x
x `mappend` (y `mappend` z) = (x `mappend` y) `mappend` z
例如，使用这些定律，mconcat [x,y,z] 的结果可以更简单地写成下面这样，不需要括号或 mempty，因为幺半群定律确保它们不会影响结果：
x `mappend` y `mappend` z
未来某个时候，Haskell 中的 Monoid 类可能会被拆分为两个独立的类，一个提供结合运算符，另一个提供单位元。如果这个变化被实现，所需的任何调整都会在本书网站上说明。
示例
库 Data.Monoid 提供了许多标准幺半群。最简单的例子是列表幺半群，其中 mempty 和 mappend 分别由空列表和列表追加运算符给出：
instance Monoid [a] where
-- mempty :: [a]
mempty = []
-- mappend :: [a] -> [a] -> [a]
mappend = (++)
方法名 mempty 和 mappend 的灵感来自这个实例，但这样的命名并不理想，因为一般来说，幺半群原语并不一定对应空值，也不一定提供追加值的方式。唯一需要的是两个满足幺半群定律的原语。
第二个例子中，类型 Maybe a 也可以做成幺半群，前提是参数类型 a 是幺半群：
instance Monoid a => Monoid (Maybe a) where
-- mempty :: Maybe a
mempty = Nothing
-- mappend :: Maybe a -> Maybe a -> Maybe a
Nothing `mappend` my = my
mx `mappend` Nothing = mx
Just x `mappend` Just y = Just (x `mappend` y)
也就是说，mempty 由失败值 Nothing 给出，而 mappend 会组合两个可能失败的参数的结果。在后一种情况下，如果任意一个参数失败，就返回另一个参数；如果两个参数都成功，就使用参数类型 a 的 mappend 组合两个结果值。
某个具体类型可能以多种不同方式产生幺半群。例如，我们已经看到整数在加法下构成幺半群，因此可以声明下面这个简单实例：
instance Monoid Int where
-- mempty :: Int
mempty = 0
-- mappend :: Int -> Int -> Int
mappend = (+)
整数在乘法下也构成幺半群，其单位元是一，因此也可以声明：
instance Monoid Int where
-- mempty :: Int
mempty = 1
-- mappend :: Int -> Int -> Int
mappend = (*)
不过，Haskell 不允许同一个类型为同一个类声明多个实例，因此试图以这种方式为 Monoid Int 声明两个独立实例会产生错误。解决方案是为两个实例分别引入专用包装类型。
对于加法，幺半群库声明了一个新类型 Sum a，带有一个同样名为 Sum 的哑构造子，该构造子接收一个类型为 a 的参数，并提供一个移除构造子的函数：
newtype Sum a = Sum a
deriving (Eq, Ord, Show, Read)
getSum :: Sum a -> a
getSum (Sum x) = x
上面的 deriving 子句确保类型 Sum a 的值支持标准相等和排序运算符，并且可以在字符串之间转换。现在，对于任何数值类型的参数类型 a（例如 Int），可以把类型 Sum a 做成幺半群：把 mempty 取为值 Sum 0，并把 mappend 取为类型 Sum a 的值上的加法运算符：
instance Num a => Monoid (Sum a) where
-- mempty :: Sum a
mempty = Sum 0
-- mappend :: Sum a -> Sum a -> Sum a
Sum x `mappend` Sum y = Sum (x+y)
例如，使用这个实例有：
> mconcat [Sum 2, Sum 3, Sum 4]
Sum 9
如果希望在 GHCi 中尝试这类例子，必须先输入 import Data.Monoid 加载幺半群库。特别是，把 Sum 应用到列表中的每个数字，可以确保 mconcat 使用求和的幺半群。下一节会看到如何简化这类包装器的使用。
类似地，对于数字乘法，幺半群库使用与加法相同的方法声明了一个新类型 Product a：
newtype Product a = Product a
deriving (Eq, Ord, Show, Read)
getProduct :: Product a -> a
getProduct (Product x) = x
随后，可以用适合乘法的方式定义两个原语，把类型 Product a 做成 Monoid 类的实例：
instance Num a => Monoid (Product a) where
-- mempty :: Product a
mempty = Product 1
-- mappend :: Product a -> Product a -> Product a
Product x `mappend` Product y = Product (x*y)
例如：
> mconcat [Product 2, Product 3, Product 4]
Product 24
以类似方式，逻辑值类型在逻辑与和逻辑或下都构成幺半群。为此，幺半群库为 Bool 提供了名为 All 和 Any 的包装类型，细节见附录 B。例如，对于 All，函数 mconcat 会判断列表中的所有逻辑值是否都为 True；对于 Any，则判断是否存在这样的值为 True：
> mconcat [All True, All True, All True]
All True
> mconcat [Any False, Any False, Any False]
Any False
本节最后注意，库还提供了 mappend 的中缀版本，定义为 x <> y = x mappend y，它允许幺半群表达式写得更简洁，例如 x <> y <> z。这个运算符经常在实际应用中使用，但出于说明目的，本章更倾向于直接使用原语 mappend。
14.2 Foldable
Haskell 中幺半群的主要应用之一，是把数据结构中的所有值组合成单个值。例如，对列表来说，可以如下定义一个函数 fold 来实现这个思想：
fold :: Monoid a => [a] -> a
fold [] = mempty
fold (x:xs) = x `mappend` fold xs
也就是说，把 fold 应用于空列表会得到幺半群的单位元 mempty；对于非空列表，则使用幺半群运算符 mappend 把列表头部与递归处理尾部的结果组合起来。例如，把 fold 应用于形如 [x,y,z] 的列表，会得到：
x `mappend` (y `mappend` (z `mappend` mempty))
换句话说，fold 提供了一种使用幺半群“折叠”列表的简单方式，因此选择了这个函数名。注意，fold 的行为与 Monoid 类中的 mconcat 相同，但它使用显式递归定义，而不是使用 foldr。以类似方式，也可以为叶子中带有数据的二叉树类型定义一个 fold 版本：
data Tree a = Leaf a | Node (Tree a) (Tree a)
deriving Show
fold :: Monoid a => Tree a -> a
fold (Leaf x) = x
fold (Node l r) = fold l `mappend` fold r
也就是说，对于叶子，只返回其中包含的值；对于节点，递归折叠两棵子树，并用 mappend 组合所得值。这个例子的定义不需要使用单位元 mempty，因为这种类型的树总是非空的。
更一般地说，使用幺半群折叠数据结构中的值这一思想并不特定于列表和二叉树这类类型，而可以抽象到一系列参数化类型。在 Haskell 中，这个概念由库 Data.Foldable 中的下面类声明捕获：
class Foldable t where
fold :: Monoid a => t a -> a
foldMap :: Monoid b => (a -> b) -> t a -> b
foldr :: (a -> b -> b) -> b -> t a -> b
foldl :: (a -> b -> a) -> a -> t b -> a
也就是说，要让参数化类型成为 Foldable 类的实例，它必须支持一系列具有指定类型的折叠函数。按照惯例，foldable 类型通常记为 t，如上面的声明所示。
直观来看，Foldable 类中推广后的 fold 接收一个类型为 t a 的数据结构，其中元素类型为 a，并使用该类型的幺半群原语组合这些元素，得到一个类型为 a 的单个值。接着，foldMap 通过额外接收一个类型为 a -> b 的函数来推广 fold。该函数会在组合之前应用到结构中的每个元素上，然后使用类型 b 的幺半群原语组合所得值。
上面类声明中的最后两个函数 foldr 和 foldl，把第 7 章介绍的列表高阶函数推广到其他数据结构。注意，对于这两个函数，不需要底层幺半群，因为起始值和用于组合两个值的函数都会显式作为参数提供。
完整版本的 Foldable 类还包含许多其他有用函数，以及一些默认定义，但我们先考虑上面给出的简化版本。
示例
正如预期，列表类型可以通过适当定义折叠原语来成为 foldable 类型：
instance Foldable [] where
-- fold :: Monoid a => [a] -> a
fold [] = mempty
fold (x:xs) = x `mappend` fold xs
-- foldMap :: Monoid b => (a -> b) -> [a] -> b
foldMap _ [] = mempty
foldMap f (x:xs) = f x `mappend` foldMap f xs
-- foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ v [] = v
foldr f v (x:xs) = f x (foldr f v xs)
-- foldl :: (a -> b -> a) -> a -> [b] -> a
foldl _ v [] = v
foldl f v (x:xs) = foldl f (f v x) xs
例如，使用上一节中的数值幺半群，foldMap 现在可以用来计算一个数字列表的和与积：
> getSum (foldMap Sum [1..10])
55
> getProduct (foldMap Product [1..10])
3628800
如果尝试这些例子，请确保导入 Data.Monoid 和 Data.Foldable。二叉树实例可以用类似方式定义，只是需要注意确保 foldr 和 foldl 分别按从右到左和从左到右的顺序组合树中的值：
instance Foldable Tree where
-- fold :: Monoid a => Tree a -> a
fold (Leaf x) = x
fold (Node l r) = fold l `mappend` fold r
-- foldMap :: Monoid b => (a -> b) -> Tree a -> b
foldMap f (Leaf x) = f x
foldMap f (Node l r) = foldMap f l `mappend` foldMap f r
-- foldr :: (a -> b -> b) -> b -> Tree a -> b
foldr f v (Leaf x) = f x v
foldr f v (Node l r) = foldr f (foldr f v r) l
-- foldl :: (a -> b -> a) -> a -> Tree b -> a
foldl f v (Leaf x) = f v x
foldl f v (Node l r) = foldl f (foldl f v l) r
例如，考虑下面这棵整数树：
tree :: Tree Int
tree = Node (Node (Leaf 1) (Leaf 2)) (Leaf 3)
那么求值 foldr (+) 0 tree 会得到结果 1+(2+(3+0))，其中加法从右到左执行；而 foldl (+) 0 tree 会得到 ((0+1)+2)+3，其中加法从左到右执行。当然，在这个例子中结果相同，因为加法满足结合律。不过，正如第 15 章将看到的，使用 foldl 可能更高效。
其他原语与默认定义
除了四个基本折叠原语之外，Foldable 类还包含一系列用于组合数据结构中值的其他有用函数。第一组函数推广了列表上的熟悉函数：
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
例如，null 判断一个结构是否为空，也就是没有元素；length 计算类型为 t a 的结构中类型为 a 的元素数量。因此，这些函数既可以应用到列表，也可以应用到树：
> null []
True
> null (Leaf 1)
False
> length [1..10]
10
> length (Node (Leaf 'a') (Leaf 'b'))
2
接着，这个类还包含用于至少含有一个元素的结构的 foldr 和 foldl 版本，因此它们不需要起始值：
foldr1 :: (a -> a -> a) -> t a -> a
foldl1 :: (a -> a -> a) -> t a -> a
例如：
> foldr1 (+) [1..10]
55
> foldl1 (+) (Node (Leaf 1) (Leaf 2))
3
这个类中的最后一个原语会把数据结构展平成列表，例如把树 Node (Leaf 1) (Leaf 2) 转换为列表 [1,2]：
toList :: t a -> [a]
事实上，函数 toList 在 Foldable 类声明中扮演特殊角色，因为它可以用于根据列表的对应原语，为类中的大多数其他原语提供默认定义。特别是，有下面这组默认定义：
foldr f v = foldr f v . toList
foldl f v = foldl f v . toList
foldr1 f = foldr1 f . toList
foldl1 f = foldl1 f . toList
null = null . toList
length = length . toList
elem x = elem x . toList
maximum = maximum . toList
minimum = minimum . toList
sum = sum . toList
product = product . toList
例如，定义 null = null . toList 说明，可以先把数据结构展平成列表，再使用列表实例中的 null 检查这个列表是否为空，从而判断数据结构是否为空。其他定义也有类似直接的解释。
foldable 类中的最后三个默认定义建立了原语 fold、foldMap 和 toList 之间的重要关系：
fold = foldMap id
foldMap f = foldr (mappend . f) mempty
toList = foldMap (\x -> [x])
也就是说，fold 可以看作 foldMap 的一个特例，其中在组合之前会把恒等函数应用到每个元素上。接着，foldMap 可以根据 foldr 定义，做法是在使用幺半群原语组合元素之前，把函数 f 应用到每个元素上。最后，toList 可以根据 foldMap 定义，做法是先把每个元素转换为单元素列表，然后使用列表幺半群拼接得到的列表。
总之，Foldable 类提供了一系列处理数据结构中值的有用函数，其中大多数都根据列表的特定实例或类中的其他泛型函数给出默认定义。此时自然会产生三个问题。
-
为什么类中有这么多函数？特别是，可能会问，为什么
null、length等额外原语作为Foldable类中的方法提供，而不是作为 foldable 库中的定义提供。原因是这样可以在需要时覆盖默认定义；如果它们被定义为顶层函数，这一点就不可能做到。 -
需要手动定义什么？
Foldable类实例的最小完整定义是定义foldMap或foldr之一，因为类中的所有其他函数都可以使用默认定义和列表实例从这两者之一推导出来。正如我们已经在列表和树中看到的，定义函数foldMap往往最简单。 -
效率如何？对许多应用来说，使用类中提供的默认定义就足够了；但如果需要更高效率，可以像上面所说的那样覆盖它们。实践中，GHC 系统使用的默认定义比这里展示的简单版本更高效，但它们在功能上与我们的简单版本等价。
本节最后注意，GHC 会自动导入库 Data.Foldable，但当前会隐藏该类的 fold 和 toList 方法。因此，使用 foldable 类型编程时，我们通常更喜欢显式导入 Data.Foldable，而不是依赖自动提供的裁剪版本。作为参考，Foldable 类的完整定义可见附录 B。
泛型函数
抽象出 foldable 类型概念的一个重要好处，是可以使用 Foldable 类中的原语定义可用于任何这类类型的泛型函数。例如，回忆一下第 2 章中定义过一个函数，用来计算整数列表的平均值：
average :: [Int] -> Int
average ns = sum ns `div` length ns
现在已经看到，函数 sum 和 length 并不特定于列表，而可以用于任何 foldable 类型，因此 average 的类型可以推广，而定义本身不需要任何修改：
average :: Foldable t => t Int -> Int
average ns = sum ns `div` length ns
因此，它现在既可以应用到列表，也可以应用到树：
> average [1..10]
5
> average (Node (Leaf 1) (Leaf 3))
2
类似地，库 Data.Foldable 为许多作用于逻辑值列表的熟悉函数提供了泛型版本：
and :: Foldable t => t Bool -> Bool
and = getAll . foldMap All
or :: Foldable t => t Bool -> Bool
or = getAny . foldMap Any
all :: Foldable t => (a -> Bool) -> t a -> Bool
all p = getAll . foldMap (All . p)
any :: Foldable t => (a -> Bool) -> t a -> Bool
any p = getAny . foldMap (Any . p)
在每种情况下，使用 foldMap 以及合适的幺半群原语，都让我们能够以泛型方式获得期望行为：
> and [True,False,True]
False
> or (Node (Leaf True) (Leaf False))
True
> all even [1,2,3]
False
> any even (Node (Leaf 1) (Leaf 2))
True
最后一个例子，拼接列表的函数 concat :: [[a]] -> [a] 现在可以推广到任意元素为列表的 foldable 类型，只需使用列表幺半群折叠这些元素：
concat :: Foldable t => t [a] -> [a]
concat = fold
例如：
> concat ["ab","cd","ef"]
"abcdef"
> concat (Node (Leaf [1,2]) (Leaf [3]))
[1,2,3]
总之，在 Haskell 中声明新类型时，考虑它是否可以做成 foldable 类型是有益的；为此只需定义原语 foldMap 或 foldr 之一。这样做的好处是，通过 Foldable 类中包含的默认定义，以及任何基于这些原语定义的其他泛型函数，我们基本上可以“免费”获得一系列适用于该类型的有用函数。
14.3 Traversable
正如第 12 章所见，把函数映射到数据结构中每个元素上的思想由函子概念捕获：
class Functor f where
fmap :: (a -> b) -> f a -> f b
例如，对列表来说，原语 fmap 由熟悉的库函数 map 给出，它可以递归定义如下：
map :: (a -> b) -> [a] -> [b]
map g [] = []
map g (x:xs) = g x : map g xs
不过，把函数映射到列表上的思想还可以进一步推广。例如，假设应用到每个元素上的函数 g 可能失败，也就是说，它的类型是 a -> Maybe b，而不是简单的 a -> b；并且整个映射只有当每次这样的应用都成功时才成功。利用第 12 章也见过的 Maybe 是 applicative 这一事实，很容易定义一个实现这种行为的函数：
traverse :: (a -> Maybe b) -> [a] -> Maybe [b]
traverse g [] = pure []
traverse g (x:xs) = pure (:) <*> g x <*> traverse g xs
这个定义的递归结构本质上与 map 相同，只是使用 applicative 机制来管理失败的可能性。通过这种方式，traverse 提供了一种使用可能失败的函数遍历列表元素的简单方法，因此选择了这个函数名。
举例来说，假设用 Maybe 类型定义一个递减整数的函数，前提是该整数严格为正：
dec :: Int -> Maybe Int
dec n = if n > 0 then Just (n-1) else Nothing
那么有：
> traverse dec [1,2,3]
Just [0,1,2]
> traverse dec [2,1,0]
Nothing
如果希望在 GHCi 中尝试这些例子，注意标准库中已经定义了 traverse，如下节所示。
毫不意外，以这种方式遍历数据结构的思想并不特定于列表类型，也不特定于可能失败的参数函数。支持这种广义映射函数的类型类称为 traversable types，简称 traversables。在 Haskell 中，这个概念由下面的内置类声明捕获：
class (Functor t, Foldable t) => Traversable t where
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
也就是说，对于一个既是函子又是 foldable 的参数化类型 t，要让它成为 Traversable 类的实例，它必须支持一个具有指定类型的 traverse 函数。要求 t 是函子反映出 traversable 推广了映射思想，因此应当支持原语 fmap。要求 t 是 foldable 则确保 traversable 类型中的值在需要时也可以被折叠起来。
示例
因为列表既是函子又是 foldable，列表类型可以通过把用于 Maybe 类型的 traverse 推广到任意 applicative 来做成 traversable。也就是说，定义保持不变，但类型被推广：
instance Traversable [] where
-- traverse :: Applicative f => (a -> f b) -> [a] -> f [b]
traverse g [] = pure []
traverse g (x:xs) = pure (:) <*> g x <*> traverse g xs
树的实例也可以用类似方式定义，只是参数函数的应用发生在基本情况中：
instance Traversable Tree where
-- traverse :: Applicative f =>
-- (a -> f b) -> Tree a -> f (Tree b)
traverse g (Leaf x) = pure Leaf <*> g x
traverse g (Node l r) =
pure Node <*> traverse g l <*> traverse g r
例如，现在可以使用 traverse 把可能失败的函数（例如上一节中的 dec）映射到列表和树上：
> traverse dec [1,2,3]
Just [0,1,2]
> traverse dec [2,1,0]
Nothing
> traverse dec (Node (Leaf 1) (Leaf 2))
Just (Node (Leaf 0) (Leaf 1))
> traverse dec (Node (Leaf 0) (Leaf 1))
Nothing
其他原语与默认定义
除了 traverse 原语之外，Traversable 类还包含下面这个额外函数和默认定义：
sequenceA :: Applicative f => t (f a) -> f (t a)
sequenceA = traverse id
这个类型表示，sequenceA 会把一个元素为 applicative 动作的数据结构转换为单个这样的动作，该动作返回一个数据结构；而定义说明，这可以通过使用恒等函数遍历结构中的元素来实现，在这里恒等函数的类型为 f a -> f a。
例如，sequenceA 可以把元素可能失败的数据结构转换为可能失败的数据结构：
> sequenceA [Just 1, Just 2, Just 3]
Just [1,2,3]
> sequenceA [Just 1, Nothing, Just 3]
Nothing
> sequenceA (Node (Leaf (Just 1)) (Leaf (Just 2)))
Just (Node (Leaf 1) (Leaf 2))
> sequenceA (Node (Leaf (Just 1)) (Leaf Nothing))
Nothing
反过来，类声明也包含一个根据 sequenceA 定义 traverse 的默认定义。它表达的是：为了使用带效果函数遍历数据结构，可以先使用 fmap 把函数应用到每个元素上，然后使用 sequenceA 组合所有效果：
-- traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
traverse g = sequenceA . fmap g
通过这种方式，声明 Traversable 类实例时，只需定义 traverse 或 sequenceA 之一，因为每一个都可以通过上面的默认定义由另一个推导出来。不过，由于 traverse 的默认定义在概念上会对数据结构进行两遍处理，一遍使用 fmap，另一遍使用 sequenceA，因此通常更倾向于定义 traverse，而不是 sequenceA。
最后，当涉及的效果是 monadic 而不是 applicative 时，这个类还为两个 traversable 原语的特殊情况提供了专门名字，如下所示。作为参考，Traversable 类的完整定义可见附录 B。
mapM :: Monad m => (a -> m b) -> t a -> m (t b)
sequence :: Monad m => t (m a) -> m (t a)
mapM = traverse
sequence = sequenceA
总之，在声明新类型时，考虑它是否可以通过定义原语 traverse 或 sequenceA 之一做成 traversable 类型也是有益的。这样做的好处是，通过 Traversable 类中的默认定义，我们随后会获得若干适用于该类型的带效果编程函数。
14.4 章注（Chapter remarks）
关于 Haskell 中幺半群使用的更多信息可见文献 [26]。从列表向其他数据结构推广 foldr 有两种标准方式，在文献中称为 catamorphisms [27] 和 crush operators [28]。Foldable 类捕获的广义折叠形式对应 crush，因此可以说 Foldable 类实际上应该叫作 Crushable，而原语 fold 应该叫作 crush。Traversable 由文献 [19] 引入，其中也讨论了定律问题。
14.5 练习（Exercises）
- 补全
Data.Monoid中的下面实例声明，使一对类型在两个组成类型都是幺半群时成为幺半群：
instance (Monoid a, Monoid b) => Monoid (a,b) where
-- mempty :: (a,b)
mempty = ...
-- mappend :: (a,b) -> (a,b) -> (a,b)
(x1,y1) `mappend` (x2,y2) = ...
- 以类似方式，说明如何在结果类型
b是幺半群时，把函数类型a -> b做成幺半群。 - 通过给出
fold、foldMap、foldr、foldl和traverse的显式定义，说明如何把Maybe类型做成 foldable 和 traversable。 - 以类似方式，说明如何把下面这种节点中包含数据的二叉树类型做成 foldable 和 traversable 类型：
data Tree a = Leaf | Node (Tree a) a (Tree a)
deriving Show
- 使用
foldMap，定义高阶列表函数filter的泛型版本，使其可以用于任何 foldable 类型：
filterF :: Foldable t => (a -> Bool) -> t a -> [a]
练习 1 和 2 的解答见附录 A。