Implementation of ChainRec from Fantasy Land specification for Array

readme.md

Implementation of ChainRec from Fantasy Land specification for Array

Array.chainRec.js

var flatten = Function.prototype.apply.bind([].concat, [])
Array.prototype.chain = function(f) {
  return flatten(this.map(f))
}

var stepNext = function (x) { return {value: x, done: false }; };
var stepDone = function (x) { return {value: x, done: true }; };
Array.chainRec = function _chainRec(f, i) {
  var todo = [i];
  var res = [];
  var buffer, xs, idx;
  while (todo.length > 0) {
    xs = f(stepNext, stepDone, todo.shift());
    buffer = [];
    for (idx = 0; idx < xs.length; idx += 1) {
      (xs[idx].done ? res : buffer).push(xs[idx].value);
    }
    todo.unshift.apply(todo, buffer);
  }
  return res;
}



// # example 1
//
// generate strings with all combination of `a` and `b` 
// ending with `!` or `?`
// [ "aaaaa!",  "aaaaa?", "aaaab!", "aaaab?", ..... ]
//
// ## using chain
function example1chain(){
  function rec(i) {
    if (i.length == 2){
      return [i+"!", i+"?"]
    }
    return [i+"a", i+"b"].chain(rec)
  }
  return rec("")
}

// ## using chainRec
function example1chainRec(){
  return Array.chainRec(function(next, done, n) {
    if (i.length == 2){
      return [i+"!", i+"?"].map(done)
    }
    return [i+"a", i+"b"].map(next)
  }, "")
}


// # example 2
//
// just perform subtraction multiple times
//
// ## using chain
// here stack will overflow
function example2chain(){
  function rec(next, done, n) {
    if (n === 0) {
      return ['DONE']
    }
    return [n - 1].chain(rec)
  }
  return rec(100000)
}

// ## using chainRec
// here stack will not overflow 
function example2chainRec() {
  Array.chainRec(function(next, done, n) {
    if (n === 0) {
      return [done('DONE')]
    } else {
      return [next(n - 1)]
    }
  }, 100000)  
}

did you mean to type n instead of i?

https://gist.github.com/safareli/ea45b45bed99f32bae7002e19dcf13c2#file-array-chainrec-js-L45-L48