Heaven's Kitchen

amachangさんが試行錯誤しているのを見て，ついかっとなってやってしまった。

少し長いけど，ようするにフィボナッチ数列をHaskell風に

cons(0, cons(1, zipWith(add, fib, cdr(fib))))

と書きたかった。

以下が実装。

(* 16:00 修正: ひろきのだいちくんの指摘により，selfだったところをidentityに変えました。 ついでに，使ってなかった関数を消してすっきりさせました。*)

function Cons (car, cdr) {
    if (car == null || cdr == null) {
	throw "illegal object.";
    }
    this.car = car;
    this.cdr = cdr;
}

function Action (act) {
    if (act == null || !(act instanceof Function)) {
	throw "illegal object.";
    }
    this.action = act;
}

function Thunk (any) {
    if (any instanceof Thunk) {
	this.value = any.value;
	this.evaled = any.evaled;
    } else {
	this.value = any;
	this.evaled = !(any instanceof Action);
    } 
}

var _ = function (f) { return new Thunk(f); };
var action = function (f) { return _(new Action(f)); };
var nil = function () { };
var identity = function () { return this; };

Cons.prototype.run = identity;
Number.prototype.run = identity;
String.prototype.run = identity;
Boolean.prototype.run = identity;
Function.prototype.run = identity;
nil.run = identity;
nil.toString = function () { return "nil";};
Action.prototype.run = function () { 
    return this.action(); 
};

Thunk.prototype.run = function () {
    if (this.evaled) {
	return this.value;
    }
    this.value = this.value.run();
    while (this.value instanceof Thunk) {
	this.value = this.value.run();
    }
    this.evaled = true;
    return this.value;
};

Thunk.prototype.toString = function () {
    return this.run().toString();
};

Cons.prototype.toString = function () {
    var str = "(";
    var car = this.car.run();
    var cdr = this.cdr.run();
    while (cdr instanceof Cons) {
	str += (car == nil) ? "" : car;
	car = cdr.car.run();
	cdr = cdr.cdr.run();
	if (car != nil) str += " ";
    }
    str += ((car == nil) ? "" : car);
    str += ((cdr == nil) ? "" : " . " + cdr);
    return str + ")";
}

/*** premitives ***/

function cons (car, cdr) {
    return action(function () { return new Cons(car, cdr) });
}

function car (val) {
    return action(function () {
	    val = val.run();
	    if (val == nil) {
		return nil;
	    }
	    if (!(val instanceof Cons)) {
		throw "cons applyed to non-Cons object.";
	    }
	    return val.car;
	});
}

function cdr (val) {
    return action(function () {
	    val = val.run();
	    if (val == nil) {
		return nil;
	    }
	    if (!(val instanceof Cons)) {
		throw "cons applyed to non-Cons object.";
	    }
	    return val.cdr;
	});
}

/*** operators ***/

function decr (n) {
    return action(function () {
	    n = n.run() - 1;
	    return n;
	});
}

function incr (n) {
    return action(function () {
	    n = n.run() + 1;
	    return n;
	});
}

/*** list ***/

function nth (n, xs) {
    return action(function () {
	    if (n.run() <= 0) {
		return car(xs);
	    }
	    return nth(decr(n), cdr(xs));
	});
}

function dup (lst) {
    return action(function () {
	    if (lst.run() == nil) {
		return nil;
	    }
	    return cons(car(lst), dup(cdr(lst)));
	});
}

function append (xs, ys) {
    return action(function () {
	    if (xs.run() == nil) {
		return dup(ys);
	    }
	    return cons(car(xs), append(cdr(xs), ys));
	});
}

function take (n, lst) {
    return action(function () {
	    if (lst.run() == nil || n.run() == 0) {
		return nil;
	    }
	    return cons(car(lst), take(decr(n), cdr(lst)));
	});
}

function zipWith (op, xs, ys) {
    return action(function () {
	    if (xs.run() == nil || ys.run() == nil) {
		return nil;
	    }
	    return cons(op.run()(car(xs).run(), car(ys).run()), 
			zipWith(op, cdr(xs), cdr(ys)));
	});
}

/*** infinity ***/

function cycle (lst) {
    return action(function () {
	    return append(lst, cycle(lst));
	});
}

function from (n) {
    return action(function () {
	    return cons(n, from(incr(n)));
	});
}

ここまで作れば後は

var fib = action(function () {
	var add = function (x, y) { return x + y; };
	return cons(0, cons(1, zipWith(add, fib, cdr(fib))));
    });

でフィボナッチの無限リストが!!

というわけで実行してみる。

print(take(10, cycle(cons(1,cons(2,nil))))); // (1 2 1 2 1 2 1 2 1 2)
print(take(10, from(3))); // (3 4 5 6 7 8 9 10 11 12)
print(take(10, fib)); // (0 1 1 2 3 5 8 13 21 34)
print(nth(99, fib)); // 218922995834555200000

あってるかどうかわからんけど，これやるのに一晩かかったので解説は後日気が向いたら…。