跳转到内容

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. 因为其更基础, foldMapFoldable 的核心, 其进而将 foldr 推广到任意数据结构.

练习
  1. 实现两个版本的作用于列表上 foldMap: 其中一个使用 foldr, 另一个使用显示递归.

Foldable 类型类

[编辑]

为数据结构实现 Foldable 的 instance 只需要一个函数: foldMapfoldr 任选其一即可. 然而, 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. 但在任何情况下, 只要实现了 foldMapfoldr, 我们都可以"免费"使用上面列出的所有这些有用的函数. 这还没完: Data.Foldable 模块提供了更多推广了 Foldable 的函数, 其中包括了值得注意的 mapM_/traverse_.

我们来看一个使用 Data.MapFoldable 实现的样例:

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
昨天

起床
的时候
发现自己
含着
一个
柠檬

除了提供一些有用的推广之外, FoldablefoldMap 还揭示了一种声明式编程的视角. 比如说, 与其将 sum 看成一个遍历一个列表 (或者一棵树或者随便什么数据结构) 并将其中的值用 (+) 累加起来的函数, 我们可以认为其询问了每个元素的值并使用 Sum 将询问结果总结了. 虽然这看起来并没有太大不同, 这种总结一个 monoid 的新角度能够让我们抛去被 fold 的数据结构的实现细节, 专注于我们想要的结果.


列表风格的 fold

[编辑]

Foldable 还提供了一个 toList :: Foldable t => t a -> [a] 函数. 这意味着, 一个 Foldable 数据结构能够被转化成一个列表; 而且, 在这个列表上进行 fold 得到的结果和直接在原来的数据结构上进行结果无异. 一个可行的使用 foldMaptoList 实现是[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. 证明 fstsnd 幺半群同态.
    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é