实用函数式编程技巧：Combinator Pattern

在实现《React 优化技巧在 Web 版光线追踪里的应用》时，我有个需求是，让循环不是从 start 到 end，而是从中间开始，往两侧延展。实现下面的效果

图片渐进式呈现，不是从上到下，而是从中间展开。

一开始，我是用 for 循环加各种变量去切换，调试起来很痛苦，最后也让我失去了耐心。可能这个需求有很直接的处理办法，不过在当时我没想到。

因此，我从 “编程兵器库” 拿出一个强大的武器，解决了这个小问题。并且发现，这种高射炮打蚊子的场景，很适合作为讲解案例。故有此文。

Combinator Pattern 是 Functional Programming 里的常用模式，Haskell 里的知名解析库 parsec 就采用了这个模式，又名 Parser Combinator。

Combinator 一词有很多种意思。在这里 Combinator Pattern 描述的是，由 Primitives 和 Combinators 组合起来的计算结构。

我需要特别强调 “计算结构” 一词，尽管它不是真正的术语，但我认为它很有传播的价值。我们非常熟悉所谓的程序就是数据结构 + 算法的说法，在写底层代码时，它们确实非常有用。但对于应用层的代码，我们更需要别的视角，因此我想强调计算结构。

计算结构，在我看来，属于算法的特殊写法。同一个算法，有很多不同的编写方式。有一些性能好，有一些代码量少，有一些直观易读；而有一些可组合性好，可推理性高，它们可以呈现出有层次的计算过程。

我们以中间展开的循环算法为例。演示 Combinator Pattern 可以如何呈现出优雅的计算层次结构。

先来讲一下 Combinator Pattern 的第一个组成部分，Constructor。它负责把一个普通的数据，放入计算结构。相当于构造出一种计算，函数类型大致长这样：a -> m a。

a 是任意值，m a 是基于 a 可产生的计算。

这里的 Constructor 跟 ES2015 Classes 里的 constructor 方法以及函数的 prototype 里的 constructor 方法的关系是，后者是前者的其中一个体现。Constructor 表达的是普适的构造，class 里的 constructor 是普适构造里的其中一种，用以构造出该 class 的实例。

而 Combinator Pattern 的第二个组成部分，Combinators。它负责把一种计算结构，转换成另一种计算结构，或者把两个计算结构，合并成一个。不管如何，都是从计算结构到计算结构的转换。函数类型大概长这样：m a -> m b。

m a 是基于 a 可产生的计算，m b 是基于 b 可产生的计算。m a -> m b 则是把基于 a 可产生的计算，转换成基于 b 可产生的计算。

如果你觉得很抽象，很奇怪，看下面的例子感受一下。

正如前面所言，Constructor 和 Combinators 没有定势，全靠我们自行定义，满足条件即可。我们未必要用 Class，我们就定义 iterator 代表一种计算结构，它被调用 next 方法时，就计算出了下一个值。

iterator 可以视为 {next}，它有一个 next 方法用以产生实际的计算。

那么，Constructor 就是把一个 a 变成一个 iterator 的东西。所有 Generator Function 在这里，都是天然的 Constructor。因为 Generator Function 的参数就是 a，返回值是 iterator。因此它满足：a -> {next}。

我们的 incre 函数是一个 iterator 计算结构的 Constructor，你给它 start, end, step 参数，它返回一个 iterator 计算结构，反复调用 next 时，计算出每一个符合条件的值。

我们的 decre 函数也是 iterator 的一个 Constructor，它包含的计算跟 incre 函数反过来，一个是从小到大，一个是从大到小。

我们的 range 函数，也是一个 Constructor，尽管它不是 Generator Function ，尽管它里面用到了其它 Constructor。这不会改变它的函数类型，它依然是根据 start, end, step 参数，构造一个 iterator。它包含的计算结构是，如果 start < end 就是从小到大的计算，反之则是从大到小的计算。

而我们的 toggle 函数，就不只是 Constructor 了。它接受两个 iterator 计算结构，返回一个新的 iterator 计算结构。新的结构包含的计算，是不断地在 a, b 里切换计算，直到消费完所有值。

