無限リストと遅延評価 ― 2008年02月02日 15時53分
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 キーワードを省略できるという記法である。これを使って前述のリストを書き直すと以下のようになる。
var _ = this;
_['[]'] = let (nil = []) (nil[0] = nil)[1] = function () nil;
_[':'] = function (x) function (xs) [x, xs];
_['map'] =
function (f)
function (x)
(x == _['[]']()) ? _['[]']()
: _[':'](f(x[0]))(function () _['map'](f)(x[1]()));
_['!!'] = function (x) {
if (x == _['[]']()) throw 'index too large';
return function (i) (i == 0) ? x[0] : _['!!'](x[1]())(_['-'](i)(1));
};
_['+'] = function (a) function (b) a + b;
_['-'] = function (a) function (b) a - b;
_['*'] = function (a) function (b) a * b;
_['/'] = function (a) function (b) a / b;
var a = function () _['[]']();
var b = function () _[':'](1)(function () _['[]']());
var c = function () _[':'](1)(function () _[':'](2)(function () _['[]']()));
var d =
function ()
let (ff = function (i)
(i == 0)
? _['[]']()
: _[':'](1)(function () _['map'](_['+'](1))(ff(_['-'](i)(1)))))
ff(10);
var e = function () _[':'](1)(function () _['map'](_['+'](1))(e()));
var f = function () _[':'](1)(function () _['map'](_['+'](_['-'](3)(1)))(f()));
var g = function () _['map'](function (x) _['*'](x)(x))(f());いかがだろうか。少しは見やすく……なったかもしれないということにしておこう。
ジェネレータを使った無限リスト
無限リストの値を利用するためにはいったんリストの計算を止めなくてはいけないが、完全に中止してしまうとそれ以降の値を求められない。途中の値を求め、かつ計算を続けるためには処理を中断する必要がある。中断、そう、今こそジェネレータの本領発揮である。JavaScript 1.8 からは、ジェネレータ式の導入により、
var g = (function () { for (var i in o) yield i + i; })();を以下のように書けるようになり、よりジェネレータが扱いやすくなっている。
var g = (i + i for (i in o));ここで、function キーワードがなくなっていることに注意してほしい。すなわち、ジェネレータ式を使えば、function キーワードを用いずに遅延評価を導入できるのである。
以下にジェネレータを使った無限リストの表現例を示す。[]、:、!!、+、-、*、/ は、便宜上それぞれ nil、cons、at、add、sub、mul、div と改名した。nil が生成するのは空のジェネレータイテレータであり、next メソッドが呼び出されると直ちに StopIteration 例外を投げて停止する。
var nil = function () { return; yield; };
var cons = function (x) {
return function (xs) {
yield x;
for (var i in xs)
yield i;
};
};
var map = function (f) {
return function (x) {
yield f(x.next());
for (var i in map(f)(x))
yield i;
};
};
var at = function (x)
function (i)
let (first = x.next())
(i == 0) ? first : at(x)(sub(i)(1));
var add = function (a) function (b) a + b;
var sub = function (a) function (b) a - b;
var mul = function (a) function (b) a * b;
var div = function (a) function (b) a / b;
var a = function () nil();
var b = function () cons(1)(nil());
var c = function () cons(1)(cons(2)(nil()));
var d = function ()
let (ff = function (i)
(i == 0)
? nil()
: cons(1)(map(add(1))(e for (e in ff(sub(i)(1))))))
ff(10);
var e = function () cons(1)(map(add(1))(i for (i in e())));
var f = function () cons(1)(map(add(sub(3)(1)))(i for (i in f())));
var g = function () (mul(x)(x) for (x in f()));
function take(iter, n) {
var i = 0;
for (var e in iter) {
if (++i > n) break;
yield e;
}
}
print([i for (i in a())]); // => (空文字列)
print([i for (i in b())]); // => 1
print([i for (i in c())]); // => 1,2
print([i for (i in d())]); // => 1,2,3,4,5,6,7,8,9,10
print(at(e())(2)); // => 3
print(at(f())(2)); // => 5
print([i for (i in take(e(), 5))]); // => 1,2,3,4,5
print([i for (i in take(f(), 5))]); // => 1,3,5,7,9
print([i for (i in take(g(), 5))]); // => 1,9,25,49,81
最近のコメント