I'm trying to implement basic lazy sequences in JavaScript. I'm only using closures and continuations. This is what I got so far:
var cons = curry(function(x, y, list){
return list(x, y);
});
var head = function(seq){
return seq(function(x, y){
return x;
});
};
var tail = function(seq){
return seq(function(x, y){
return y();
});
};
var iterate = function(f){
var next = f();
if (next != null) {
return cons(next, function(){
return iterate(f);
});
}
};
var take = curry(function(n, seq){
if (n && seq != null) {
return cons(head(seq), function(){
return take(n - 1, tail(seq));
});
}
});
var doSeq = curry(function(n, f, seq){
while (n-- && seq != null) {
f(head(seq));
seq = tail(seq);
}
});
var rand = iterate(Math.random);
var log = function(x){ console.log(x) };
doSeq(10, log, rand); //=> logs 10 random numbers
I didn't post the curry function as it isn't directly related to the question.
Now the deal breaker is filter
. The canonical implementation is tail recursive:
var filter = curry(function(f, seq){
if (seq == null) {
return;
}
if (!f(head(seq))) {
return filter(f, tail(seq)); // recursion
}
return cons(head(seq), function(){
return filter(f, tail(seq));
});
});
When I run it many times on a sequence the stack will eventually blow up:
I know a common workaround is to use a trampoline, and that's relatively easy in an eager world, but it seems daunting to implement it for a lazy sequence. I found an intricate solution in Scheme, but I gave up on trying to implement it as-is in JavaScript.
Is this as complicated as it seems? Is there another way to solve this issue, with iteration maybe? Any hints on porting the Scheme code to JavaScript in a sane way?