如果你愿意，可以仿照 React 里所谓的 Higher Order Component 的说法，称之为 Higher Order Constructor，亦即高阶构造器。不过，Combinator 这个词儿对我来说更好。

Constructor 跟 Combinator，都是函数，都返回计算结构（在这里是 iterator），它们的差别在于，Constructor 的参数是非计算结构，而 Combinator 的参数里包含计算结构。这是一种有益的区分。

Constructor :: a -> m a

Combinator :: m a -> m b

有了 range 和 toggle，我们很容易组合出一个新的 Constructor。spread 内部基于 range 和 toggle，实现了在 middle -> start 和 middle -> top 中来回切换的计算结构。

这正是我们想要的中间展开的循环算法。

如你所见，我们并没有在一个函数里，用很多局部变量，在 for 循环里根据各种条件去修改变量值，然后解决一次性问题。我们仅仅是按照函数名如 incre, decre, range, toggle, spread 等所描述的行为，去实现它们罢了。

我们渐进式的解决了好几种问题。它们是通用的，可以在其它场景里被复用。并且 incre, decre, range, toggle, spread 任意一个函数，都符合只做一件事情并做好它的编程原则；任意一个，都是可单独测试的。

我们不再迷失于复杂函数内部的局部变量追踪中，浪费大量调试时间。我们可以很容易根据需求，拓展出新的 Constructor 和 Combinator。比如：

区区 3 行代码，实现了 map 这个 Combinator，它返回的计算结果由 f 参数的函数所指定。在上面的例子里，是把数字加倍。

至此，是否有一种 rxjs 的既视感？

没错，我们还可以很简单地实现 rxjs 里的 operators，比如 filter 和 take。

当多个 Combinators 要一起工作时，我们需要写一个辅助函数 pipe，让它看起来更容易阅读。将来 Pipeline Operators 特性定案后，可以省掉 pipe，用 |> 符号代替。

如你所见，map, filter, take 等 Combinators 代码很简洁，只是做了它该做的事情。

像 concat 这种操作，则更为简单，就两次 for-of + 无脑 yield。

那么，我们这个 iterator 跟 rxjs，究竟什么关系？为什么它们的 API 可以如此一致？

可以很简单的回答这个问题，rxjs 也是 Combinator Pattern。作为 Pattern，它们的 API 相似很正常。

rxjs 的 of, Observable.create 等函数，属于 Constructors。像 concat, merge, combineLatest 等函数，则是 Combinators。所有 Rxjs 的 Operators 都是 Combinators。

所谓的 Operators，它的类型大致是：a -> m b -> m c。而 concat 则是 (m a, m b) -> m c。看似不同。其实，把高阶函数的多个单参数，视为多参数函数的特殊情况。或者把多参数函数，视为多个高阶单参数函数的特殊情况。它们就一致了。无非是互相 curry 或 uncurry 一下，这个过程不产生实质的计算（即最终输出是一样的）。

此外，如果你对比了 rxjs 和我们的 iterator 的计算结构。你会发现，iterator 仅仅有 {next} 的计算。而 rxjs 包含的结构要复杂得多，首先它的 a -> { subscribe } 返回的是可订阅的结构。

subscribe({next, completed, error}) 里又把包含 next, completed, error 三种计算的结构传入，并且返回 unsubscription 可以取消订阅。

因此，rxjs 里包含的计算能力，远比 iterator 里的层次多、能力广。要使用 iterator 实现 rxjs 里的复杂计算，可得自己额外做很多处理工作。

如你所见，在计算结构的考察视角下，我们有了分析一个 library 的实际表达能力的可靠思路。我们知道，并非两个 API 长得像，就表示它们具备同等的能力。

至此，我们知道了 Constructor 和 Combinator 分别是什么，那 Primitives 又是什么呢？

它正是 Combinator Pattern 里最有趣的部分。

在前文里，我们看到了，可以不断地编写出新的 Constructor 和 Combinator。只要它们满足 a -> m a 和 m a -> m b 的类型跟行为要求。这是一个开放的视角。我们也看到了，可以在一个 Constructor 或 Combinator 使用其它 Constructor 和 Combinator。此时，我们有了一个收敛视角。

