Haskell/Foldable类型类
Foldable 类型类归纳了列表上各种形式的 fold (foldr 和它的朋友们) 并将它们扩展到了任意的数据结构. 除了本身有极大的实用价值之外, Foldable 还很好地演示了 monoid 如何能够帮助我们更好地抽象.
解剖 foldr
编辑
foldr 要做的事情并不少 -- 接收一个并返回一个二元函数, 每一个的类型中都有两个变量.
foldr :: (a -> b -> b) -> b -> [a] -> b
如果我们想要一般化 foldr, 或许我们会需要一个更简单的函数, 或者我们至少要能够将它拆散成更简单的组件. 这些组件是什么呢?
列表上的 fold 可以被粗略地描述为, 顺序访问列表内的元素并用一个二元函数将它们结合起来. 我们恰巧知道, 有一个类型类存在的目的就是为了结合一对值: 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, 正如同我们使用 mconcat 一样 (即 (<>)) 和 mempty:
mconcat :: Monoid m => [m] -> m
mconcat 很好地复刻了 foldr 的"将所有元素结合"的特性, 并且支持一些后者的用法:
GHCi> mconcat ["Tree", "fingers"] -- concat
"Treefingers"
很好 −- 但显然我们不希望只能 fold Monoid. 一个可能的解决方案是将一个列表中任意类型的元素转化为 Monoid 值以使用 mconcat 进行 fold:
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. 我们可以在 Data.Monoid 模块中的 Endo 里找到对应的 Monoid instance 定义[1]:
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)))
-- (<>) 和 (.) 满足结合律, 因此括号其实可有可无.
-- 作为例子, 我们试着剖析计算过程:
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 是 Foldable 的核心, 其进而将 foldr 推广到任意数据结构.
| 练习 |
|---|
|
Foldable 类型类
编辑
为数据结构实现 Foldable 的 instance 只需要一个函数: foldMap 和 foldr 任选其一即可. 然而, Foldable, 定义了许多其它函数:
-- 简便起见, 我们这里只写出类型.
class Foldable t where
foldMap :: Monoid m => (a -> m) -> t a -> m
foldr :: (a -> b -> b) -> b -> t a -> b
-- 以下函数都有默认实现:
fold :: Monoid m => t m -> m -- 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
我们将扩展出的函数也定义在类型类中 (而不是在模块中直接提供默认的定义) 是为了为更高效的实现留出位置 -- 比如说, 如果我们需要一个对性能高度敏感的数据结构, 或许我们不会希望如同 foldl' 的默认实现那样使用一些低效的技巧以将 foldr 转换成 foldl. 但在任何情况下, 只要实现了 foldMap 或 foldr, 我们都可以"免费"使用上面列出的所有这些有用的函数. 这还没完: Data.Foldable 模块提供了更多推广了 Foldable 的函数, 其中包括了值得注意的 mapM_/traverse_.
我们来看一个使用 Data.Map 的 Foldable 实现的样例:
GHCi> import qualified Data.Map as M
GHCi> let testMap = M.fromList $ zip [0..] ["昨天","我","起床","的时候","发现自己","含着","一个","柠檬"]
GHCi> length testMap
8
GHCi> sum . fmap length $ testMap
18
GHCi> elem "柠檬" testMap
True
GHCi> foldr1 (\x y -> x ++ (' ' : y)) testMap -- 注意: foldr1 是一个偏函数!
"昨天 我 起床 的时候 发现自己 含着 一个 柠檬"
GHCi> import Data.Foldable
GHCi> traverse_ putStrLn testMap
昨天
我
起床
的时候
发现自己
含着
一个
柠檬
除了提供一些有用的推广之外, Foldable 和 foldMap 还揭示了一种声明式编程的视角. 比如说, 与其将 sum 看成一个遍历一个列表 (或者一棵树或者随便什么数据结构) 并将其中的值用 (+) 累加起来的函数, 我们可以认为其询问了每个元素的值并使用 Sum 将询问结果总结了. 虽然这看起来并没有太大不同, 这种总结一个 monoid 的新角度能够让我们抛去被 fold 的数据结构的实现细节, 专注于我们想要的结果.
列表风格的 fold
编辑Foldable 还提供了一个 toList :: Foldable t => t a -> [a] 函数. 这意味着, 一个 Foldable 数据结构能够被转化成一个列表; 而且, 在这个列表上进行 fold 得到的结果和直接在原来的数据结构上进行结果无异. 一个可行的使用 foldMap 的 toList 实现是[2]:
toList = foldMap (\x -> [x])
toList 反映了, 列表实际上是 Haskell 中类型上的自由幺半群(free monoid). "自由"指的是, 任何值都能够被以某种方式转化成一个 monoid, 并且不增添或遗漏任何信息 (使用 (\x -> [x]) 和 head, 我们能够将任意类型为 a 的值与 [a] 互相转化并且不丢失信息) [3].
Foldable 的一个与此有关的关键性质能够被 toList 体现出来. 因为对于列表来说, toList = id, 如果我们有这样定义的一个函数...
-- xs :: [a]
xsAsFoldMap :: Monoid m => (a -> m) -> m
xsAsFoldMap = \f -> foldMap f xs
... 我们只要将 (\x -> [x]) 传递给 xsAsFoldMap 就可以从中得回 xs. 这种意义上, 一个列表和它的右 fold 等价(同构). 这意味着, 对任何比列表复杂的 Foldable 的操作都会损失一定的信息. 换句话说, Foldable 提供的从列表推广出的 fold 都没有我们在更多数据类型一章中所见到的那么通用 (在后者中我们总是能够从 fold 得回原值).
| 练习 |
|---|
|
更多关于 Foldable 的事
编辑
Foldable 在 Haskell 的通用而有特殊规定的类型类中独树一帜, 因为其并没有规定自己的法则. 然而, 我们确实能够得出以下性质, 虽然它们严格来说并不是法则 (因为对于任何 instance 它们都成立): 对于一个幺半群同态 g[4],
foldMap (g . f) = g . foldMap f
不使用 foldMap (g . f) 的写法, 而是使用 g . foldMap f 有一些好处, 也就是 g 只被应用到了 fold 的结果上, 而不是应用到了被 fold 的数据结构中的每一个值上.
如果这里的 Foldable 也是一个 Functor, 我们有这个性质...
foldMap f = fold . fmap f
... 因此在使用了 Functor 法则后我们能够得到:
foldMap g . fmap f = foldMap (g . f) = g . foldMap f
虽然 foldMap 或许暗示了任何 Foldable 都应该也是一个 Functor, 实际情况却并不总是这样. 例如 Data.Set.Set. 因为其中的值必须有 Ord instance, 因此它提供的 map 函数并不能和 fmap 等价, 因为后者的返回值类型可能没有 Ord instance. 但是, 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"
| 练习 |
|---|
|
| Foldable类型类 |
| 习题解答 |
| 高级Haskell |
|
Monoid类型类 >> Applicative类型类 >> 箭头 >> 理解箭头 >> Foldable类型类 >> Traversable类型类 >> 延续过渡风格（CPS） >> 可变对象 >> 拉链 >> 适用函子 >> 独异点 >> Lens 和引用 >> 并行 |
| Haskell |
|
Haskell基础
>> 初级Haskell
>> Haskell进阶
>> Monads
|
- ↑ "Endo" 是 "endomorphism" 的缩写, 指一个参数和返回值同类型的函数.
- ↑
Data.Foldable为了性能考虑使用了一种不同的默认实现. - ↑ 对于列表形成一个自由幺半群这件事, 在非终止性上有一个值得注意的地方. 详见 Dan Doel 所写的 Free Monoids in Haskell. (那篇文章中的讨论或许有些超前, 毕竟我们刚刚介绍了
Foldable.) - ↑ 即满足
f (x `mappend` y) = f x `mappend` f y的函数f. - ↑ 见Haskell Café