はじめに

とある本の検証のために、JavaScript(正確にはECMAScript-262 5.1)の仕様書を読んだりしていた。というのも、JavaScriptの場合、大抵のメソッドについては、どのように実装されるべきか、というアルゴリズムが定義されており、これを見ればどういう挙動になっているのかがわかるからです。詳細については、Array.prototype.reduce() - JavaScript | MDNという信頼できるドキュメントがあるので、そちらに譲るとして、そもそもreduceとは何なのかについて、せっかくなので、調べたことをメモしておきます。

reduceとは

一般的に、reduceというのを一言で説明する言葉として「折りたたみ操作」という言葉が使われることが多いです。どういうことかというと、実例として、某書に頻出する表現を使いますと:

[1, 2, 3, 4].reduce(function(a, b) { return a + b }; );
// => 10

というようになります。原理的には、このreduceは以下のような操作のことを指しています。

(((1 + 2) + 3) + 4)

抽象的に言うと、「前の結果を利用して、それとペアにして次の要素に、関数を適用する」というのが、この操作となります。上記の場合ならば、最初に1, 2のペアにfunction(この場合であるならば、a + bの値を返すfunction)を適用し、3を作ります。この3を次の要素である3 + 3とし……といったように、繰り返し行って行きます。

どうも仕様書を見るかぎり、このfunctionは各要素をwhileで調べて行くのが一般的な実装のようです。このような実装になっているのは思い当たりがあるのですが、この場合、再帰で実装したほうが幾分わかりやすいので、再帰で実装してみます。

function reduce(a, f, v) {
  var s = a.slice(); 
  if (typeof v === "undefined") { 
    v = s.shift();
  }
  if (s.length < 1) {
    return v;
  } else {
    v2 = s.shift();
    return reduce(s, f, f(v, v2));
  }
}

このように、次の要素をとっては、関数を適用した結果を溜め込んでいくような関数として実装ができます。slice()を使っているのは、JavaScriptで、引数として入ってきた配列をshiftすると、元のところまで変更が波及してしまうからです。

再帰的な定義を見るとわかるように、折りたたみ過程である配列を第一引数に、そして実行しようとする関数オブジェクトを第二引数に、そして結果を第三引数に渡し、次の過程においては第三引数で渡ってきた前回の結果と、次の要素を適用したものを次の関数として定義しています。

再帰の弱点

このような、折りたたみに関しては、再帰で表現したほうが幾分かわかりやすい(と自分では思っている)のですが、しかし現実的な実装としては、そうではありません。先ほどのドキュメントを見る限りだと、whileを使った実装を使っているようです。簡略化した実装を考えてみましょう。

function reduce(a, f) {
  var i = 1, l = a.length, v;
  v = a[0];
  while(i < l) {
    v = f(v, a[i]);
    i++;
  } 
  return v;
}

どうもこっちのほうがシンプルそうですが、これがポイントなのではなく、再帰の場合、最適化がされていない場合、スタックがオーバーフローしてしまう可能性があるのと、スタックによるオーバーヘッドがかさむという、現実的なチューニングの話になるので、おそらくこのような実装のほうを仕様として採用しているのだと思われます。

あるいは、どうしてもJavaScriptの場合、配列を扱うさいに、破壊的にならざるを得ないという事情も含めたり、あるいはメソッド自体を一つに抑えたいということを考えると、このような実装を採用しているのだろうと思いました(月並みな感想)。

まとめ

この元ネタは、1から10を足すコードが何度も出てくることで有名な本なのですが、この本を詳細に見ていって、検証した結果、reduceの実装がこういう風になっているんだ、というのがわかってよかった。冷静に考えれば、そりゃそうなんだけど、実際に、仕様書を見てみると「なるほどなー」と思えるので、もし機会があれば、仕様書を読むのも悪くないように思えます。