哪些 Constructor 和 Combinator 不能由其它 Constructor 和 Combinator 组合出来？

我们能否找到一批 Constructors 和 Combinators，通过它们，可以构造出其它的 Constructors 和 Combinators？

如果能，我们可以称之为 Primitives。

举个例子，我们的 incre 和 decre 里包含的计算过程是如此相似，它们谁才是 Primitives？

答案是，有了 reverse 这个 Combinator，实现 incre 跟 decre 任意一个，都一个实现另一个。

Primitives 不全是天生的，必然的；很多情况下，它跟我们自身的选择有关。这并非显得任性与儿戏，这是一个宝贵的特性。有一些 Primitives 比较难实现，而另一些比较简单，它们可以互相表达对方。因此我们有机会选择实现简单的那个。

更有趣的是，有时一个 Constrcutor 即便能由其它 Primitives 和 Combinator 组合出来，我们也可以选择手动实现。

比如，当我们用 incre 和 reverse 去实现 decre 时，它尽管得到了一样的输出结果，但开销不同。reverse 内部完全启用了 incre 里的所有计算，然后进行反向输出。它没法说只要第一个，就只产生一次计算。而手动实现的 decre，可以做到按需计算。

我们可以认为，Primitives 和 Combinators，给了我们一些 Free API，我们能免费或者廉价地组合出更复杂的计算结构。但 Free 是有代价的。在快速原型开发阶段，我们可以用 Combinator Pattern 迅速得到可用的计算结构；等到功能稳定，则进行重构，将部分 Constrcutor 和 Combinators 用手动的方式去优化。

如上所示，我们不再使用 range 和 toggle 去构造 spread，我们直接把它们包含的计算过程内联 (inline) 到里面，减少了性能开销。

我们惊讶地发现，这个重构版本，不正是一开始我们用局部变量和循环想得到的吗？当时我们调试很久而无所得，如今只是解开一些 Constructor 和 Combinators 就轻易得到了。这真是一个神奇的过程。

反思一下，我们会发现，直接使用多个局部变量和循环去实现，实质上是一个用蛮力去试错、摸索出 spread 需要多少个计算的过程。而多个局部变量之间的互相影响，却让代码难以调试。

如果采用 Combinator Pattern，我们可以隔离出很多 Constructor 和 Combinator，它们代码量少，可单独测试，可组合出更复杂的计算结构。当我们使用它们组合出了 spread 时，我们就知道 spread 里包含的必要计算过程是什么，然后进行清晰的、有节奏的、有规划的重构优化。

并且，凭借我们对 Primitives 之间的关系的知识，我们还可以推理出新的思路。比如，我们已经知道，incre 和 decre 可以通过 reverse 互相实现对方。因此，我们不需要追踪两个局部变量 incre 和 decre，只需要追踪一个，然后通过 reverse / 取反等操作，衍生出另一个即可。

如上所示，我们只追踪了 count 这一个局部变量，通过 +offset 和 -offset 的互为反向操作得到 incre 和 decre，实现了同样的算法。

从之前抓耳挠腮，盲目试错无果，到现在我们能用 3 种不完全相同的方式实现 spread 函数。这正是 Combinator Pattern 的强大之处。它作为一个方法论，能引领和启发我们解决之前解决不了的问题，以及更好地解决已经解决的问题。

而这篇文章所展示的，只是函数式编程里的冰山一角。更多好用的武器，等待我们去学习。可以通过学习 Haskell 等函数式语言，领会更多技巧。然后应用于前端开发等日常工作中，优化我们的代码。

如果你想知道 Haskell 里写起来大概是什么样，上图是一个简单粗暴的翻译。把 JS 的版本翻译到 Haskell。

想了解更多 Combinator Pattern 的应用案例，可以点击《揭秘 Vue-3.0 最具潜力的 API》查看内容，里面将 reactivity value 视为一种计算结构，并组合出了 reactivity view 等更复杂的计算结构。