javascript lazy seq

lazyseq.js

function isFunction(x){
  return typeof(x) === 'function';
}

function jsBool(x){
  return !( x === null || x === undefined || x === false);
}

function isSeq(x){
  return jsBool(x.myType === "seq");
}

function isEmpty(x){
  if(x === null){
    return true;
  }else if(Array.isArray(x)){
    return x.length === 0;
  }else if(isFunction(x.isEmpty)){
    return x.isEmpty();
  }else if(isFunction(x)){
    throw new Error("no cdr implementation for function. here's the function: " + x.toString());
  }else{ // could extend for objects etc etc
    throw new Error("can't do isEmpty check on this. type: " + typeof(x));
  }
}

// this one is a little mysterious
function seq(xs){
  if(isEmpty(xs)){
    return null;
  }else if(isSeq(xs)){
    return xs;
  }else{
    var cdrbuddy = thunk(function(){return seq(cdr(xs));});
    return {myType: "seq",
	    isEmpty: function(){return isEmpty(xs);},
	    car: function(){return car(xs);},
	    cdr: function(){return cdrbuddy.deref();}};
  }
}

function cons(x, ys){
  var thk = thunk(function(){return seq(ys);});
  return {myType: "cons",
	  args: [x, ys],
	  isEmpty: function(){return false;},
	  car: function(){return x;},
	  cdr: function(){
	    if(isEmpty(ys)){
	      return null;
	    }else{
	      return thk.deref();
	    }
	  }};
}

function car(x){
  if(x === null){
    return null;
  }else if(isFunction(x.car)){
    return x.car();
  }else if(Array.isArray(x)){
    if(0 < x.length){
      return x[0];
    }else{
      return null;
    }
  }else{
    throw new Error("no car implementation found. type: " + typeof x);
  }
}

function arCdr(ar){
  function step(i){
    if(i < ar.length){
      return cons(ar[i], lazySeq(function(){return step(i + 1);}));
    }else{
      return null;
    }
  };
  return step(1);
}

function cdr(x){
  if(x === null){
    return null;
  }else if(isFunction(x.cdr)){
    return x.cdr();
  }else if(Array.isArray(x)){
    if(0 < x.length){
      return arCdr(x);
    }else{
      return null;
    }
  }else if(isFunction(x)){
    throw new Error("no cdr implementation for function. here's the function: " + x.toString());
  }else{
    throw new Error("no cdr implementation found");
  }
}

function thunk(delayedF){
  return {realized: false,
	  state: null,
	  deref: function(){
	    if(this.realized){
	      return this.state;
	    }else{
	      var result = delayedF();
	      this.state = result;
	      this.realized = true;
	      return result;
	    }
	  }};
}

function lazySeq(delayedF){
  var thk = thunk(delayedF);
  var lsq = {myType: "lazySeq",
	     isEmpty: function(){return isEmpty(thk.deref());},
	     car: function(){return car(thk.deref());},
	     cdr: function(){
	       if(this.isEmpty()){
		 return null;
	       }else{
		 return lazySeq(
		   function(){
		     return cdr(thk.deref());});}},
	     reduce: function(f, init){
	       var state = init;
	       var xs = this;
	       while(!isEmpty(xs)){
		 state = f(state, car(xs));
		 xs = cdr(xs);
	       }
	       return state;
	     }};
  return lsq;
}

function take(n, xs){
  return lazySeq(function(){
    if(n < 1 || isEmpty(xs)){
      return null;
    }else{
      return cons(car(xs), take(n - 1, cdr(xs)));
    }});
}

function iterate(f, x){
  return cons(x, lazySeq(function(){return iterate(f, f(x));}));
}

function last(xs){
  return xs.reduce(function(ar, x){return x;}, null);
}

function range(start, end, jump){
  var step = function(n){
    if(!(n < end)){
      return null;
    }else{
      return cons(n, step(n + jump));
    }
  };
  return step(start);
}

// use this to smoosh (finite!) lazy seq into an array
function intoArray(xs){
  return xs.reduce(function(ar, x){ar.push(x); return ar;}, []);
}

so

> intoArray(take(10, iterate(function(x){return x + 1;}, 0)))
[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]