Skip to content

Instantly share code, notes, and snippets.

@AutoSponge
Last active December 15, 2015 16:59
Show Gist options
  • Save AutoSponge/5293209 to your computer and use it in GitHub Desktop.
Save AutoSponge/5293209 to your computer and use it in GitHub Desktop.
//don't use native bind... it's too slow
function recur(fn) {
return function () {
var bounce = fn.apply(this, arguments);
while (bounce.call) {
bounce = bounce();
}
return bounce;
};
}
function bind(fn, receiver) {
return function () {
var args = arguments;
return function () {
return fn.apply(receiver || this, args);
};
};
}
var sum = bind(function (x, y) {
return y > 0 ? sum(x + 1, y - 1) :
y < 0 ? sum(x - 1, y + 1) :
x + this.test;
}, {test: "done"});
var sum1 = recur(sum);
sum1(1, 50000);
//a cleaner approach?
function recur(fn) {
return function () {
var bounce = fn.apply(this, arguments);
while (bounce.call) {
bounce = bounce();
}
return bounce;
};
}
var sum = Function.call.bind.bind(function (x, y) {
return y > 0 ? sum(x + 1, y - 1) :
y < 0 ? sum(x - 1, y + 1) :
x;
}, null);
var sum1 = recur(sum);
sum1(1, 50000);
function recur(fn) {
return function () {
var bounce = fn.apply(this, arguments);
while (bounce.call) {
bounce = bounce();
}
return bounce;
};
}
var sum1 = recur(function sum(x, y) {
return function() {
return y > 0 ? sum(x + 1, y - 1) :
y < 0 ? sum(x - 1, y + 1) :
x;
};
});
sum1(1,50000);
function recur(fn) {
return function () {
var bounce = fn.apply(this, arguments);
while (typeof bounce !== "number") {
bounce = fn.apply(this, bounce);
}
return bounce;
};
}
var fact = recur(function (n, val) {
return n > 1 ? [n - 1, n * (val || 1)] : val;
});
fact(10);
//needs bigint implementation, this just shows the idea
//modified to use a continuation and trampoline
function trampoline(fn) {
return function () {
var bounce = fn.apply(this, arguments);
while(typeof bounce === "function") {
bounce = bounce();
}
return bounce;
}
}
var fact = trampoline(function (n) {
var n1 = n,
val = 1;
return function bounce() {
return n1 > 1 ? (val = n1 * val) && (n1 -= 1) && bounce : val;
};
});
fact(10);
/*the all-in-one version*/
var fact = function (n) {
var n1 = n,
val = 1,
result;
function bounce() {
return n1 > 1 ? (val = n1 * val) && (n1 -= 1) && bounce : val;
}
result = bounce();
while (typeof result === "function") {
result = bounce();
}
return result;
};
fact(10);
/*all-in-one with a short-circuit*/
var fact = function (n) {
var n1 = n,
val = 1,
result;
function bounce() {
return (val = n1 * val) && (n1 -= 1) && bounce || val;
}
result = bounce();
while (n1 > 0) {
result = bounce();
}
return result;
};
fact(10);
function getInstance(self, constructor) {
return self instanceof constructor ? self : new constructor;
}
function done(result) {
var self = getInstance(this, done);
self.isDone = true;
self.result = result;
return self;
}
function cont(thunk) {
var self = getInstance(this, cont);
self.isDone = false;
self.thunk = thunk;
return self;
}
function trampoline(bounce) {
while(!bounce.isDone) {
bounce = bounce.thunk();
}
return bounce.result;
}
function recurse(n) {
function inner(i) {
//if (i > 20790) console.log(i);
if (i === n) {
return done(n);
}
return cont(function() {
return inner(i + 1);
});
}
return trampoline(inner(0));
}
recurse(20800);
/* fails to reach a point where it can console results */
function recurse(i) {
if (i > 20799) console.log(i);
return i < 20800 ? recurse(i + 1) : 20800;
}
recurse(0);
function trampoline(bounce) {
while(bounce.thunk) {
bounce = bounce.thunk();
}
return bounce.result;
}
function recurse(n) {
function inner(i) {
if (i === n) {
return {
result: n
};
}
return {
thunk: function() {
return inner(i + 1);
}
};
}
return trampoline(inner(0));
}
recurse(20800);
//this version more clearly demonstrates the technique.
//this version probably also outperforms the other, jsperf incoming
@buzzdecafe
Copy link

great job, nice tight and elegant code. as discussed, the only drawback is you can't return a function from the recursion.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment