Array#inject を Scheme 的に -> map 関数の実装
id:reinyannyan:20061127:p1 で取り上げた SICP の accumulate 関数は、まだ Lisp の肝であるリストが紹介されていない段階のものでした。
２章に入り、リストを用いた、より汎用的な実装が示されていますので、前回のアップデートも兼ねて見ておきたいと思います。
// 再帰版
function accumulate(op, initial, lst) {
return nullp(lst) ? initial
: op(car(lst), accumulate(op, initial, cdr(lst)));
}// 反復版
function accumulate(op, initial, lst) {
function iter(result, lst) {
return nullp(lst) ? result
: iter(op(car(lst), result),
cdr(lst));
}
return iter(initial, lst);
}"nullp" はリスト (配列) が空かどうかを判定する関数です。Scheme では "null?" なんですが、クエスチョン記号が使えないため、Lisp の慣習に倣って "predicate" の "p" を付けてみました ("po" でも良かったかもしれません)。
"car" はリストの先頭の要素、"cdr" は先頭の要素を除いたリストを返す関数です。
(これらサポート関数の実装は最後にまとめてお見せします)
それぞれの accumulate を大雑把に説明しておきますと、上の方はリストの先頭と残りの要素を任意の関数 (op) で連結する、という意味になります。
下の方は「残りの要素」ではなく「前回までの連結結果」と連結する、という点が異なります。前者はスタックを積み上げますが、後者は毎回の演算結果を積み上げていきます。
また、関数 "op" で要素を連結する方向によって "fold-right"、"fold-left" という別名で呼ばれているそうです (例では反復版が "fold-left" になっていると思います)。
(注: この辺りの記述について、最後の方に幾つか訂正を追記しました)
使い方はこんな感じです:
var add = function(a,b){return a+b};
var lst = [1,2,3,4,5];
accumulate(add, 0, lst);
// -> 15
// cf. prototype.js
lst.inject(0, add);
// cf. Mochikit
reduce(add, lst, 0);
さて、accumulate が出来たところで、Scheme の apply 関数が実装できるんじゃないかと思いました。apply 関数とは、
apply(add, 1, 2, 3, list(4, 5)); // -> 15
のように、引数リストに対して任意の関数を実行し、その連結結果を得るものです。
accumulate と似た感じなんですが、仕様が少し違います。最後の引数はリストでなければならず、その前にゼロ個以上の非リストを取ります。
このように書けました:
function apply(proc) {
var lst = accumulate(function(a,b) {
return not(pairp(a)) ? cons(a,b)
: append(a,b);
},
nil(),
list_tail(arguments,1));
return accumulate(proc, car(lst), cdr(lst));
}要素がリストでなければ (not pairp) 残りのリストに cons ( b.unshift(a) とほぼ同義) し、リストであれば append ( a.concat(b) ) することで、非リストとリストの列をフラットにしています。
Scheme の仕様よりも甘くなっていると思いますが、とりあえず良しとしておきます。
apply が出来ると、リスト操作が俄然強力に行えるようになります。ここでは "any" と "map" をセットで実装してみます。
"any" はリストの中で少なくとも一つの要素が条件に合えば真を返す、"map" はリストの個々の要素に関数を適用して新しいリストを返す、というものです。例:
map(square, list(1,2,3)) // -> [1,4,9] any(nullp, list(1,2,nil())) // -> true (nil は空リストを返す関数)
これらを、「リストのリスト」も扱えるようにしたいんですが、その際に apply が活躍するというわけです:
function map(proc, lst) {
var rest = list_tail(arguments,2);
return nullp(rest) ? map1(proc, lst)
: map2(proc, cons(lst, rest));
}
function map1(proc, lst) {
return nullp(lst) ? nil()
: cons(proc(car(lst)), map1(proc, cdr(lst)));
}
function map2(proc, lst) {
return any1(nullp, lst) ? nil()
: cons(apply(proc, map1(car, lst)),
map2(proc, map1(cdr, lst)));
}
function any(pred, lst) {
var rest = list_tail(arguments,2);
return nullp(rest) ? any1(pred, lst)
: any2(pred, cons(lst, rest));
}
function any1(pred, lst) {
return nullp(lst) ? false
: pred(car(lst)) || any1(pred, cdr(lst));
}
function any2(pred, lst) {
return any1(nullp, lst) ? false
: apply(pred, map1(car, lst)) || any2(pred, map1(cdr, lst));
}(Guile の SRFI (Scheme Requests for Implementation) 1 の実装を参考にしました)
使用例:
map(add, list(1,2,3), list(4,5,6), list(7,8,9)); // -> [12,15,18]
単純化のため、フラットなリスト、リストのリスト、それぞれで別バージョンの関数を用意しています。
ここでは各関数の簡潔さを見ていただければと思います。
私自身、再帰や高階関数といった技法はあまり積極的に使ってきませんでしたので、学ぶところが多いなぁと感じる今日この頃です。
最後に、上で使用した関数郡です:
function cons(x,lst) {
(lst = lst.unshift ? [].concat(lst) : list(lst)).unshift(x);
return lst;
}
function car(lst) {
return lst[0];
}
function cdr(lst) {
(lst = [].concat(lst)).shift();
return lst;
}
function list() {
return list_tail(arguments);
}
function list_tail(lst, k) {
return Array.prototype.slice.call(lst, k||0);
}
function append(a,b) {
return (a||nil()).concat(b);
}
function not(p) {
return !p;
}
function nil() {
return [];
}
function nullp(lst) {
return lst == null || lst == undefined ||
(lst instanceof Array) && lst.length == 0;
}
function pairp(lst) {
return (lst instanceof Array) && lst.length > 0;
}
function accumulate(op, initial, lst) {
var rest = list_tail(arguments,3);
if (pairp(rest)) // N-ary case
return accumulate_n(op, initial, cons(lst, rest));
// Fast path
return nullp(lst) ? initial
: op(car(lst), accumulate(op, initial, cdr(lst)));
}
function accumulate_n(op, initial, lst) {
return any(nullp, lst) ? nil()
: cons(accumulate(op, initial, map(car, lst)),
accumulate_n(op, initial, map(cdr, lst)));
}(あくまで Lisp 的な思想や思考方式などを吸収したい、という個人的な目的で書いており、Scheme 風ライブラリを作ろうなんてことは考えていません。が、結果的に充実してきたら楽しいかなぁとも思います…)
参考:
jsScheme - Scheme interpreter in JavaScript (ソースは読んでませんが、多分 Scheme インタープリタ API を Ajax で呼び出す式のオンライン Scheme シェルです 訂正 [20061223]: ソースを見たんですが、JavaScript で書かれた Scheme インタープリタでした (jQuery とか書いてあったもので、勘違いしてしまいました)。相当本格的な内容みたいです)
追記 [20061221]:
1.
fold-left/right の説明が少し間違っていたようです。Wikipedia の記事によると、普通の再帰処理で実装される fold (reduce) を fold-right、末尾再帰による実装を fold-left と言うそうです。
ただ、再帰の種類にかかわらず、要素を連結していく方向をもって left/right と呼んでいる実装もあります (例: MzScheme の foldl/foldr @ collects/mzlib/list.ss)
また、末尾再帰版 (反復版) の実装に関して、スタックを積み上げないかのような書き方をしてしまいましたが、それは Scheme の話で、JavaScript に当てはまるものではありません。
2.
うっかりしていたんですが、ドット付きペア
(cons 1 2) ; -> (1 . 2)
の cdr は (2) じゃなくて 2 を返すんですね。上の実装だと (2) になってしまいます。と言うか、そもそもドット付きペアは実装していませんでした。
とりあえず、以下の変更でそれらしきものが出来るみたいです:
var dot,undot;
(function() {
var _ = {};
dot = function(x) {
return list(_, x);
};
undot = function(lst) {
return eqp(car(lst), _) ? cadr(lst) : lst;
};
})();
function cons(x,lst) {
(lst = lst.unshift ? [].concat(lst) : dot(lst)).unshift(x);
return lst;
}
function cdr(lst) {
(lst = [].concat(lst)).shift();
return undot(lst);
}
function cadr(lst) {
return car(cdr(lst));
}
function list() {
return Array.prototype.slice.call(arguments);
}
function list_tail(lst, k) {
lst = list.apply(null, lst).slice(k||0);
return undot(lst);
}
function eqp(a,b) {
return a==b;
}
// 確認
var dp = cons(1,2); // -> [1, {dot}, 2]
cdr(dp); // -> 2 (not [2], nor [{dot}, 2])
list_tail(dp,1); // -> ditto3.
どうも apply の実装が間違っていたようです。なぜか fold/accumulate と同じくリストの要素を一つずつ結合していくものだと思っていたんですが、いっぺんに関数に渡してしまうんですね。
Scheme で
(apply (lambda (a b) (+ a b))
'(1 2 3))とするとエラーになったので気付きました。ここは素直に JavaScript の Function#apply メソッドを使うべきでした。
