容器抽象：Foldable 与 Traversable¶

早期 Haskell 中，map 与 foldr 只对列表有效。现在这些操作被抽象为两个通用的容器类型类：Foldable（泛化折叠）与 Traversable（带效果的遍历与结构翻转）。

有了这两个类型类，同一套代码可以操作列表、二叉树、集合以及任何自定义容器。

Foldable：泛化的折叠¶

定义在 Data.Foldable 中：

class Foldable t where
  foldr   :: (a -> b -> b) -> b -> t a -> b
  foldMap :: Monoid m => (a -> m) -> t a -> m

只要一个类型构造器 t（Kind 为 * -> *）装着元素，并且能按某种顺序遍历，它就可以成为 Foldable。

foldMap 与 Monoid¶

foldMap 接收一个把元素映射为某种 Monoid 的函数，然后用该 Monoid 的 (<>) 与 mempty 把整个容器合并起来：

import Data.Foldable
import Data.Monoid

-- 为二叉树实现 Foldable
data Tree a = Leaf | Node (Tree a) a (Tree a) deriving (Show, Eq)

instance Foldable Tree where
  foldMap _ Leaf = mempty
  foldMap f (Node left val right) =
    foldMap f left <> f val <> foldMap f right

只实现这一个函数，二叉树就可以使用所有标准折叠函数：

ghci> myTree = Node (Node Leaf 1 Leaf) 2 (Node Leaf 3 Leaf)
ghci> sum myTree
6
ghci> length myTree
3
ghci> toList myTree
[1,2,3]
ghci> elem 2 myTree
True
ghci> maximum myTree
3
ghci> find (> 1) myTree
Just 2
ghci> foldl' (+) 0 myTree
6

这些函数全部定义在 Data.Foldable 里，签名中的容器类型都是 Foldable t => t a。sum、length、elem、maximum 这几个 Prelude 直接导出，toList、find、foldl' 需要从 Data.Foldable 导入。

警告

Prelude 里的 length、sum、elem 都是 Foldable 上的通用函数，不只对列表有效。Maybe 和二元组也是 Foldable 实例，所以下面这些都能编译，而且结果往往不是直觉里的那个：

ghci> length (Just 3)
1
ghci> length (1, 2)
1
ghci> sum (Just 5)
5

二元组的实例只折叠第二个分量，所以 length (1, 2) 是 1 而不是 2。想对 Maybe 或元组“数个数”时，多半是写错了类型；类型检查不会拦住这类错误，只能靠自己留意。

小技巧

如果你熟悉其他语言：把 Foldable 理解为 Reducible：

直觉：Reducible，即可以规约成单个值的容器。核心操作是 foldr（通用折叠）与 foldMap（借助 Monoid 合并）。
跨语言映射：
- JavaScript：数组的 [].reduce((acc, x) => ..., initial)。
- Python：标准库 functools.reduce(function, iterable[, initializer])。
- Java：Stream API 的 stream.reduce(...)。
与命令式循环的差异：Foldable 不需要显式的游标和局部累加变量。只要元素之间有一个二元合并操作（或者本身是 Monoid），就可以把整个容器归并为一个结果。

Traversable：带效果的遍历与结构翻转¶

考虑这样一个场景：有一个用户 ID 列表 [101, 102, 103]，需要逐一调用网络接口 fetchUser :: Int -> IO User。

如果只用 fmap：

ghci> :t fmap fetchUser [101, 102, 103]
fmap fetchUser [101, 102, 103] :: [IO User]

得到的是一个由 IO 动作组成的列表（[IO User]）。但多数时候我们想要的是一个返回用户列表的 IO 动作（IO [User]），执行它时依次完成所有查询。

