1

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?

  • Why not just define `const Defer = thunk => thunk;` and use `()` instead of `.runDefer`? Do you consider the latter more readable? – Patrick Roberts Mar 04 '20 at 19:03
  • @PatrickRoberts Yes, I think it is more readable and provides more "type safety" to use a object wrapper instead of a bare thunk. For the same reason I use `app` instead of an IIFE. –  Mar 04 '20 at 19:12

1 Answers1

1

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.

Aadit M Shah
  • 72,912
  • 30
  • 168
  • 299
  • This is an amazing idea, as always. I think I prefer `tail` to be always in WHNF so that I can define the getter logic directly within the respective constructor, e.g. `cons = (head, tail) => ({head, get tail() {return tail()}})`. This way there is no need for object introspection and associated pitfalls like `(...args) => "I am not a thunk"` can be avoided. The downside is that I have to use `cons` always with a thunk as 2nd argument. By using a smart getter that replaces itself after the 1st invokation we could additionally obtain a sharing "effect". –  Mar 06 '20 at 17:54
  • WHNF was the missing piece of the puzzle. Thanks again! First class functions and the ability to create expressions in WHNF are the main ingredients for a language to be a good fit for the functional paradigm. With object getters we can express value recursion in JS. Here is a [proof of concept](https://repl.it/repls/LividCoolParallelcomputing) to create transparent thunks so that we can define lazy functions like `unfoldr, which can handle infinite lists. –  Mar 07 '20 at 15:41