第 12 章: 遍历

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

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

类型与类型

让我们整点怪活：

// 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 （分别在各自空闲时间完成任务后再返回）要好操作得多。

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

// 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 重新编排编排类型：

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 对它的参数有一点挑剔。它看起来像这样子：

// 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，会如何实现它：

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

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

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

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) 则会是一个服务端的验证。类型可以互换，为我们带来不同的作用。

// 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 是如何形成的。

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 中正常工作。这是一个很棒的例子，展示了那些抽象能够如何帮助我们写出高度通用的代码，仅仅依赖于一点点假设（而且这些假设可以通过类型系统声明和检查！）。

类型的华尔兹

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

// 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 倾向于以一种互操作、可重用的方式捕获我们想做的大部分事情，而不必像单个类库那样为某一类型重新发明这些函数。

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

// 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)

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，可能会引起一些人的注意。请记住，一个范畴是由其对象之间的变形来定义的，这些变形具有关联构成和同一性。当处理 functor 的范畴时，自然变换就是形态，而 Identity 就是，嗯，自身。Identity functor 和 compose 函数一样，都是很基本的定律。好了，关于 Identity 就先到这里，接下来我们看看 Compose 类型：

组合 (Composition)

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 或 jsverify 这样的库可以通过模糊测试输入来帮助我们测试这个规律。

作为上述定律的自然结果，我们能够获得融合遍历的能力，这从性能的角度来看很不错。

自然 (Naturality)

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 然后再翻转类型得到同样的结果。

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

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

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

总结

Traversable 是一个强大的接口，能够让你像有心灵感应的室内设计师一样轻松重新编排类型。我们可以通过不同的顺序达到不同的作用，也可以熨平那些令人讨厌的无法 join 的类型皱纹。接下来，我们将一起欣赏函数式编程乃至于代数学本身最强大的接口之一：Monoids。

练习

考虑下列元素：

// 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)

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

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

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

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

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

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

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