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

おおげさなタイトルでなんかすまん

目的と結論

• 目的
  map, reduceを納得して使う

• 結論
  map, reduce の本質は、イテレーション可能なデータソースを対象にしたデータの加工である。map は加工の際に状態を持てないため複雑な作業はできないが簡単に扱える。reduce は状態を持てる分複雑なデータ加工が可能であるが、出力データの構築という本質と外れた操作を含む。この出力データの構築の部分をより具体化させると、reduce は into という操作になり、一般化すると reduce は transduce という操作になる。

結論に興味がある人は読んでほしい。最近 transduce に興味を持った人には特に得るものが多いと思う。

姉妹編:
map, reduce もいいけどtransduce もね
https://qiita.com/41semicolon/items/666a3ff1c226828ecdb2

前提・表記

map, reduce を苦なく使える人向け。関数型プログラミングの知識があるとなおよい。

本稿は JavaScriptで記述する。以下のように map、reduceを定義し、断りが無い場合この実装を指すものとする。本稿では仮引数 xs をイレモノと呼ぶ。これは比喩表現ではなくファンクターないしトラバーサブルの別称である（専門用語をつかいたくない）。

const map = (mapper, xs) => xs.map(mapper)
const reduce = (reducer, initial, xs) => (
  xs.reduce(reducer, initial)
)

map、reduceに引き渡す関数を mapper, reducer と呼ぶ。今後断りなく本文で使う。また、mapper, reducer の仮引数 x をデータと呼ぼう。つまり、イレモノのなかにデータが入っている、というイメージである。[1, 2, 3]では、Arrayがイレモノであり、2がデータである。 reducerの仮引数 accはアキュミュレータと呼び、今後断りなく本文で使う。

//データを2乗するmapper
const sampleMapper = (x) => x **2; 
//アキュムレータにデータを足し上げるreducer
const sampleReducer = (acc, x) => acc + x; 

本章で定義した用語: map, mapper, reduce, reducer, イレモノ, データ, アキュムレータ

map の描像

データを 2倍する mapper によって[1, 2, 3] -> [2, 4, 6] となる例を念頭にしながら map を整理しよう。

まずは、入出力。map は入力と出力のイレモノが同じである。Arrayが入力ならArrayが出力だ。出力を文字列にするとかの操作はできない。イレモノを変えずにデータを変えるというのが map の性質の一つと言える。

続いて、手続き型との比較。手続き的に map と同等のコードを書くとすると、以下のようになる

const myMap = (mapper, xs) => {
  const ret = [];
  for (x of xs) { // 1. データの取り出し
    const transformed = mapper(x) // 2. データの変換
    ret.push(transformed) // 3. データの詰め込み
  }
  return ret
}

コメントにも記載したように、本質的な処理として3つのフェーズが存在する。一つはイレモノからデータを取り出すフェーズ、二つ目はデータを変換させるフェーズでありmapper がその役目を担う。三つ目は変換したデータを出力先に詰め込むフェーズ。取り出すフェーズと詰め込むフェーズは map 関数の内部で行われる。mapper はデータを変換することのみに焦点があり、データがどのように来て、変換したデータがどのように詰め込まれるかについては関知しない。

データ加工の種別についても言及が必要だろう。mapper はデータを次々と加工していくが、データ同士を組み合わせるというタイプの加工はできないし、しない。mapperは状態を持たないと言い換えてもいいかもしれない。

本章のまとめ

• map では、入力と出力のイレモノの型は変わらない
• map ＝「取り出し」＋「加工」＋「詰め込み」
• mapper は加工専門、イレモノを意識しない
• mapper は状態をもたない処理しかできない

reduce の描像

整数データを整数型のアキュミュレータに足しこむ reducer によって、[1, 2, 3] -> 6 となるreduce を念頭にしながら、reduceを整理しよう。

まずは、入出力。入力はイレモノであるが、出力はイレモノに制限されない。出力をイレモノにしてもよいし、例のように整数にしてもよい。

続いて手続き型との比較。手続き的に同等のコードを書くと以下のようになる。

