Heaven's Kitchen

IT戦士amachangのこのエントリーを見てJavaScriptで無限リストをやってみたくなった。amachangのやりたいことをあんまり理解してないので，関係ないかも知れないけど…。

無限リストは先頭要素の値と，n番目の要素の値からn+1番目の要素を計算する関数の組で表現できる。

JSにはタプルはないので，配列でこの組を保持することにして1から始まる自然数の無限列は次のような感じになる。

var nat = [1, function (x) { return x + 1; }];

このnatという無限列の10番目を取り出すには

function next(n) {
    return [n[1](n[0]), n[1]];
}

function pos(ix, n) {
    for (var i=0;i<ix;i++) {
	n = next(n);
    }
    return n[0];
}

こんな感じのpos関数を作っといて

print(pos(9, nat)); // 10

とかやればいい。

調子にのってHaskellのtakeやmap風のこともやってみる。

function take(n, inflist) {
    var ary = [];
    for (var i=0;i<n;i++) {
	ary.push(inflist[0]);
	inflist = next(inflist);
    }
    return ary;
}

function map(func, inflist) {
    var n = inflist;
    return [func(n[0]), 
	    function(x) {
		n = next(n);
		return func(n[0]);
	    }];
}

var evens = map (function(x) { return x*2; }, nat);

print(take(10, nat)); // 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
print(take(10, evens)); // 2, 4, 6, 8, 10, 12, 14, 16, 18, 20

素数の列を

var prime = [2, function (prime) {
	prime++;
    outloop:
	while(true) {
	    for(var i=2;i<=Math.sqrt(prime);i++) {
		if (prime % i == 0) {
		    prime++;
		    continue outloop;
		}
	    }
	    return prime;
	}
    }];

と作っておけば，

print(pos(99, prime)); // 541 (100番目の素数)
print(take(100, prime)); // 100個まで素数を列挙

みたいな感じで遊べる。

プログラミング in OCamlっていう本を参考にしているので，考え方はOCaml風(?)．もっとJavaScript風の書き方がありそうだなぁ。