Maximum call stack size for Async monad

[mohaalak]

Describe the bug Async Monad will raise error call stack size

To Reproduce

import {Async, traverse, map} from 'crocks';
import {range} from 'ramda';

const wrap = a => Async((rej, res) => res(a))

traverse(Async.of, wrap, range(0, 4000)).fork(console.error, console.log)

Expected behavior I think we can trampoline so we don't get this error.

Additional context maybe there is another way for traverse that I'm not aware of.

[evilsoft]

Will look into this and see about getting a fix out on the next release. Sorry about the inconvenience.

[karthikiyengar]

@evilsoft - In case you're not looking into this already, I'd be very eager to pick this one up.

[evilsoft]

@karthikiyengar go for it, was looking into various trampoline techniques as well as some nasty business of using an internal queue that we can for each over (but that is horrible). the hard part is keeping the functions in place and not moving to class definitions.

This will effect pretty much every type, for chaining though, we do have the chainRec spec we can implement.

[tounano]

Hi all,

The same thing actually happened to me on State monad.

And unfortunately, it will happen with every Monad that has lazy computation. It also happens with every library out there.

This is due to composition.

Here's an example:

const { add, range } = require('ramda');
const { compose } = require('crocks');

const addAll = range(0, 10000)
                          .map(x => add(x))
                          .reduce((x,y) => compose(x,y))
addAll(0);

This will crash your stack, this is the root cause.

It happens even with a really simple compose function:

const composeTwo = (f,g) => x => f(g(x))

I was able to fix the problem by creating a better compose, that can compose an infinite number of functions without overloading the stack.

I actually developed two versions of such compose.

The highlights of V1 is that it doesn't compose in real time, it creates a tree of composition using arrays. When the function is finally called it flattens the array. It sounds crazy but it's like 10 loc and a few helpers.

I didn't like this solution much, so I developed something with a lazy sequence and a trampoline, this is a pretty elegant solution, which I really like.

I also benchmarked my solutions and surprisingly, the first solution (the one with a Tree/Array representation) is pretty robust. It performed better than compose from both crocks and ramda. But worth than composeTwo above.

After doing that, I realized something...

Composing a function so much is a code smell. You don't really need that much compositions.

The real problem is with traverse...

Traverse is a nice function, but it's really not efficient. It's usefulness comes from the fact that it's really generic and would apply for all types of Monads, however it can never be efficient because it doesn't know the underlying structure of data type.

And then I came up with a function I called invertState, but if you know the internal data structure, you can code it for pretty much any datatype.

I was able to turn around an array with many 1000s states into a State of array of 1000s items.

// invertState :: [State s x] -> State s [x]
const invertState = ss => 
  State(s => 
    ss.reduce((acc, currentState) => {
      const resolvedState = currentState.runWith(acc.snd())

      return acc.bimap(
        append(resolvedState.fst()),
        constant(resolvedState.snd())
      )
    }, Pair([], s))
    )

Now, this one works on Array State, but it's really easy to turn it around to work on Monoid State.

@evilsoft I can send a pull request with an upgraded version (that also follows community standards), but it's your decision if you want to include it in the API.

For future reference, if someone in the future would get a Call Stack error, 99% chance it's because you're traversing.

[JamieDixon]

If anyone's interested I implemented a version of trampolines using Proxy that doesn't require any changes to the function signature being trampolined. Usually there's a requirement to return a function from a trampolined function but this solution I've put together allows the original function to be wrapped, unmodified.

It's here for inspiration if anyone's keen: https://repl.it/@jamiedixon/safe-recur#index.js

[dalefrancis88]

Nice work, just seen this, thanks for sharing!