const myReduce = (reducer, initial, xs) => {
  let acc = initial; // 1.アキュムレータの初期化
  for (x of xs) { // 2. データの取り出し
    acc = reducer(acc, x) //3. データを元にアキュムレータを加工
  }
  return acc // 4. アキュムレータの書き出し
}

コメントにも記載したが、本質的に4つのフェーズがある。1つ目は最初に1回だけ行われるアキュムレータの初期化である。2つ目はデータの逐次取り出しである。3つ目は取り出したデータを使ったアキュムレータの加工であり、4つ目は最後に行われるアキュムレータの書き出しである。reducerは3番目のフェーズを担当する。

map と違って reduceはデータをアキュムレータというイテレーションのスコープより長寿命な変数を参照できるので状態を持った処理が可能である。

本章のまとめ

• reduce の出力はイレモノである必要がない
• reduceの描像＝「初期化」＋「取り出し」＋「加工」＋「詰め込み」
• reducer は状態を持った処理ができる

中間報告

mapもreduceもイレモノの中のデータを加工するために使われる。map は状態を持たない処理しかできない。reduce は状態を持った処理を実現できる。機能性でみれば reduceは mapの上位互換であるが、その分 reduce の方が実装がやっかいであると言える。

map も reduceも、イレモノからデータを取り出す部分を考慮しなくて済むように工夫がされている。つまり、mapper, reducerの実装さえすればよいように設計されている。ただ、この観点からみると、reducer のAPI に100点満点をあげるわけにはいかない。アキュムレータは、最終的に出力になる変数である。reducer がアキュムレータの更新を担うということは、出力を意識した実装になってしまっているからだ。

その点を深掘りしていこう。

reducer の分解

前章で述べたように、reducer には二つの担務がある。一つはデータの加工と、もう一つは加工したデータを使ったアキュムレータの更新だ。具体的として、よく似た二つの reduce を考えよう。[1, 2, 3] -> 'one two three' と [1, 2, 3] -> ['one', 'two', 'three']を考える。

よく似た二つのreducer.js

const dict = ['zero', 'one', 'two', 'three'];
// [1,2,3] -> 'one two three'
const translateString = (acc, x) => [acc, dict[x]].join(' ');
// [1,2,3] -> ['one', 'two', 'three']
const translateArray = (acc, x) => acc.concat(dict[x]);

二つのreducer に共通するのは翻訳という部分である。一方異なるのは、アキュムレータが文字列であるか、Arrayであるかという点である。これを踏まえて以下のように reducer を変形してみよう。

reducerの分解.js

const translate = (acc, x) => dict[x];
const intoArray = (acc, x) => acc.concat(x);
const intoString = (acc, x) => [acc, x].join(' ');
// rewrite translateString to
const intoStringTranslate = (acc, x) => intoString(acc, translate(acc, x));
// rewrite translateArray to
const intoArrayTranslate = (acc, x) => intoArray(acc, translate(acc, x));

このように、一般に reducer は、データ加工部(translate) とアキュムレータ更新部(intoString, intoArray) に分解することができる。前者は出力の型に依存しない部分であり、後者が出力に依存する部分である。

データ加工は変数名として xForm が当てられることが多い。今回の例では、こんな感じ (注：この表現はナイーブすぎる。あくまで気持ちだと思ってほしい。正確には補足1. で示すようにtransducer に変換しなくてはならない)

const xForm = translate;

実際には翻訳して、 大文字にして、などと加工をつなげる＝関数合成することが多いので以下のように構成するのが一般的だ。

const xForm = x => addExplametion(toUpper(translate(acc, x)));

本章のまとめ

• reducer＝「データ加工」＋「アキュムレータ更新」

reduce から into へ

前章の考察を受けて、reduce に立ち返ってみよう。今や私たちは reduce がデータ加工部と出力更新部に分かれることを知っている。したがって、reduce をもう少し具体的な形で再定義できる。

前章の場合を考えよう。この場合、reduce をより具体化したintoA, intoSという形で再定義できる。出力先のことを知っているため、もはや initial は必要ない。

