跳转到内容

Haskell/Foldable类型类

编辑链接
维基教科书，自由的教学读本
Foldable类型类 (解答)
高级Haskell

Monoid类型类
Applicative类型类
箭头
理解箭头
Foldable类型类
Traversable类型类
延续过渡风格（CPS）
可变对象
拉链
适用函子
独异点
Lens 和引用
并行

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 推广到任意数据结构.

练习
  1. 实现两个版本的作用于列表上 foldMap: 其中一个使用 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 得回原值).

练习

  1. 这个练习使用到更多数据类型中的数据结构:

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

    1. 为 Tree 实现 Foldable 的 instance.
    2. 实现 treeDepth :: Tree a -> Int, 其给出树最深处的深度. 你可以使用 Foldable 或者更多数据类型一章中的 treeFold. 事实上, 这两种实现方式都是可行的吗? 
      treeFold :: (b -> b -> b) -> (a -> b) -> Tree a -> b
treeFold fbranch fleaf = g where
  g (Leaf x) = fleaf x
  g (Branch left right) = fbranch (g left) (g right)

更多关于 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"
练习
    1. 为二元组实现 Monoid instance,
      (Monoid a, Monoid b) => Monoid (a,b)
    2. 证明 fst 和 snd 幺半群同态.
    3. 使用上文提到的 foldMap 和幺半群同态的性质证明
      foldMap f &&& foldMap g = foldMap (f &&& g)
      其中,
      f &&& g = \x -> (f x, g x)

    这个练习来源于 Edward Kmett 的帖子.[5].


Foldable类型类
习题解答
高级Haskell

Monoid类型类  >> Applicative类型类  >> 箭头  >> 理解箭头  >> Foldable类型类  >> Traversable类型类  >> 延续过渡风格（CPS）  >> 可变对象  >> 拉链  >> 适用函子  >> 独异点  >> Lens 和引用  >> 并行


Haskell

Haskell基础 >> 初级Haskell >> Haskell进阶 >> Monads
高级Haskell >> 类型的乐趣 >> 理论提升 >> Haskell性能

库参考 >> 普通实务 >> 特殊任务

  1. ↑ "Endo" 是 "endomorphism" 的缩写, 指一个参数和返回值同类型的函数.
  2. ↑ Data.Foldable 为了性能考虑使用了一种不同的默认实现.
  3. ↑ 对于列表形成一个自由幺半群这件事, 在非终止性上有一个值得注意的地方. 详见 Dan Doel 所写的 Free Monoids in Haskell. (那篇文章中的讨论或许有些超前, 毕竟我们刚刚介绍了 Foldable.)
  4. ↑ 即满足 f (x `mappend` y) = f x `mappend` f y 的函数 f.
  5. ↑ 见Haskell Café
检索自“https://zh.wikibooks.org/w/index.php?title=Haskell/Foldable类型类&oldid=133752”