Day 07 - Transduce I

从一个简单的问题开始

假设我们目前有一组长度为一百万的阵列，需要将阵列内的每个数值乘三并且只保留偶数，那我们会如何实作这简单的问题?

根据上面的问题，我们在实作前需要准备

1 长度为一百万的阵列

const makeArr = (randomCeil) => (len) =>
  Array.from({ length: len }, (v, i) => Math.floor(Math.random() * randomCeil));

const arrOfMillion = makeArr(100)(1e6);

2 将每个数值乘三的函式

const tripleIt = (num) => num * 3;

3 只保留偶数的函式

const isEven = (num) => num % 2 === 0;

接来开始想实作方式吧!

在不认识 Transduce 以前

在我还不认识 Transduce 这个概念前，马上想到的方法可能就是用

1 Array.prototype.map 与 Array.prototype.filter

// code.1

const result = arrOfMillion.map(tripleIt).filter(isEven);

2 或是 forEach

// code.2

const result = [];

arrOfMillion.forEach((item) => {
  const tripleItem = tripleIt(item);

  if (isEven(tripleItem)) {
    result.push(tripleItem);
  }
});

虽然这两种方法都可以解决问题，但各自都有优缺点:

1. 第一种方法

   1. 优点: 可读性佳。
   2. 缺点: 执行速度慢。(由於会让阵列跑了两次回圈。 map, filter 都会各跑一次，时间复杂度 O(2n)，用更直觉一点的想，跑了两次当然会拖慢程序的效能。)

2. 第二种方法

   1. 优点: 执行速度快。(只需要跑一次回圈)
   2. 缺点: 可读性差，且不容易进行复用。

那有没有一个解决方法是可以拥有第一种方法的可读性，且程序的执行速度跟第二种方式一样快!

Tranduce 就是集结了两方法优点的概念。 其是一个比较进阶的概念，笔者也是理解与消化了许久才了解其中的奥秘，接下来我们就一步一步探索着个有趣的概念吧!

如何使用 Transduce

与其先知道是如何实作，不如从如何使用开始，接下来使用的范例是使用 Ramda 提供的 tranduce 函式去解决一开始提到的问题。

Ramda 的 transduce 共需要放入四个参数

1. transducer: compose 一个或多个 transformer 函式
2. reducer: 为一个函式须传入 accumulator 跟 currentValue， 并将 currentValue 累加到 accumulator 的运算函式。
3. initialValue: 初始值。
4. data: 想要进行处理的资料。

// code.3

const R = require('ramda');

const transducer = R.compose(R.filter(isEven), R.map(tripleIt));

const reducer = (acc, val) => (acc.push(val), acc); // same as (acc, val) => { acc.push(val); return acc }

const result = R.transduce(transducer, reducer, [], arrOfMillion);

很清楚地可以看到，程序码可读性与第一种方法相差不远。但如何去评测其是否也拥有第二种方法的效能?

效能评比

简易的效能工具

const timer = (marked, fn) => {
  console.time(marked);
  fn();
  console.timeEnd(marked);
};

在来就是分别去比较，而比较的结果如下(秒数依电脑而异，但结论不会相差太远)

timer('first way - map & filter', () => {
  /** run code.1 */
});

timer('second way - forEach', () => {
  /** run code.2 */
});

timer('third way - transduce', () => {
  /** run code.3 */
});

大家应该已经发现，用 transduce 这个概念不但可以兼顾链式写法的可读性，也可以具有比 imperative (forEach) 写法更好的效能，更不用说是本身就自带 FP 的可复用性。

Transduce 这个概念到底是如何实作的!!

其实 Transduce 就是一个不断抽象化的过程，而笔者整理出了其抽象化的四个步骤，但在解释这四个步骤前，我们需要知道一些名词

名词解释

1. reducer 为一个函式须传入 accumulator 跟 currentValue， 并将 currentValue 累加到 accumulator 的运算函式。

而 JS 任意的资料结构都可以组成相对应的 reducer，从 字串 到 物件 都有自己的 reducer 函式。

const reducer = (acc, val) => acc + val;

// string
reducer('Hello', ', World'); // Hello, World

// number
reducer(5, 20); // 25

// object
const objectReducer = (acc, val) => ({ ...acc, ...val });

const myInfo = {
  name: 'Jing',
  email: '[email protected]',
};

objectReducer({ ...myInfo }, { phone: '0912345678' }); // {name: "Jing", email: "[email protected]", phone: "0912345678"}

而为什麽会被称为 reducer 呢? 大家想想看 Array.prototype.reduce，所放入的第一个函式不就是 (acc, val) => {/** do something, then concat*/ } 吗!!

const arrReducer = (acc, val) => [...acc, val];

[2, 3, 4].reduce(arrReducer, [1]); // [1, 2, 3, 4]

2. Transformer 函式为传入 Array.prototype.map，也就是将回圈时传入的值透过 transformer 去进行值的转换。

[1, 2, 3, 4].map(tripleIt); // [3, 6, 9, 12]

tripleIt 这个就是 transformer，将其值进行三倍的转换。

3. Predictor 函式为传入 Array.prototype.filter，在回圈中筛选通过 predictor 函式的值。

[1, 2, 3, 4].filter(isEven); // [2, 4]

isEven 这个就是 predictor，筛选其为偶数的数值。

步骤一，用 reduce 实践 map 与 filter

可以想像一下，如果现在 JS 语法已经不在支援， map 与 filter 也不能直接用 forEach 去实作，简单来说就只能用 Array.prototype.reduce

那要如何用 reduce 去实作 map 跟 filter 呢?

const map = (transformer, array) =>
  array.reduce((acc, val) => [...acc, transformer(val)], []);

