Range#inject を Scheme 的に -> 積分への応用

SICP を読んでいます (まだ 1 章の高階関数のところです)。

練習問題で Smalltalk や Ruby (や prototype.js) の inject メソッドと同等のものが出てきましたので、ピックアップしてみたいと思います。

以下の様な、a から b までの範囲の数列の総和・総乗などの計算式を、高階関数を使って一般化する、という課題です。

function sum(a, b) {
  return a > b ? 0
               : a + sum(a + 1, b);
}
sum(1, 10); // -> 55

function product(a, b) {
  return a > b ? 1
               : a * product(a + 1, b);
}
product(1, 10); // -> 3628800

上の 2 例を見比べると、形としては全く同じ式であることが分かります。ということで、異なる点

a の値が b を追い越した時の値 (0 / 1)
各項の累算の方式 (+ / *)

を切り出して引数として受け取るようにすれば良いですね。

課題ではさらに

各項の表現の仕方 (term)
項目インデックスの繰り上げ方 (next)

も高階化するように、との仕様が示されています。

このようになりました。

// 再帰版
function accumulate(combiner, null_value, term, a, next, b) {
  return a > b ? null_value
               : combiner(
                    term(a),
                    accumulate(combiner, null_value, term, next(a), next, b));
}

// イテレータ版
function accumulate(combiner, null_value, term, a, next, b) {
  function iter(n, result) {
    return n > b ? result
                 : iter(next(n), combiner(term(n), result));
  }
  return iter(a, null_value);
}

(先に Scheme で書いたものを JavaScript に書き直したんですが、びっくりするほどコンマを打ち忘れました)

では、これを使って sum を再実装してみます:

function sum(a, b) {
  return accumulate(function(a,b){return a+b}, 0, function(x){return x},
                    a, function(x){return x+1}, b);
}

見易さのために、値をそのまま返す関数 identity と、数値を増加させる関数 incrementor を定義しておきましょう:

function identity(x) {
  return x;
}

function incrementor(step) {
  step = step || 1;
  return function(x) {
    return x + step;
  };
}

すると、こうなります:

function sum(a, b) {
  return accumulate(function(a,b){return a+b}, 0, identity, a, incrementor(), b);
}

また、試しにこんなのはどうでしょう？:

function char_sum(a, b) {
  return accumulate(function(a,b){return b+a}, "",
                    function(x){return String.fromCharCode(x)},
                    a, incrementor(), b);
}
char_sum(97,122); // -> ?

Composite Simpson's rule

SICP の課題 1.29、シンプソンの公式

$\int_a^b f(x) \, dx\approx \frac{h}{3}\bigg[f(x_0)+2\sum_{j=1}^{n/2-1}f(x_{2j})+ 4\sum_{j=1}^{n/2}f(x_{2j-1})+f(x_n) \bigg]$

というのを見て、accumulate が利用できるんじゃないかと思いました。

すなわち、

2 から n - 2 までの偶数項
1 から n - 1 までの奇数項

における関数 f(x) の値の総和をそれぞれ accumulate で計算することが出来そうです。

このように書けました (n は a から b までの範囲の分割個数 (偶数)、f は任意の関数です):

function simpson_integral(f, a, b, n) {
  var h = (b - a) / n;

  function x(j) {
    return f(a + (j * h));
  }

  function sum_x(k) {
    return accumulate(function(a,b){return a+b}, 0, x, k, incrementor(2), (n - k));
  }

  return multiply(
    (h / 3),
    add(x(0),
        2 * sum_x(2),
        4 * sum_x(1),
        x(n)
    )
  );
}

simpson_integral(function(x){return x*x*x}, 0, 1, 100); // -> 0.25

accumulate があることによって、一見難しそうな計算も非常にシンプルに (sum_x(k)) 書くことが出来るわけです。

さて、ここで不必要に凝ってみたのが multiply と add という関数です。その名のとおり引数を掛けたり足したりする関数なんですが、どうやって実装できるでしょうか？

そうです、これも accumulate が使えるんですね:

function add() {
  var args = arguments;
  return accumulate(function(a,b){return a+b}, 0, function(x){return args[x]},
                    0, incrementor(), (args.length - 1));
}
function multiply() {
  var args = arguments;
  return accumulate(function(a,b){return a*b}, 1, function(x){return args[x]},
                    0, incrementor(), (args.length - 1));
}

あれ、どこかで見た感じではないでしょうか？　そう、sum と product で見た類似パターンですね。一般化してしまいましょう:

function accumulate_args(combiner, null_value, args) {
  return accumulate(combiner, null_value, function(x){return args[x]},
                    0, incrementor(), (args.length - 1));
}