You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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:
// Catamorphismconstcata=B=>alg=>{constrec=xs=>alg(B.map(rec)(xs));returnrec;};// Initial algebraconstNil=undefined;constCons=x=>xs=>({ x, xs });constmatch=({ Nil, Cons })=>l=>{if(l===undefined)returnNil;const{ x, xs }=l;returnCons(x)(xs);};// Base functor// Don't really need a separate ListF set of constructors, it's already polymorphic in `xs`constListBase=(()=>{constmap=f=>match({
Nil,Cons: x=>xs=>Cons(x)(f(xs))});return{ map };})();constsum=cata(ListBase)(match({Nil: 0,Cons: x=>xs=>x+xs}));constxs=Cons(1)(Cons(2)(Cons(3)(Nil)));constresult=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 😅).
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.
The text was updated successfully, but these errors were encountered:
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.
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:
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 😅).
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
.The text was updated successfully, but these errors were encountered: