javascriptでstream - trotrの日記

sicpの中にstreamというデータ構造が出てきます。
streamを使うと無限の長さのデータを表せるらしいです。
でも、streamが分かっているのか分かっていないのかよく分かりません＞＜。
他の言語でstreamのようなものが実装できたら、分かっているということにしようと想います。

注意

javascriptの使い方が正しいか自信がないです。（特にthisの部分とか）
あと、call by need ではなく、 call by nameになっていると想います。
ここに書いてあることの正しさは保証できません

Streamの作成

//Streamのconstructor
function Stream(hd,tl){
	this.hd = hd;
	this.tl = tl; //tlは関数
	//this.display = function(){print("hd=",this.hd," tl=",this.tl)};
}

//アクセスはhdとtlを通してできる。


//Streamのn番目の要素を表示する。
function stream_ref(s,n){
	if (n == 0) {
    return s.hd
  } else {
    return stream_ref(s.tl(), n-1);
  }
}

//0からn番目までの要素を配列にして返す
function stream_to_list(s, n){
	var re = []
	for(var i=0;i<n;i++){
		re[i] = s.hd;
		s = s.tl();
	}
	return re
}

とりあえず実験

自然数のStreamを作成して、表示してみる。

//fromで与えた値から始まる自然数のStreamを返す。
function integer_stream_from(from){
	return new Stream(from,function(){return new Stream(this.hd+1,this.tl)})
}

var s = integer_stream_from(1);
print(stream_ref(s,100))
// 101
print(stream_to_list(s,5));
// 1,2,3,4,5

一応、動いているみたいです。

Streamに操作を加えてみる。

filter関数を定義してみます。

//条件式に合った値のみからなるStreamを返す。
function stream_filter(p,s){
	if (p(s.hd)){
		return new Stream(s.hd, function(){return stream_filter(p, s.tl())})
	} else{
		return stream_filter(p, s.tl())
	}
}

//実験
var nums = integer_stream_from(2); //2から始まってる
var s = stream_filter(function(e){return e%2==0}, nums);
print(stream_ref(s,5))
// 12 //[2,4,6,8,10,12]だから合っている
var ss = stream_filter(function(e){return e>100},s);
      //100より小さい値は存在を消す(ssのStream的に)
print(stream_to_list(ss,5));
// 102,104,106,108,110

組み合わせて素数だけからなるStreamを作ってみる。

エラトステネトスの篩というものが作れる。

エラトステネトスの篩自体はこんな感じのアルゴリズムです。

function f(n){
	var a = [];
	var re = [];
	for(var i =2; i<n; i++){ 
		a[i] = i;
	}
	while (a.length!=0){
		var x = a.shift();
		var a = a.filter(function(e){return e%x!=0});
		re.push(x);
	}
	return re;
}
 print(f(100));
// ,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97

Streamを使った場合

//篩
function sieve(s){
	var nextf = function(){
		return sieve(stream_filter(function(e){return e%s.hd!=0}, s))
	}
	return new Stream(s.hd,nextf);
}

//実験
var nums = integer_stream_from(2);
print(stream_to_list(sieve(nums), 7));
// 2,3,5,7,11,13,17
print(stream_ref(sieve(nums),100));
// 547

一応動いてます。（でもとても遅いです＞＜）