JavaScript で Listモナド

[id:gakuzo:20090223:1235405890]「JavaScript で Maybe」に続く、Monadic Programming in JavaScript 第二弾。JavaScript で Listモナドです。

さっくりコードに行きましょう。

Array.ret = function(obj) {
    return [obj];
}
/** jQuery版 */
Array.prototype.bind = function(callback) {
    return this.concat.apply([], jQuery.map(this, callback));
}
/** prototype.js版 */
Array.prototype.bind = function(callback) {
    return this.concat.apply([], this.map(callback));
}

Array#map を使いたかったので jQuery版と prototype.js版の両方を書いておきました。環境に合わせて下さい。どちらも使用していない場合は Array#map を自前で実装しましょう。 Firefox であればデフォルトで実装されてますが。

使い方は以下のような感じです。
例として「ふつうのHaskellプログラミング」で使われていたパターン展開の例をそのまま拝借してしまいましょう。

ふつうのHaskellプログラミング ふつうのプログラマのための関数型言語入門

「」パターンと「{}」パターンの両方を展開する expandPattern 関数を作りたいとします。
「」パターンは「img[012].png」という書式が「img0.png」「img1.png」「img2.png」に展開されるパターンです。
「{}」パターンは「img.{png,jpg}」という書式が「img.png」「img.jpg」に展開されるパターンです。
つまり expandPattern("img[012].{png,jpg}") を実行すると ["img0.png", "img0.jpg", "img1.png", "img1.jpg", "img2.png", "img2.jpg"] という値を返す関数を作りたい訳です。

ここで expandPattern をそのまま書くのは大変なので、「[]」パターンを展開する expandCharClass関数と「{}」パターンを展開する expandAltWords関数を定義します。

/** 
 * 「[]」パターンを展開します
 * "img[012].png" という文字列が渡されたら
 * ["img0.png", "img1.png", "img2.png"] という配列を返します。
 */
function expandCharClass(str) {
    if (!str.match(/(.*)\[(.*?)\](.*)/)) return [str];
    var result = [];
    var pre = RegExp.$1;
    var matched = RegExp.$2;
    var post = RegExp.$3;
    for (var i = 0, n = matched.length; i < n; i++) {
        var expanded = pre + matched.charAt(i) + post;
        result = result.concat(expandCharClass(expanded));
    }
    return result;
}

/** 
 * 「{}」パターンを展開します
 * "img.{png,jpg}" という文字列が渡されたら
 * ["img.png", "img.jpg"] という配列を返します。
 */
function expandAltWords(str) {
    if (!str.match(/(.*)\{(.*?)\}(.*)/)) return [str];
    var result = [];
    var pre = RegExp.$1;
    var matched = RegExp.$2.split(",");
    var post = RegExp.$3;
    for (var i = 0, n = matched.length; i < n; i++) {
        var expanded = pre + matched[i] + post;
        result = result.concat(expandAltWords(expanded));
    }
    return result;
}

この二つの関数を使って expandPattern を定義します。

function expandPattern(str) {
    return Array.ret(str).bind(expandCharClass).bind(expandAltWords);
    // return expandCharClass(str).bind(expandAltWords);  これでもOK
}

Array がモナドとして振舞えるので、expandCharClass と expandAltWords の二つの関数を bind することで、シンプルに expandPattern を実装することができます。