配列の畳み込みを利用して合成関数（？）を表現する

手軽に関数型言語を学ぶには js はいいかもしれない。

【追記】ここで定義している map と filter だけど、ECMAScript 262 5th editon の アルゴリズムに沿ってないっていう指摘がありました。ECMAの Array#map と Array#filter のアルゴリズム（というか定義）を知りたい人は http://www.ecmascript.org/docs/tc39-2009-043.pdf 見るといいです。あと実装については

を見るといいです。ここでの map と filter の定義は、「配列の各要素に関数を適用した値をとる新しい配列を作る」と「配列の各要素でテストにマッチした要素だけ抜き出す」の最小限度のことだけやってます。その辺は生暖かい眼で見ていただければ。(2011.11.25 23:08)

リストを扱う filter, map, folded（畳み込み）を大雑把に実装してみると

if (! Array.prototype.filter) { // grep
    Array.prototype.filter = function (patternFunc) {
        var helper = function (thisArray, newArray) {
            if (! newArray) newArray = [];

            if (thisArray && thisArray.length > 0) {
                var el = thisArray.shift();
                if (patternFunc(el)) newArray.push(el);
                return helper(thisArray, newArray);
            }
            return newArray;
        };

        return helper(this.slice());
    };
}

if (! Array.prototype.map) {
    Array.prototype.map = function (patternFunc) {
        var helper = function (thisArray, newArray) {
            if (! newArray) newArray = [];

            if (thisArray && thisArray.length > 0) {
                var el = thisArray.shift();
                return helper(thisArray, newArray.push(patternFunc(el)));
            }
            return newArray;
        };

        return helper(this.slice());
    };
}

if (! Array.prototype.folded) { // reduce ?
    Array.prototype.folded = function (func, i) {
        var helper = function (arry) {
            if (arry && arry.length > 0) {
                i = func(i, arry.shift());
                return helper(arry);
            }
            return i;
        };

        return helper(this.slice());
    };
}

みたいな感じでゲフンゲフンできますね。(型判断とか、エラー処理とか省いてます。おおざっぱー）

実際には

var a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ];

// 偶数だけ抜き出した配列
var even = a.filter(function (arg) {
    return (arg % 2 === 0) ? 1 : 0;
});
// とか、インクリメントした配列とか
var add1 = a.map(function (arg) {
    return arg + 1;
});
// 配列の合計値を出すとか
var sum = a.folded(function (arg1, arg2) {
    return arg1 + arg2;
}, 0);

console.log(even); // [ 0, 2, 4, 6, 8 ]
console.log(add1); // [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
console.log(sum);  // 45

// ネスト配列の合成とか
var b = [ [ 0, 1 ], [ 2, 3 ], [ 4, 5 ], [ 6, 7 ], [ 8, 9 ] ];
var single = b.folded(function (arg1, arg2) {
    return arg1.concat(arg2);
}, []);
console.log(single); // [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

とか、実際の場面でどれだけ使うかは、関数型言語的な処理に慣れないてないし、分んないけど。

関数の合成って Array#folded 使えばできるんじゃない？


関数合成

２つの関数 f(x) と g(x) がある。
y = f(x)
z = g(y)
とすると
z = g(f(x))
とすることができ、変数 x は 関数 f につづいて関数 g を機能させることにより z に対応するので、g(f(x)) を１つの関数と見なせる。

ということ（らしい）ので

function inc (x) {
    return x + 1;
}
function double (x) {
    return x * 2;
}
function square (x) {
    return x * x;
}

var num = 3;

// num を２乗したものを、２倍して、インクリメントする
num = inc(double(square(num)));

console.log(num);// 19

は

var func = [ double, square ].folded(function (f, g) {
    return function (x) {
        return f(g(x));
    };
}, inc);

console.log(func(num));

とできる。できるけど、全然直感的でない！

せめて、var func = [ inc, double, square ].composeFunc() ぐらいにはしたい。
【追記】: この配列に格納している関数の並び順だけど、これだと、最初に適用する関数 square が最後にきて、最後に適用する関数 inc が最初にくるので、直感的じゃない気がする。好みの問題でもあるけど [ square, double, inc ].composeFunc とした方が、square -> doble -> inc という順番というのが分かりやすいと思うので、ちょっと書きなおしてみた。(2011.11.25 16:00)

// おおざっぱー
if (! Array.prototype.composeFunc) {
    Array.prototype.composeFunc = function () {
        // var funcs = this.slice(); // 2011.11.25 16:00 削除
        var funcs = this.slice().reverse(); // 2011.11.25 16:00 追加
        var first = funcs.shift();
        return funcs.folded(function (f, g) {
            return function (x) {
                return f(g(x));
            };
        }, first);
    };
}

なので、関数合成関数はこう。

function compose () {
    return Array.prototype.slice.apply(arguments).composeFunc();
}

んで、

// var func = compose( inc, double, square ); // 2011.11.25 16:00 削除
var func = compose( square, double, inc );  // 2011.11.25 16:00 追加
console.log(func(num)); // 19

パフォーマンス考えたら、helper 使わずにループ使うほうがまったく早いとか、型判断すらしてねーから、どこでコケたかわかんねーだろとか、ゲフンゲフン