Skip to content

Instantly share code, notes, and snippets.

@ivenmarquardt
Last active May 18, 2018 20:37
Show Gist options
  • Star 8 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ivenmarquardt/046a6a680593cc007efa4f25541b6b5d to your computer and use it in GitHub Desktop.
Save ivenmarquardt/046a6a680593cc007efa4f25541b6b5d to your computer and use it in GitHub Desktop.
Lazy evaluation, lazy getters, eta reduction, function composition, implicit thunks through deferred type
// Lazy Getters
/* What enables Tail Recursion Modulo Cons in Javascript is a thunk in Weak Head Normal Form.
An expression in weak head normal form has been evaluated to the outermost data constructor,
but contains sub-expressions that may not have been fully evaluated. In Javascript only thunks
can prevent sub-expressions from being immediately evaluated. */
const cons = (head, tail) => ({head, tail});
let list;
for (let i = 1e5; i > 0; i--)
list = cons(i, list);
const take = n => ({head, tail}) =>
head === undefined || n === 0
? {}
: {head, get tail() {return take(n - 1) (tail)}};
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ not yet evaluated sub-expression
take(1e5) (list); // stack safe
// ETA Expansion
const fix = f => x => f(fix(f)) (x);
// ^ ^^^
const fact = fix(
f => n => (n === 0) ? 1 : n * f(n - 1)); // stack safe
fact(10); // 3628800
// Function Composition
/* While composition is known to produce point-free code
its ability to obtain the lazy evaluated argument effect
is more important in strictly evaluated languages. */
comp = f => g => x => f(g(x));
// ^^^^
// Implicit Thunks through Defer Type
const Data = name => Dcons => {
const Data = x => {
const t = new Tcons();
Object.defineProperty(
t,
typeof x === "function" ? `run${name}` : `get${name}`,
{value: x});
t[Symbol.toStringTag] = name;
t.tag = name;
return t;
};
const Tcons =
Function(`return function ${name}() {}`) ();
return Dcons(Data);
};
const Defer = Data("Defer")
(Defer => thunk => Defer(thunk));
Defer.map = f => tx => Defer(() => f(tx.runDefer()));
Defer.ap = af => ax => Defer(() => af.runDefer() (ax.runDefer()));
const add = m => n => m + n;
const sqr = n => Defer(() => n * n);
const z = Defer.ap(
Defer.map(add)
(sqr(5)))
(sqr(5));
// nothing has been evaluated up to this point
z.runDefer(); // 50
// we can express infinite streams like in Haskell
const repeat = x => Defer(() => [x, repeat(x)]);
Defer.map(
([head, tail]) => [sqr(head), tail])
(repeat(5))
.runDefer(); // [25, Defer]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment