JavaScriptでリスト内包表記を作ってみた

haskellやErlangにあるようなリスト内包表記を理解する為にも、
また便利っぽいのでJavaScriptでも使えるよう実装してみる事にした。

実装前に検索をかけてみると既にそういう事やってる人はいるみたいだ。
JavaScriptでリストの内包表記(の真似) | 東京嫉妬

まぁ理解する為には実装してみるのが一番って事で、車輪の再発明なんて気にしない。
それに既に途中までやってるしね。ではいってみよー。

インターフェースをどうする？

まず内包表記の分解から。
[x | x <- [1,2,3,4,5,6], x < 4]
こんな感じの記法で、[1,2,3]というリストと等価になる。

この書き方は元々、数学の集合の定義を表現する記法に由来しているらしく、
x <- [1,2,3,4,5,6]ってのは数学の場合
x ∈ [1,2,3,4,5,6]という記述になるみたい。
これで「x は　[1,2・・]の集合の要素」という意味らしい。

内包表記の文法は

要素に対する式の適用部
リストとその変数のbind定義部
処理に含める要素の条件定義部（省略すると全て要素に対して式を適用）

に分解できそうだ。

問題はこの記述を関数にどう渡すかだが、
一つの文字列として書けたら他の言語と同じ記述にできるが、文字列の解析が面倒な気もするので、
とりあえず列挙した３つをそれぞれ引数として受け取る関数定義にする。

こんな感じか。
function listC(e, bindings, filters);

eは文字列でいいだろう。最後に内部でevalする。

bindingsは、文字列の方が見た目的に良さそうだが、
他の関数の実行結果とかを考慮にいれるとオブジェクトも有りか。
"x <- [1,2,3]" のような書き方と{x: [1,2,3]}という書き方の
両方使えるようにする。
文字列の場合は <- を : に置き換えて内部で eval してオブジェクト化。
つまり : が　<- になっただけのjson形式での記述になる。

filtersも文字列もしくは関数オブジェクトを受け取れるようにする。
とりあえずこれでインターフェースは決まった。

実装

まずは渡されたリスト同士のデカルト積を取る必要がある。
これには昨日作った関数を利用する。

このデカルト積でできたリスト全てをフィルターに通した上で、
第一引数で渡された式を適用してやればいいはず。

式を適用する時、変数名をバインドしてやる部分がこの関数の肝となるのかな。
例えば適用する式が "x + y" の場合、思いついた処理はこんな感じ。

var e = "x + y";
var result;
with({x: 20, y:10}) {
   result = eval(e);
}
// result = 30

そしてこれをサブ関数化する。

function makeEvaluater(exp) {
  return function(obj) {
    with(obj) return eval(exp);
  }
}

最終的な評価リストに含めるリストをフィルタリングする部分の式の扱いも基本的に同じ。
ただし、関数を指定する事もできるので、この場合は関数の仮引数にバインドしてやりたい。
処理としては以下の通り。

var e = function(x,y) { return x + y; }; // 引数で渡された関数とする
var params = e.argumentNames(); // prototype.jsから仮引数リストを取得する関数をパクった
var obj = {x: 20, y:10};
var args = params.map(function(name) { return obj[name]; });
e.apply(obj, args);
// 30

先ほどのmakeEvaluaterにこの処理を追加してやり、
引数の型に応じてそれぞれに合わせた関数を返してやるようにする。

function makeEvaluater(e) {
    if (typeof e == "string") {
        return function(obj) {
            with(obj) return eval(e);
        }
    } else if (typeof e == "function") {
        var params = e.argumentNames();
        return function(obj) {
            var args = params.map(function(name) { return obj[name] });
            return e.apply(obj, args);
        };
    } else {
        return function(){};
    }
}

次に式に渡すオブジェクトを考える必要がある。
例えば集合を "x <- [1,2], y <- [3,4,5]" と定義した場合、
デカルト積は、[ [1,3],[1,4],[1,5],[2,3],[2,4],[2,5] ]　となり、
[{x:1,y:3},{x:1,y:4},{x:1,y:5},{x:2,y:3}…] というリスト変換してから、
makeEvaluaterによって返された関数を順番に適用していけばよい。
このリストからオブジェクトへの変換処理は簡単なので省略。

こうしてできあがったものがこれ。

function listComprehension(e, bindings, filters) {
    if (typeof e == "string") e = makeEvaluater(e);
    var keys = [], lists = [];
    bindings = parseBindings(bindings);
    for(var key in bindings) {
        keys.push(key);
        lists.push(bindings[key]);
    }
    var filters = parseFilters(filters);
  
    var prod = product.apply(null, lists);
  
    var targets = prod.map(function(l) {
        return bindKey(keys,[].concat(l));
    }).filter(function(obj) {
        return filters.all(function(f){    return f(obj); });
    });

    return targets.map(e);
}

前半で渡された引数の解析や配列からオブジェクトへの変換を行い、後半はそれらを順次適用してやるといった処理。
サブルーチン化されているいくつかの関数は、動作デモのページでソースを直接見てください。

処理的にはたぶんもっとコンパクトになるんじゃないかな。
あと、本来はデカルト積をとりながら、フィルタリングと式の適用を全部やる方が
速度的に速いんだろうけど、それは最適化とかでやるべきだと思うし、
分かり易く富豪的にやってみました。