// reduce の再定義
const intoA = (xForm, xs) => ( // no initial!
  reduce((acc, x) => intoArray(acc, xForm(acc, x)), [], xs)
);
const intoS = (xForm, xs) => ( // no initial!
  reduce((acc, x) => intoString(acc, xForm(acc, x)), '', xs)
);

こんな風につかう。使い方は簡単。

const xf1 = (acc, x) => translate(acc, x);
console.log(
  intoA(xf1, [1, 2, 3]),
  intoS(xf1, [1, 2, 3]),
);

好みに応じて intoA と intoS を一つの関数 into にして、引数でどちらの動作にするかを動的に変更してもいいだろう。例えば、Ramdaのintoの実装では第1引数に配列や文字列を渡すことで、どのタイプの reduce が行えるかを切り替えている。

このように、reduce の担う二つの担務（データ加工、出力処理）を明確にし、出力処理を切り出すことで reduce はより見通しのよい into として再定義することができる。

本章のまとめ

• reduce は into で再定義できる

reduce から transduce へ

前章では、アキュムレータ更新の方法が与えられた場合、reduce は into と呼ばれるより具体的で簡潔で合目的な操作に変換することをみた。本章ではその逆、つまりアキュミュレータ更新の方法自体を入力にすることで、reduce をより一般的な形で定式化しよう。この操作は transduce と呼ばれる。

エッセンスは上記のとおりなのでいきなり実装を示す。

// transduceの実装
const transduce = (xForm, finto, initial, xs) => {
  const rFunc = (acc, x) => finto(acc, xForm(acc, x));
  return reduce(rFunc, initial, xs);
};

// 使用例
const xf = (acc, x) => translate(acc, x);
const fiA = (acc, x) => acc.concat(x);
const fiS = (acc, x) => [acc, x].join(' ');
console.log(
  transduce(xf, fiS, '', [1, 2, 3]), // ->  one two three
  transduce(xf, fiA, [], [1, 2, 3]), // ->  [ 'one', 'two', 'three' ]
);

本章のまとめ

• reduce は transduce で再定義できる

まとめ

お疲れ様。大体終わり。まとめよう。と言っても冒頭に記載した内容を繰り返すだけになる。

map, reduce の本質は、イテレーション可能なデータソースを対象にしたデータの加工である。map は加工の際に状態を持てないため複雑な作業はできないが簡単に扱える。reduce は状態を持てる分複雑なデータ加工が可能であるが、出力データの構築という本質と外れた操作を含む。この出力データの構築の部分をより具体化させると、reduce は into という操作になり、抽象化すると reduce は transduce という操作になる。

補足1: この記事の実装はクソである

説明をある程度簡略化するため、into, transduce の実装がクソである。動きはするが理論的に微妙に間違えている。成熟したライブラリとして Ramda を使うべきだ。先ほどの翻訳の例をRamdaで書き換えるとこうなる。本投稿を読んだ人なら一目でなにをやっているのかがわかるだろう。

const R = require('ramda');

const dict = ['zero', 'one', 'two', 'three'];
const translate = x => dict[x];
const xForm = R.map(translate);
const xForm2 = R.compose(R.map(translate), R.map(R.toUpper));

console.log(
  R.into([], xForm, [1, 2, 3]), // -> [ 'one', 'two', 'three' ]
  R.into([], xForm2, [1, 2, 3]), // -> [ 'ONE', 'TWO', 'THREE' ]
  R.into('', xForm, [1, 2, 3]), // -> 'onetwothree'
  R.into('', xForm2, [1, 2, 3]), // ->'ONETWOTHREE'
);

const arrayInto = R.flip(R.append);
const stringInto = R.concat
console.log(
  R.transduce(xForm, arrayInto, [], [1, 2, 3]), // -> [ 'one', 'two', 'three' ]
  R.transduce(xForm2, arrayInto, [], [1, 2, 3]), // -> [ 'ONE', 'TWO', 'THREE' ]
  R.transduce(xForm, stringInto, '', [1, 2, 3]), // -> 'onetwothree'
  R.transduce(xForm2, stringInto, '', [1, 2, 3]), // -> 'ONETWOTHREE'
);

私の実装は学習以外では使わないように。上述のように全てRamdaで代替可能である。

