IT 戦記で Haskell のリストを JavaScript で書くというのをやっている。これは面白い。ただ、そのまま書くと無限リストが無限再起に陥ってしまうので、遅延評価を行わなくてはいけない。

関数式を使った遅延評価

JavaScript で遅延評価を行うにはどうすればいいか。その答えのひとつが関数式だ。リストの各セルを、先頭の値と後続のリストという構造ではなく、先頭の値と後続のリストを返す関数という構造にしてやれば、リストの最初のセルを評価した時点で残りのセルがすべて評価されるという事態を防げる。

具体的には、リスト構築の際、後続のリストそのものの代わりにリストを返す関数を渡し、後続のリストを得るときは関数呼び出しを伴うようにすればよい。なお、ここでは空リストを表現するのに nil という特殊な値を用いる。nil は先頭の値も後続のリストも nil 自身であるリストである。

var _ = this;

_['[]'] = (function () {
  var nil = [, function () { return nil; }];
  nil[0] = nil;
  return function () { return nil; };
})();

_[':'] = function (x) {
  return function (xs) {
    return [x, xs];
  };
};

_['map'] = function (f) {
  return function (x) {
    if (x == _['[]']()) return _['[]']();
    return _[':'](f(x[0]))(function () { return _['map'](f)(x[1]()); });
    // function () ... リスト構築時の第 2 引数には関数を渡す。
    // x[1]() 後続のリストを参照するときは関数呼び出しを行う。
  };
};

_['!!'] = function (x) {
  return function (i) {
    if (x == _['[]']()) throw 'index too large';
    if (i == 0) return x[0];
    return _['!!'](x[1]())(_['-'](i)(1));
  };
};

_['+'] = function (a) { return function (b) { return a + b; }; };
_['-'] = function (a) { return function (b) { return a - b; }; };
_['*'] = function (a) { return function (b) { return a * b; }; };
_['/'] = function (a) { return function (b) { return a / b; }; };

function stringifyList(list) {
  if (list == _['[]']()) return '[]';
  return '[' + list[0] + ', ' + stringifyList(list[1]()) + ']';
}
function take(list, n) {
  if (n == 0) return [];
  if (n == 1) return [list[0]];
  return [list[0]].concat(take(list[1](), n - 1));
}

// a = []
_['a'] = function () { return _['[]'](); };
print(stringifyList(a()));
// => []

// b = [1]
// b = (:) 1 []
_['b'] = function () { return _[':'](1)(function () { return _['[]'](); }); };
print(stringifyList(b()));
// => [1, []]

// c = [1, 2]
// c = (:) 1 ((:) 2 [])
_['c'] = function () {
  return _[':'](1)(function () {
    return _[':'](2)(function () {
      return _['[]']();
    });
  });
};
print(stringifyList(c()));
// [1, [2, []]]

// d = [1..10]
_['d'] = function () {
  var ff = function (i) {
    if (i == 0) return _['[]']();
    return _[':'](1)(function () {
      return _['map'](_['+'](1))(ff(_['-'](i)(1)));
    });
  };
  return ff(10);
};
print(stringifyList(d()));
// => [1, [2, [3, [4, [5, [6, [7, [8, [9, [10, []]]]]]]]]]]
print(_['!!'](d())(2));
// => 3

// e = [1..]
_['e'] = function () {
  return _[':'](1)(function () {
    return _['map'](_['+'](1))(_['e']());
  });
};
print(_['!!'](e())(2));
// => 3
print(take(e(), 5));
// => 1,2,3,4,5

// f = [1,3..]
_['f'] = function () {
  return _[':'](1)(function () {
    return _['map'](_['+'](_['-'](3)(1)))(_['f']());
  });
};
print(take(f(), 5));
// => 1,3,5,7,9

// g = [ x * x | x <- f ]
_['g'] = function () {
  return _['map'](function (x) { return _['*'](x)(x); })(_['f']());
};
print(take(g(), 5));
// => 1,9,25,49,81

式クロージャ

しかし、このままでは function やら return やらが並んでいていささか読みづらい。そこで JavaScript 1.8 から導入された式クロージャの出番である。これは、関数本体が return 文のみからなるとき、波括弧と return キーワードを省略できるという記法である。これを使って前述のリストを書き直すと以下のようになる。