Skip to content

Instantly share code, notes, and snippets.

@norswap norswap/why.js
Created Sep 1, 2019

Embed
What would you like to do?
Y Combinator and Trampolines in Javascript
const assert = require('assert');
// const is_even = n =>
// (n === 0) || !is_even(n - 1);
const mock_is_even = (myself, n) =>
(n === 0) || !myself(myself, n - 1);
const mockingbird =
fn =>
(...args) =>
fn(fn, ...args);
// const is_even = mockingbird(mock_is_even);
// assert(is_even(10));
// assert(!is_even(11));
const memoized = fn => {
const map = new Map();
return (...args) => {
const key = JSON.stringify(args);
return map[key] || (map[key] = fn(...args));
}
}
// const is_even_memo = mockingbird(memoized(mock_is_even));
// assert(is_even_memo(10));
// assert(!is_even_memo(11));
// console.time('slow');
// is_even_memo(100);
// console.timeEnd('slow');
// console.time('fast');
// is_even_memo(100);
// console.timeEnd('fast');
const Y_is_even = (myself, n) => (n === 0) || !myself(n - 1);
const Y = fn => {
const wrapper = (...args) => fn(wrapper, ...args);
return wrapper;
}
const is_even = Y(Y_is_even);
assert(is_even(10));
assert(!is_even(11));
const is_even_memo = Y(memoized(Y_is_even));
console.time('slow');
is_even_memo(100);
console.timeEnd('slow');
console.time('fast');
is_even_memo(100);
console.timeEnd('fast');
const longtailed = fn => (...args0) => {
class Thunk {
constructor (delayed) {
this.delayed = delayed;
}
evaluate () {
return this.delayed();
}
}
const wrapper = (...args) =>
new Thunk(() => fn(wrapper, ...args));
let value = fn(wrapper, ...args0);
while (value instanceof Thunk)
value = value.evaluate();
return value;
}
const Y_is_even_tailrec = (myself, n) =>
n === 0 ? true :
n === 1 ? false :
myself(n - 2);
const iter_is_even = longtailed(Y_is_even_tailrec);
assert(iter_is_even(10));
assert(!iter_is_even(11));
// No problem!
iter_is_even(1000000);
// Maximum call stack size exceeded
// is_even(1000000);
const iter_is_even_memo = longtailed(memoized(Y_is_even_tailrec));
assert(iter_is_even_memo(10));
assert(!iter_is_even_memo(11));
console.time('slow');
iter_is_even_memo(100);
console.timeEnd('slow');
console.time('fast');
iter_is_even_memo(100);
console.timeEnd('fast');
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.