Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
// a tree
var t = {
left: {
left: {
left: null,
right: null
},
right: null
},
right: {
left: null,
right: null
}
};
// v1: recursive
var depth = function(t) {
if (t == null) {
return 0;
} else {
return 1 + Math.max(depth(t.left), depth(t.right));
}
};
depth(t);
// v2: cps, still recursive
var id = function(x) {
return x;
};
var depth_cps = function(t, k) {
if (t == null) {
return k(0);
} else {
return depth_cps(t.left, function(r1) {
return depth_cps(t.right, function(r2) {
return k(1 + Math.max(r1, r2));
});
});
}
};
depth_cps(t, id);
// v3: trampolining, non recursive
var depth_cps2 = function(t, k) {
if (t == null) {
return k(0);
} else {
return function() {
return depth_cps2(t.left, function(r1) {
return function() {
return depth_cps2(t.right, function(r2) {
return k(1 + Math.max(r1, r2));
});
};
});
};
}
};
var depth_trampoline = function(t) {
var bounce = depth_cps2(t, id);
while (typeof bounce == "function") {
bounce = bounce();
}
return bounce;
}
depth_trampoline(t);
// make a deep tree
var t2 = (function() {
var r = {};
var rr = r;
for (var i = 0; i < 100000; ++i) {
rr.left = {};
rr.right = null;
rr = rr.left;
}
rr.left = null;
return r;
})();
depth(t2); // Safari: 'max stack exceeded'
depth(t2, id); // as above
depth_trampoline(t2); // works
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.