> For the complete documentation index, see [llms.txt](https://llh911001.gitbook.io/mostly-adequate-guide-chinese/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://llh911001.gitbook.io/mostly-adequate-guide-chinese/ch12.md).

# 第 12 章: 遍历

迄今为止，在我们的容器马戏团中，你曾看到我们驯服了凶猛的 [functor](/mostly-adequate-guide-chinese/ch8.md)，让它听从我们的意志，执行任何让我们心动的操作；你曾被同时使用[函数应用](/mostly-adequate-guide-chinese/ch10.md)来收集结果的许多危险作用的杂耍弄得晕头转向；你曾在看到容器通过 [join](/mostly-adequate-guide-chinese/ch9.md) 凭空消失时惊讶地坐倒。在副作用杂耍中，我们看到它们经过 compose 合为一体。而最近，我们大胆地超越了自然，在你的眼前将一种类型转化为另一种 ([natural transformations](/mostly-adequate-guide-chinese/ch11.md))。

至于我们的下一个表演，我们要看一下遍历。我们将看着类型在彼此之间翱翔，就像空中飞人一样保持着我们的值不变。我们将像倾斜旋转中的手推车一样重新排列作用 (effects)。当我们的容器像变形金刚的四肢一样交织在一起时，我们可以用这个接口来进行整理。我们将见证不同的作用与不同的顺序。拿上我的长裤和滑动口哨，让我们开始吧。

## 类型与类型

让我们整点怪活：

```js
// readFile :: FileName -> Task Error String

// firstWords :: String -> String
const firstWords = compose(intercalate(' '), take(3), split(' '));

// tldr :: FileName -> Task Error String
const tldr = compose(map(firstWords), readFile);

map(tldr, ['file1', 'file2']);
// [Task('hail the monarchy'), Task('smash the patriarchy')]
```

在这里，我们读了一堆文件然后形成一个无用的 task 数组。要怎么样对其中的每一个进行 fork 操作呢？如果我们能够把类型做一些变化，得到 `Task Error [String]` 而不是 `[Task Error String]` 的话，想必是极好的。这样，我们将得到一个包含所有结果的 future value（译注：即异步任务完成后返回的值）；从异步的需求来说，这要比多个 future value （分别在各自空闲时间完成任务后再返回）要好操作得多。

这里有最后一个例子，展示一种棘手的情况：

```js
// getAttribute :: String -> Node -> Maybe String
// $ :: Selector -> IO Node

// getControlNode :: Selector -> IO (Maybe (IO Node))
const getControlNode = compose(
  map(map($)),
  map(getAttribute('aria-controls')),
  $
);
```

看看那些渴望在一起的 `IO` 们。如果能把他们 `join` 起来，让他们面对面地跳舞，那真是太可爱了。可惜的是，一个 `Maybe` 站在他们之间，就像舞会上的陪练。我们最好的办法是把它们的位置移到彼此旁边，这样每种类型最后都可以在一起，我们的签名可以简化为 `IO (Maybe Node)`。

## 类型风水

`Traversable` 接口由两个值得称道的函数组成：`sequence` 和 `traverse`。

我们用 `sequence` 重新编排编排类型：

```js
sequence(List.of, Maybe.of(['the facts'])); // [Just('the facts')]
sequence(Task.of, new Map({ a: Task.of(1), b: Task.of(2) })); // Task(Map({ a: 1, b: 2 }))
sequence(IO.of, Either.of(IO.of('buckle my shoe'))); // IO(Right('buckle my shoe'))
sequence(Either.of, [Either.of('wing')]); // Right(['wing'])
sequence(Task.of, left('wing')); // Task(Left('wing'))
```

看清楚这里发生了什么吗？嵌套类型里外翻转了过来，就像潮湿夏夜里的皮裤翻过来了一样。内部的 functor 转移到了外部，而外部的转移到了内部。不过要注意，`sequence` 对它的参数有一点挑剔。它看起来像这样子：

```js
// sequence :: (Traversable t, Applicative f) => (a -> f a) -> t (f a) -> f (t a)
const sequence = curry((of, x) => x.sequence(of));
```

我们先看第二个参数。它必须是一个持有 *Applicative* 的 *Traversable*。这听起来很严格，但是事实往往如此。这就是把 `t (f a)` 转换成了 `f (t a)`。还不够明显吗？这两种类型简直就是在背靠背。而第一个参数，它仅仅是一个拐杖，只在无类型的语言中是必要的。它提供了一个类型构造器（即 *of*）用来倒置那些不情愿被 map 的类型（比如 `Left`）——稍后会有更多介绍。

使用 `sequence`，我们可以像在人行道上变戏法一样精确地转移类型。但它是如何工作的呢？让我们看看一个类型，比如说 `Either`，会如何实现它：

```js
class Right extends Either {
  // ...
  sequence(of) {
    return this.$value.map(Either.of);
  }
}
```

没错，如果我们的 `$value` 是一个 functor （事实上它必须是一个 applicative functor），我们就可以简单地 `map` 我们的构造器来实现类型的跃迁。

你可能注意到，我们把 `of` 完全忽略掉了。它仅仅是为了在 `map` 不可用的情况下而被传入的，比如在 `Left` 中：

```js
class Left extends Either {
  // ...
  sequence(of) {
    return of(this);
  }
}
```

我们希望这些类型总是以相同的排列结束，所以对于像 `Left` 这样的实际上并不持有 applicative functor 的类型来说，我们有必要这么做来让它们获得一点小小的帮助。 *Applicative* 接口要求我们首先有一个 *Pointed Functor*，使得我们总是有一个 `of` 来传入。在具有类型系统的语言中，外部的类型可以通过签名被推断而不需要显式地给出。

## 作用组合

就我们的容器而言，不同的顺序会带来不同的结果，如果我有一个 `[Maybe a]`，它是一个包含可能的值的集合 (a collection of possible values)；而如果我有一个 `Maybe [a]`，那是一个可能的包含值的集合 (a possible collection of values)。前者表示我们会宽容地保留那些"好"的值，而后者则意味着这是一个 "all or nothing" 的情况。类似地，`Either Error (Task Error a)` 可以表示一个客户端的验证，而 `Task Error (Either Error a)` 则会是一个服务端的验证。类型可以互换，为我们带来不同的作用。

```js
// fromPredicate :: (a -> Bool) -> a -> Either e a

// partition :: (a -> Bool) -> [a] -> [Either e a]
const partition = (f) => map(fromPredicate(f));

// validate :: (a -> Bool) -> [a] -> Either e [a]
const validate = (f) => traverse(Either.of, fromPredicate(f));
```

这里，根据我们使用 `map` 还是 `traverse`，我们有两个不同的函数。第一个， `partition` 将会根据谓词函数给我们一个包含 `Left` 和 `Right` 的数组。这能够把宝贵的数据保留起来以供未来使用，而不是将它和洗澡水一同过滤掉。相反，`validate` 将会给我们一个包含第一个不符合谓词函数的项目的 `Left`，或者如果一切顺利的话给我们所有的包含对应元素的 `Right`。通过选择不同的类型顺序，我们得到不同的行为。

让我们看看 `List` 的 `traverse` 函数，来了解 `validate` 是如何形成的。

```js
traverse(of, fn) {
  return this.$value.reduce(
    (f, a) => fn(a).map(b => bs => bs.concat(b)).ap(f),
    of(new List([])),
  );
}
```

它仅仅是对这个列表运行了一次 `reduce`。 传入的 reduce 函数是 `(f, a) => fn(a).map(b => bs => bs.concat(b)).ap(f)`，这看起来有点儿吓人，让我们一步步看。

1. `reduce(..., ...)`

   它的签名是 `reduce :: [a] -> (f -> a -> f) -> f -> f`。第一个参数事实上是由 `$value` 的点标记提供的，它是一个数组。然后我们需要一个函数，以一个 `f` (一个累计器) 和一个 a (迭代器，代表当前值) 为输入参数，返回一个新的累计器。
2. `of(new List([]))`

   reduce 函数的初始值是 `of(new List([]))`，在我们的例子当中则是 `Right([]) :: Either e [a]`。注意 `Either e [a]` 同时也是我们的最终返回类型。
3. `fn::Applicative f => a -> f a`

   如果我们把它应用到上面的例子， `fn` 实际上是 `fromPredicate(f) :: a -> Either e a`

   > fn(a) :: Either e a
4. `.map(b => bs => bs.concat(b))`

   当 `fn(a)` 是一个 `Right` 的时候，`Either.map` 将正确的值传入函数中并且返回一个包含结果的新的 `Right`。在这个例子中，函数有一个参数 (`b`)，并且返回了另一个函数 (`bs => bs.concat(b)`，其中 `b` 由于闭包的存在是在作用域内的。)。当它是一个 `Left` 时，Left 对应的值会被返回。

   > fn(a).map(b => bs => bs.concat(b)) :: Either e (\[a] -> \[a])
5. `ap(f)`

   `f` 在这里是一个 Applicative，所以我们可以把函数 `bs => bs.concat(b)` 应用到 `f` 中任意的值 `bs :: [a]`。幸运的是，`f` 是从我们的初始种子得到的，它有这样的类型：`f :: Either e [a]`，这也会在我们应用 `bs => bs.concat(b)` 的时候保留下来。当 `f` 是 `Right` 的时候，它将会调用 `bs => bs.concat(b)`，返回一个将元素添加到列表中的 `Right`；当它是个 `Left` 的时候，Left 对应的值会被返回。

   > fn(a).map(b => bs => bs.concat(b)).ap(f) :: Either e \[a]

这个神奇的转换仅仅通过 `List.traverse` 中的 6 行简短的代码实现，并且通过 `of`, `map` 和 `ap` 完成，所以它将在任意的 Applicative Functor 中正常工作。这是一个很棒的例子，展示了那些抽象能够如何帮助我们写出高度通用的代码，仅仅依赖于一点点假设（而且这些假设可以通过类型系统声明和检查！）。

## 类型的华尔兹

是时候重新回顾并且清理我们最开始的例子了。

```js
// readFile :: FileName -> Task Error String

// firstWords :: String -> String
const firstWords = compose(intercalate(' '), take(3), split(' '));

// tldr :: FileName -> Task Error String
const tldr = compose(map(firstWords), readFile);

traverse(Task.of, tldr, ['file1', 'file2']);
// Task(['hail the monarchy', 'smash the patriarchy']);
```

使用 `traverse` 而不是 `map`，我们成功地将那些不守规矩的 `Task` 赶到了一个漂亮的、协调的结果数组中。如果你熟悉 `Promise.all()`，你会发现它们很像；只不过 `traverse` 并不是个一次性的自定义函数，它适用于任何可遍历的类型。这些数学上的 API 倾向于以一种互操作、可重用的方式捕获我们想做的大部分事情，而不必像单个类库那样为某一类型重新发明这些函数。

让我们清理最后一个例子来收尾。

```js
// getAttribute :: String -> Node -> Maybe String
// $ :: Selector -> IO Node

// getControlNode :: Selector -> IO (Maybe Node)
const getControlNode = compose(
  chain(traverse(IO.of, $)),
  map(getAttribute('aria-controls')),
  $
);
```

我们用 `chain(traverse(IO.of, $))`代替 `map(map($))`，它在映射时反转我们的类型，然后通过 chain 将两个 IO 扁平化。

## 定律

好了，在你要像法官像敲槌子一样下结论关闭本章之前，还是要认识到，这些定律是很受用的法规保证。在我看来，大多数程序架构的目地是对代码加以限制来缩小可能性，最终引导我们找到正确答案。

一个没有定律的接口是迂回的。像其他的数学结构一样，为了我们自己的理智，我们必须暴露出属性。这和封装有类似的作用，因为它保护了数据，使我们能够用另一个遵守定律的公民来交换接口。

来吧，我们有一些定律要研究。

### 同一律 (Identity)

```js
const identity1 = compose(sequence(Identity.of), map(Identity.of));
const identity2 = Identity.of;

// test it out with Right
identity1(Either.of('stuff'));
// Identity(Right('stuff'))

identity2(Either.of('stuff'));
// Identity(Right('stuff'))
```

这应该是很直接的。如果我们把一个 Identity 放在 functor 中，然后用 `sequence` 把它翻出来，这就和一开始就把它放在外面是一样的。我们选择 `Right` 作为小白鼠，因为它很容易验证和检查定律。一个任意的 functor 在这里是正常的，然而，在这里使用一个具体的 functor，即定律本身中的 `Identity`，可能会引起一些人的注意。请记住，一个[范畴](https://llh911001.gitbook.io/mostly-adequate-guide-chinese/pages/-M4muCDTslAEcot3ytwW#范畴学)是由其对象之间的变形来定义的，这些变形具有关联构成和同一性。当处理 functor 的范畴时，自然变换就是形态，而 `Identity` 就是，嗯，自身。`Identity` functor 和 `compose` 函数一样，都是很基本的定律。好了，关于 `Identity` 就先到这里，接下来我们看看 [Compose](https://llh911001.gitbook.io/mostly-adequate-guide-chinese/pages/-M4muCDjeKxWItrlsblk#一点理论) 类型：

### 组合 (Composition)

```js
const comp1 = compose(sequence(Compose.of), map(Compose.of));
const comp2 = (Fof, Gof) =>
  compose(Compose.of, map(sequence(Gof)), sequence(Fof));

// Test it out with some types we have lying around
comp1(Identity(Right([true])));
// Compose(Right([Identity(true)]))

comp2(Either.of, Array)(Identity(Right([true])));
// Compose(Right([Identity(true)]))
```

这个定律如人们所期望的那样保留了组合：如果我们交换 functor 的组合，我们不应该看到任何意外，因为组合本身就是一个 functor。我们任意地选择了 `true`、`Right`、`Identity` 和 `Array` 来测试它。像 [quickcheck](https://hackage.haskell.org/package/QuickCheck) 或 [jsverify](http://jsverify.github.io/) 这样的库可以通过模糊测试输入来帮助我们测试这个规律。

作为上述定律的自然结果，我们能够获得[融合遍历](https://www.cs.ox.ac.uk/jeremy.gibbons/publications/iterator.pdf)的能力，这从性能的角度来看很不错。

### 自然 (Naturality)

```js
const natLaw1 = (of, nt) => compose(nt, sequence(of));
const natLaw2 = (of, nt) => compose(sequence(of), map(nt));

// test with a random natural transformation and our friendly Identity/Right functors.

// maybeToEither :: Maybe a -> Either () a
const maybeToEither = (x) => (x.$value ? new Right(x.$value) : new Left());

natLaw1(Maybe.of, maybeToEither)(Identity.of(Maybe.of('barlow one')));
// Right(Identity('barlow one'))

natLaw2(Either.of, maybeToEither)(Identity.of(Maybe.of('barlow one')));
// Right(Identity('barlow one'))
```

这和同一律有点像。如果我们先把类型翻转出来，在外部做一次 natural transformation，那将会和 map 一下 natural transformation 然后再翻转类型得到同样的结果。

这个定律的一个自然的结果就是：

```js
traverse(A.of, A.of) === A.of;
```

从性能的角度看，这也是极好的。

## 总结

*Traversable* 是一个强大的接口，能够让你像有心灵感应的室内设计师一样轻松重新编排类型。我们可以通过不同的顺序达到不同的作用，也可以熨平那些令人讨厌的无法 `join` 的类型皱纹。接下来，我们将一起欣赏函数式编程乃至于代数学本身最强大的接口之一：[Monoids](https://github.com/llh911001/mostly-adequate-guide-chinese/blob/master/ch13.md)。

## 练习

考虑下列元素：

```js
// httpGet :: Route -> Task Error JSON

// routes :: Map Route Route
const routes = new Map({ '/': '/', '/about': '/about' });
```

使用 traversable 接口把 `getJsons` 的类型签名改成 `Map Route Route -> Task Error (Map Route JSON)`

```js
// getJsons :: Map Route Route -> Map Route (Task Error JSON)
const getJsons = map(httpGet);
```

我们现在定义下列校验函数：

```js
// validate :: Player -> Either String Player
const validate = (player) =>
  player.name ? Either.of(player) : left('must have name');
```

使用 traversable 和 `validate` 函数，更新 `startGame` （和它的类型签名），使得只有在所有玩家是有效时才开始游戏。

```js
// startGame :: [Player] -> [Either Error String]
const startGame = compose(map(map(always('game started!'))), map(validate));
```

最终，我们考虑一些文件系统相关的帮助函数：

```js
// readfile :: String -> String -> Task Error String
// readdir :: String -> Task Error [String]
```