javascriptfunctional-programminglazy-evaluationcorecursioncodata

How to encode corecursion/codata in a strictly evaluated setting?

Corecursion means calling oneself on data at each iteration that is greater than or equal to what one had before. Corecursion works on codata, which are recursively defined values. Unfortunately, value recursion is not possible in strictly evaluated languages. We can work with explicit thunks though:

const Defer = thunk =>
  ({get runDefer() {return thunk()}})

const app = f => x => f(x);

const fibs = app(x_ => y_ => {
  const go = x => y =>
    Defer(() =>
      [x, go(y) (x + y)]);

  return go(x_) (y_).runDefer;
}) (1) (1);

const take = n => codata => {
  const go = ([x, tx], acc, i) =>
    i === n
      ? acc
      : go(tx.runDefer, acc.concat(x), i + 1);

  return go(codata, [], 0);
};

console.log(
  take(10) (fibs));

While this works as expected the approach seems awkward. Especially the hideous pair tuple bugs me. Is there a more natural way to deal with corecursion/codata in JS?

Solution

  • I would encode the thunk within the data constructor itself. For example, consider.

    // whnf :: Object -> Object
const whnf = obj => {
    for (const [key, val] of Object.entries(obj)) {
        if (typeof val === "function" && val.length === 0) {
            Object.defineProperty(obj, key, {
                get: () => Object.defineProperty(obj, key, {
                    value: val()
                })[key]
            });
        }
    }

    return obj;
};

// empty :: List a
const empty = null;

// cons :: (a, List a) -> List a
const cons = (head, tail) => whnf({ head, tail });

// fibs :: List Int
const fibs = cons(0, cons(1, () => next(fibs, fibs.tail)));

// next :: (List Int, List Int) -> List Int
const next = (xs, ys) => cons(xs.head + ys.head, () => next(xs.tail, ys.tail));

// take :: (Int, List a) -> List a
const take = (n, xs) => n === 0 ? empty : cons(xs.head, () => take(n - 1, xs.tail));

// toArray :: List a -> [a]
const toArray = xs => xs === empty ? [] : [ xs.head, ...toArray(xs.tail) ];

// [0,1,1,2,3,5,8,13,21,34]
console.log(toArray(take(10, fibs)));

    This way, we can encode laziness in weak head normal form. The advantage is that the consumer has no idea whether a particular field of the given data structure is lazy or strict, and it doesn't need to care.