Help us understand the problem. What is going on with this article?

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

41semicolon
低燃費FIRE。論理・計算関連のトピックに興味があります。JavaScript,Python,Rust,F#,Coq
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした