javascriptrecursionfunctional-programminglazy-evaluationtrampolines

Trampoline, recursion and lazy evaluation


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:

Imgur

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?


Solution

  • I think this should do it while still being lazy1:

    var filter = curry(function(f, seq){
      while (seq != null && !f(head(seq)))
          seq = tail(seq);
      if (seq == null)
        return;
      return cons(head(seq), function() {
        return filter(f, tail(seq))
      });
    });
    

    Maybe easier readable:

    var filter = curry(function(f, seq){
      for (; seq != null; seq = tail(seq))
        if ( f(head(seq)) )
          return cons(head(seq), function() {
            return filter(f, tail(seq))
          });
    });
    

    1): Your representation of lazy sequences does not seem to have a way to express a maybe-empty (yet undetermined) list