Edited at

map, reduce もいいけど transduce もね

More than 1 year has passed since last update.

続編もよければどうぞ


市民権をえた map, filter, reduce

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

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


解きたい課題

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

targetList.filter(isHoge) //中間配列1つめ

.filter(isMoge) //中間配列2つめ
.map(doFoo) //中間配列3つめ
.map(doBar) //中間配列4つめ
.map(doBaz)

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

const result = [];

for (item of targetList) {
if (!(isHoge(item) && isMoge(item)))
continue;
result.push(doBaz(doBar(doFoo(item))));
}

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

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 で書き換えることが出来ることを知ろう。

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

少し一般化してこうもかける

//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 のチェーンに書き換えられる。

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型同士の合成では、以下の二つが同じ結果になるのは自明だろう。

const x1 = transduceByPred(isHoge)

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

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

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

const x1 = transduceByMap(doFoo)

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

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

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

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