两种结构的差别如下图，traverse 做的就是把左边变成右边：

        graph LR
  subgraph before["fmap fetchUser ids :: [IO User]"]
    direction TB
    L["[ ]"] --> IO1["IO User"]
    L --> IO2["IO User"]
    L --> IO3["IO User"]
  end
  subgraph after["traverse fetchUser ids :: IO [User]"]
    direction TB
    IO["IO"] --> L2["[ ]"]
    L2 --> U1["User"]
    L2 --> U2["User"]
    L2 --> U3["User"]
  end
  before ==>|traverse| after

  classDef io fill:#fff3d6,stroke:#c48a1a;
  classDef lst fill:#dbe9ff,stroke:#3b6fb6;
  class IO1,IO2,IO3,IO io;
  class L,L2 lst;

“遍历容器的同时执行 Applicative 效果，并把内外两层结构翻转”，这就是 Traversable 做的事。

Traversable 的定义¶

定义在 Data.Traversable 中：

class (Functor t, Foldable t) => Traversable t where
  traverse  :: Applicative f => (a -> f b) -> t a -> f (t b)
  sequenceA :: Applicative f => t (f a) -> f (t a)
  sequenceA = traverse id

sequenceA：结构翻转。接收一个装着效果的容器（如 [Maybe a]），返回一个装着容器的效果（如 Maybe [a]）。
traverse：先映射产生效果，再翻转。等价于 traverse f = sequenceA . fmap f。

小技巧

如果你熟悉其他语言：把 Traversable 理解为“带效果的 map”（Effectful Mapping）：

直觉：普通 map（Functor）只能对内部的值做纯计算。如果映射函数本身会产生效果（网络请求、校验、可能失败），用普通 map 会得到一个“装满效果的容器”（例如 [IO User] 或 [Maybe a]）。
核心操作：traverse（Elm 中叫 traverse 或 combine）。它一边对每个元素做带效果的变换，一边把所有效果按顺序串联起来，最后把外层容器与内层效果翻转。
跨语言映射：
- JavaScript / TypeScript：有一个用户 ID 列表 users = [1, 2, 3]，对每个 ID 调用异步查询 fetchUser(id)。直接 users.map(fetchUser) 得到的是 Promise 数组 [Promise<User>]；要得到 Promise<User[]>，需要写 Promise.all(users.map(fetchUser))。在 Haskell 中这就是 traverse fetchUser users。
- Elm：提供 combine 函数，把 List (Result e a) 翻转为 Result e (List a)。
- Rust：把产生 Result<T, E> 的迭代器收集为一个 Result<Vec<T>, E>（即 iter.map(fetch).collect::<Result<Vec<_>, _>>()）。
- Java：把 List<CompletableFuture<User>> 汇总为一个 CompletableFuture<List<User>>。
判断标准：手里拿着“容器里装满效果”（如 [IO a] 或 [Maybe a]），而需要的是“效果里包着容器”（如 IO [a] 或 Maybe [a]）时，用 sequenceA 或 traverse。

为自定义 Tree 实现 Traversable¶

Tree 要支持 traverse，必须先实现 Functor：

instance Functor Tree where
  fmap _ Leaf = Leaf
  fmap f (Node l x r) = Node (fmap f l) (f x) (fmap f r)

instance Traversable Tree where
  traverse _ Leaf = pure Leaf
  traverse f (Node l x r) =
    Node <$> traverse f l <*> f x <*> traverse f r

通过 <*> 串联，遍历既保留了树的形状，又在每个节点上按顺序执行并组合了 Applicative 效果。

用 GHC 扩展自动派生¶

实际项目中通常直接开启扩展让编译器生成这些实例：

{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-}

data Tree a = Leaf | Node (Tree a) a (Tree a)
  deriving (Show, Eq, Functor, Foldable, Traversable)

Traversable 的三条法则（Laws）¶

合法的 Traversable 实例需要满足以下三条法则：

同一律（Identity）：用 Identity 函子遍历不改变原结构：
```
traverse Identity == Identity
```
复合律（Composition）：两个 Applicative 效果的嵌套遍历，等价于用复合函子做一次遍历：
```
traverse (Compose . fmap g . f) == Compose . fmap (traverse g) . traverse f
```
自然性（Naturality）：对于任何保持 Applicative 结构的自然变换 t，有：
```
t . traverse f == traverse (t . f)
```