const filter = (predicator, array) =>
  array.reduce((acc, val) => (predicator(val) ? [...acc, val] : acc));

const result = filter(isEven, map(tripleIt, [1, 2, 3, 4]));

但这样若想要进行多次的 map 或 filter 不就会变得难以阅读， 如

filter(isEven, map(tripleIt, filter(isEven, map(tripleIt, [1, 2, 3, 4]))));

这样就没办法快速知道这段程序码原来是将 array 各个 item 先乘 3 取偶数 再乘 3 再取偶数。

有没有甚麽方法可以先将 array 的语法抽象画出来，并用 reduce 进行链式 的写法。

接下来我们就要再抽象化，达到下例的写法

[1, 2, 3, 4]
    .reduce((acc, val) => map(tripleIt)(acc, val), [])
    .reducer(((acc, val) => filter(isEven)(acc, val), []); // [6, 12]

步骤二，将 Array 相关的语法 抽象化

要进化成上述的写法，就需要将 map 跟 filter 进行将 array 语法的抽象化，让 reduce 本身用链式的方法去执行。

const map = (transformer) => (acc, val) => [...acc, transformer(val)];

const filter = (predicator) => (acc, val) =>
  predicator(val) ? [...acc, val] : acc;

const result = [1, 2, 3, 4]
  .reduce(map(tripleIt), []) // same as `(acc, val) => map(tripleIt)(acc, val)`
  .reduce(filter(isEven), []); // same as `(acc, val) => filter(isEven)(acc, val)`

接下来大家应该都有注意到了， 第二步骤的 map 与 filter 好像都有相似之处，发现了吗?

map 函式的 [...acc, transformer(val)] 与 filter 函式的 [...acc, val] 这不就是 reducer 嘛!

所以我们可以将其抽象出来，

步骤三，将 Reducer 抽象化

const map = (transformer) => (reducer) => (acc, val) =>
  reducer(acc, transformer(val));

const filter = (predicator) => (reducer) => (acc, val) =>
  predicator(val) ? reducer(acc, val) : acc;

const reducer = (acc, val) => [...acc, val];

接下来我们就可以将我们的 map 与 filter 使用方法改写成这样

const transducer = map(tripleIt)(filter(isEven)(reducer));

const result = [1, 2, 3, 4].reduce(transducer, []); // [6, 12]

分析一下上述的函式

首先 reduce 的 callback 触发了 (acc, val) => {/** your code */}，进而启动了 transducer 这个函式

第一个 acc 跟 val 传入 reducer([], 1)，先启动了 map， 经过数值乘 3 後，输出 reducer([], 3)

接下来 filter 被启动了，并且接收了 reducer([], 3)，作为其输入，但 3 不是偶数，故 filter 回传 [] 结束第一个数值的运算，之後以此类推。

到这里大家不难发现:

Transducer 就是 reducer compose起来的方法，也可以称它为 higher-order reducer， 其需要将 reducer 传入，且输出另一个 reducer。

如果还不是很清楚的，可以透过这个好用的视觉化网站，更清晰的理解过程。

步骤四，打造 composable 的 Reducer

相信到这里大家应该都已经非常清楚地知道 transducer 整个运作流程，但还差临门一脚

const transducer = map(tripleIt)(filter(isEven)(reducer));

这段程序码好像可以进行 compose，我们先将这段程序码整理一下

const tripleMapper = map(tripleIt);
const isEvenFilter = filter(isEven);

const transducer = tripleMapper(isEvenFilter(reducer));

而 compose 不就是将 f2(f1(x)) 转换成 compose(f2, f1)(x) 的概念吗!

const compose = (...functions) =>
  functions.reduce(
    (acc, fn) => (...args) => acc(fn(...args)),
    (x) => x,
  );

const transducer = compose(isEvenFilter, tripleMapper);

const result = [1, 2, 3, 4].reduce(transducer(reducer), []); // [6, 12]

再将其转换成需要传入 transducer, reducer, initialValue 与 array 的函式

const transduce = (transducer, reducer, initialValue, array) =>
  array.reduce(transducer(reducer), initialValue);

结论

终於大功告成了，看起来我们可以对比一下使用 Ramda 的 transduce 跟我们目前写的样子

1. Ramda 的 transduce

// code.3

const R = require('ramda');

const transducer = R.compose(R.filter(isEven), R.map(tripleIt));

const reducer = (acc, val) => (acc.push(val), acc); // same as (acc, val) => { acc.push(val); return acc }

const result = R.transduce(transducer, reducer, [], arrOfMillion);

2. 我们的 transduce

const compose = (...fns) =>
  fns.reduce(
    (acc, fn) => (...args) => acc(fn(...args)),
    (x) => x,
  );

const map = (transformer) => (reducer) => (acc, val) =>
  reducer(acc, transformer(val));

const filter = (predicator) => (reducer) => (acc, val) =>
  predicator(val) ? reducer(acc, val) : acc;

const transduce = (transducer, reducer, initialValue, array) =>
  array.reduce(transducer(reducer), initialValue);

const transducer = compose(filter(isEven), map(tripleIt));

const reducer = (acc, val) => (acc.push(val), acc);

const result = transduce(transducer, reducer, [], arrOfMillion);

看起来是成功的复刻了 Ramda 的 transduce 函式，这也让我们体会到了 transduce 就是不断的抽象化的一个过程的概念，并且浓缩到兼顾可读性与复用。

小结

下一篇会讲到如何将现在的 transduce 写成让不同资料型别也可以使用的函式。

NEXT: Transduce II

Reference

1. Transducing

2. Transducer Explained

3. MAGICAL, MYSTICAL JAVASCRIPT TRANSDUCERS