Lazy evaluation, lazy getters, eta reduction, function composition, implicit thunks through deferred type

lazy-evaluation.js

// 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]