常见用法¶

1. 批量解析（带短路）¶

ghci> import Text.Read (readMaybe)
-- 全部成功，得到包含列表的 Just：
ghci> traverse readMaybe ["10", "20", "30"] :: Maybe [Int]
Just [10,20,30]

-- 任意一项解析失败，整体返回 Nothing：
ghci> traverse readMaybe ["10", "abc", "30"] :: Maybe [Int]
Nothing

短路还是累积，取决于传入的 Applicative 而不是 traverse 本身。把 Maybe 换成 Applicative 一章的 Validation，同一个 traverse 就会把所有失败项的错误收集起来，下面一节会演示。

2. 批量执行 IO 动作¶

fetchAllUsers :: [Int] -> IO [User]
fetchAllUsers ids = traverse fetchUser ids

3. 只要效果、不要返回值：traverse_ 与 for_¶

如果遍历时只关心副作用（写日志、发通知），不需要把结果收集成新列表，可以用 traverse_ 与 for_，省去分配新列表的开销：

import Data.Foldable (for_)

notifyUsers :: [User] -> IO ()
notifyUsers users = do
  for_ users $ \u -> do
    putStrLn $ "正在通知: " ++ userName u

三层抽象的分工：签名该要哪一层¶

到这里，Functor、Applicative、Monad 三层都介绍完了，可以回头看一遍它们各自买到了什么：

类型类	核心操作	能做什么
`Functor`	`fmap`	只改上下文里的结果，不新增效果，也不改变结构。
`Applicative`	`pure`、`<*>`	组合几个彼此独立的效果。哪些效果会发生在运行前就已知，所以可以并行、可以累积错误、可以静态分析。
`Monad`	`>>=`	后一步可以依赖前一步的返回值。表达力最强，代价是效果只能顺序执行，出错只能短路。

写函数签名时的规则是：要求能写出函数体的最弱约束。只用 fmap 就够的函数不要写 Monad m =>，只用 <*> 组合的函数不要写 >>=。约束越弱，函数能用在越多的类型上，调用者也能从签名直接看出这段代码不会做什么。

traverse 就是这条规则的受益者。它的签名只要求 Applicative f，所以可以用在没有 Monad 实例的 Validation 上，把所有错误一次收齐：

ghci> checkAge age = if age < 18 then Failure ["年龄必须满 18 岁: " ++ show age] else Success age
ghci> traverse checkAge [15, 20, 3]
Failure ["年龄必须满 18 岁: 15","年龄必须满 18 岁: 3"]
ghci> traverse checkAge [20, 30]
Success [20,30]

换成 mapM checkAge 则直接编译失败，报 No instance for (Monad (Validation [String]))。同一件事，签名多要了一层约束，就把一整类类型挡在了门外。

由此得到两条实践建议：

新代码优先用 traverse、for_、sequenceA，而不是 Monad 一章 Control.Monad 里的 mapM、forM_、sequence。后者只是前者限定在 Monad 上的别名，功能没有多，适用范围却更窄。
自己写实例时也从弱到强：能写 Applicative 就先写 Applicative，确实需要“下一步依赖上一步”再补 Monad。

小结¶

Foldable 统一了容器的折叠操作，实现 foldMap 即可获得 sum、length、toList 等全部函数。
Traversable 在遍历容器的同时执行 Applicative 效果，并把内外结构翻转。
mapM 和 sequence 现在只是 traverse 和 sequenceA 限定在 Monad 上的别名，新代码优先用后者。
签名只要求能写出函数体的最弱约束：Functor 改结果，Applicative 组合独立效果，Monad 才允许后一步依赖前一步。
Prelude 的 length、sum 是 Foldable 通用函数，对 Maybe 和元组也能用，留意误用。
DeriveTraversable 等扩展可以自动为自定义类型生成这些实例。

← 单子（Monad）与 do 记号状态与环境管理：Reader、Writer 与 State →