xFormの型が私の実装とRamda の実装で違う。Ramda では上述のように xForm=R.map(translate)。となる。R.map は mapper を受け取ると、 transducer として振る舞えるように tranceducer protocol を実装したオブジェクトを返す。これにより、R.transduce の引数として渡したときに、きちんと動くようになっている。R.transduce を使いたいときは、tranceducer protocolに基づいた オブジェクトを渡すようにしなければいけないが、私の実装ではそれをさぼっている、（というかそもそも関数を返してないのでtransduceすら名乗ってはいけない）

補足2: 何がうれしいの？

理論的には、二つの異なる概念を分離できたのでうれしいのだが、前章の例を見る限り、実用的でないと思われるかもしれない。

実用面で訴求するには、mapとfilterを関数合成できるとかどうだろう？map, reduce もいいけど transduce もね でも書いたが。配列の中で、偶数で正のものを選んで、100倍したのちに1を足す。

const R = require('ramda');
const xForm = R.compose(
  R.filter(d => d % 2 === 0),
  R.filter(d => d > 0),
  R.map(d => d * 100),
  R.map(R.add(1)),
);
console.log(
  R.into([], xForm, R.range(-10,10)), // -> [ 201, 401, 601, 801 ]
);

本稿では触れなかったが map と filter はどちらもtransducer 足りうる。

補足3: おまけ

遊べるように、Node ですぐに実行できるようなファイルをいかにはる。

const map = (mapper, xs) => xs.map(mapper);
const reduce = (reducer, initial, xs) => (
  xs.reduce(reducer, initial)
);
const myMap = (mapper, xs) => {
  const ret = [];
  for (x of xs) {
    const transformed = mapper(x);
    ret.push(transformed);
  }
  return ret;
};
const myReduce = (reducer, initial, xs) => {
  let acc = initial;
  for (x of xs) {
    acc = reducer(acc, x);
  }
  return acc;
};
console.log(
  map(d => d * 2, [1, 2, 3]),
  reduce((acc, x) => acc + x, 0, [1, 2, 3]),
  myMap(d => d * 2, [1, 2, 3]),
  myReduce((acc, x) => acc + x, 0, [1, 2, 3]),
);

const dict = ['zero', 'one', 'two', 'three'];
const translateString = (acc, x) => [acc, dict[x]].join(' ');
const translateArray = (acc, x) => acc.concat(dict[x]);
const translate = (acc, x) => dict[x];
const intoArray = (acc, x) => acc.concat(x);
const intoString = (acc, x) => [acc, x].join(' ');
const intoStringTranslate = (acc, x) => intoString(acc, translate(acc, x));
const intoArrayTranslate = (acc, x) => intoArray(acc, translate(acc, x));

console.log(
  reduce(translateString, '', [1, 2, 3]),
  reduce(intoStringTranslate, '', [1, 2, 3]),
  reduce((acc, x) => intoString(acc, translate(acc, x)), '', [1, 2, 3]),

  reduce(translateArray, [], [1, 2, 3]),
  reduce(intoArrayTranslate, [], [1, 2, 3]),
);

const intoA = (xForm, xs) => ( // no initial!
  reduce((acc, x) => intoArray(acc, xForm(acc, x)), [], xs)
);
const intoS = (xForm, xs) => ( // no initial!
  reduce((acc, x) => intoString(acc, xForm(acc, x)), '', xs)
);

const xf1 = (acc, x) => translate(acc, x);
console.log(
  intoA(xf1, [1, 2, 3]),
  intoS(xf1, [1, 2, 3]),
);

const transduce = (xForm, finto, initial, xs) => {
  const rFunc = (acc, x) => finto(acc, xForm(acc, x));
  return reduce(rFunc, initial, xs);
};

const xf = (acc, x) => translate(acc, x);
const fiA = (acc, x) => acc.concat(x);
const fiS = (acc, x) => [acc, x].join(' ');

console.log(
  transduce(xf, fiS, '', [1, 2, 3]), // ->  one two three
  transduce(xf, fiA, [], [1, 2, 3]), // ->  [ 'one', 'two', 'three' ]
);