Stack usage

[masaeedu]

This is probably going to be a little off topic, apologies in advance. I'm trying to write recursion schemes in JS, but I'm having issues with stack usage. For example:

// Catamorphism
const cata = B => alg => {
  const rec = xs => alg(B.map(rec)(xs));
  return rec;
};

// Initial algebra
const Nil = undefined;
const Cons = x => xs => ({ x, xs });
const match = ({ Nil, Cons }) => l => {
  if (l === undefined) return Nil;

  const { x, xs } = l;
  return Cons(x)(xs);
};

// Base functor
// Don't really need a separate ListF set of constructors, it's already polymorphic in `xs`
const ListBase = (() => {
  const map = f =>
    match({
      Nil,
      Cons: x => xs => Cons(x)(f(xs))
    });

  return { map };
})();

const sum = cata(ListBase)(match({ Nil: 0, Cons: x => xs => x + xs }));

const xs = Cons(1)(Cons(2)(Cons(3)(Nil)));
const result = sum(xs);

console.log(result);
// => 6

The code above works fine, but if I scale the list up to 100000 elements, I'm going to end up setting up a giant 10,000 frame deep call and blow the stack. I was wondering if this sort of problem is unavoidable (at least with catamorphisms), and if not, how this library solves it (hopefully in a way I can imitate in JS :sweat_smile:).

I can think of a way to write a list-specific iterativeCata that reifies the stack in an array, and does things iteratively, but that will be list-specific and won't work for e.g. TreeF.

[sellout]

In general, there are two ways to deal with this – one is to do a monadic fold with a trampoline (this is a bit tricky, and often requires using hyloM rather than just cataM). The other approach is described in the Clowns/Jokers paper, and I haven’t seen it implemented yet.

[masaeedu]

I think I understand how to do this now. Thanks!

[safareli]

@masaeedu this might help https://medium.com/@safareli/stack-safe-function-composition-85d61feee37e