map, reduce もいいけど transduce もね

続編もよければどうぞ

• 衝撃レポート！！map, reduce の本質にせまる！

市民権をえた 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), []);

めでたしめでたし。

参考