map, reduce もいいけど transduce もね

続編もよければどうぞ

- [衝撃レポート！！map, reduce の本質にせまる！](https://qiita.com/41semicolon/items/7f31297dd104f97c61b0)

# 市民権をえた map, filter, reduce
最近はどの言語でも配列やストリームにおいて map, filter, reduce が使われすっかり市民権を得た感じがある。一方、transducer はあんまり使われているのを聞いたことがない気がする。

本稿では transducer について少しだけまとめる。言語はJavaScriptを使う。

# 解きたい課題

メソッドチェーンで map, filter をつなげて処理を書くと、中間状態として無駄な配列がでてきてしまう。

```js
targetList.filter(isHoge) //中間配列1つめ
  .filter(isMoge) //中間配列2つめ
  .map(doFoo) //中間配列3つめ
  .map(doBar) //中間配列4つめ 
  .map(doBaz) 
```

でもよく考えてみると、そんなメモリは不要。手続き的に書くとこんな感じになる。若干読みにくいけど。

```js
const result = [];
for (item of targetList) {
  if (!(isHoge(item) && isMoge(item)))
    continue;
  result.push(doBaz(doBar(doFoo(item))));
}
```

map, filterをつなげたように読みやすくて、手続き的に書くような省メモリに実現できたら、それはとてもうれしい。transducer ならそれができる。先走って答えを書くと、こう。Ramda のライブラリを使っている。

```js
const xForm = R.compose(
 R.filter(isHoge),
 R.filter(isMoge),
 R.map(doFoo),
 R.map(doBar),
 R.map(doBaz)
);
R.into([], xForm, targetList);
```

仕組みと、どの部分が transducer なのかちょっと解説しよう。

# map, filter はreduceで書ける

まずは、map と filter は reduce で書き換えることが出来ることを知ろう。

```js
// arr.map(doFoo) is equivalent to
arr.reduce((acc,x) => acc.concat(dooFoo(x)), []);
// arr.filter(isHoge) is equivalent to
arr.reduce((acc,x) => isHoge(x) ? acc.concat(x) : acc)
```
少し一般化してこうもかける

```js
//map
const concatReduce = (acc, x) => acc.concat(x);
const transduceByMap = mapper => reduceFunc => (acc, x) => (
 reduceFunc(acc, mapper(x))
)
arr.reduce(transduceByMap(doFoo)(concatReduce), [])

//filter
const transduceByPred = pred => reduceFunc => (acc, x) => (
 pred(x) ? reduceFunc(acc, x) : acc
)
arr.reduce(transduceByPred(isHoge)(concatReduce), [])
```

だから先ほどの例は reduce のチェーンに書き換えられる。

```js
const concatReduce = (acc, x) => acc.concat(x);
targetList
  .reduce(transduceByPred(isHoge)(concatReduce), [])
  .reduce(transduceByPred(isMoge)(concatReduce), [])
  .reduce(transduceByMap(doFoo)(concatReduce), [])
  .reduce(transduceByMap(doBar)(concatReduce), [])
  .reduce(transduceByMap(doBaz)(concatReduce), [])
```

こうしてみると、map と filter はすごく似ている構造をしている。そこで`transduceByPred(isHoge)` とか `transduceByMap(doFoo)` に名前を付けたくなる。これが transducer と呼ばれるものになる。transducer は畳み込み関数を受け取り、畳み込み関数を返す。例では `concatReducer` を渡している。

transducer は以下のようなシグニチャを持つ。入力と出力が同じ型なのでいかにも関数合成できそうな気がする。

> transducer :: (acc, x -> result) -> (acc, x -> result)

そして実際に関数合成できる。例えば filter型同士の合成では、以下の二つが同じ結果になるのは自明だろう。

```js
const x1 = transduceByPred(isHoge)
const x2 = transduceByPred(isMoge)
targetList
  .reduce(x1(concatReduce), [])
  .reduce(x2(concatReduce), [])

targetList
  .reduce(x2(x1(concatReduce)), [])
```

同様に、 map型同士の合成では、以下の二つは同じ結果になる。順序に注意。

```js
const x1 = transduceByMap(doFoo)
const x2 = transduceByMap(doBar)
targetList
  .reduce(x1(concatReduce), [])
  .reduce(x2(concatReduce), [])

targetList
  .reduce(x1(x2(concatReduce)), [])
```

これを繰り返すと、最初の例はこうなる

```js
const xForm = R.compose(
  transduceByPred(isHoge),
  transduceByPred(isMoge),
  transduceByMap(doFoo),
  transduceByMap(doBar),
  transduceByMap(doBaz),
)
targetList.reduce(xForm(concatReducer), []);
```
めでたしめでたし。



参考

https://github.com/cognitect-labs/transducers-js

https://medium.com/@roman01la/understanding-transducers-in-javascript-3500d3bd9624