unorderedTraverse throws a Stackoverflow Error about cats HOT 6 CLOSED

I don't see how that PR can do it, but maybe. The code you are running is here I think:

and that code is just not stack safe.

To make it stack safe, we could need to have a similar tree style approach as the PR you linked.

Or, and I think this is simpler, internal to the unorderedTraverse for Map just call .toList on the Map, do the traverse there, then call .toMap. If you are converting toList however, I imagine converting to Vector and using traverseViaChain then converting to Map will be more efficient?

from cats.

we should definitely add this test though, and while we are at it see if there are other UnorderedTraverse instances that may also have an issue.

from cats.

I think the key takeaway here is that it was stack safe in 2.6.1 and I think this was an unexpected side effect of 2.7.0

from cats.

I think we should do a git bisect to find the issue. There were a lot of changes. I don't see how the code you linked is even in the call graph of this example (it may be, I just don't see how).

Also, the current code is not stack safe which you can clearly see (it builds up a linear depth computation).

It is interesting that the difference seems to be with Tuple2 applicative though, and it works here with Option.

Lastly, I'd note that 500 is pretty low to be causing stack overflows. I wonder if the Option example works with say 10000?

from cats.

Tested it with 10000:
val m: Map[Int, Int] = (1 to 10000).map(x => x -> x).toMap
it constructed the map and Scastie hangs after testing Option monad

from cats.

I don't see how that PR can do it, but maybe. The code you are running is here I think:

cats/core/src/main/scala/cats/instances/map.scala

Line 42 in 9ad3aa5

def unorderedTraverse[G[_], A, B](

and that code is just not stack safe.

To make it stack safe, we could need to have a similar tree style approach as the PR you linked.

Or, and I think this is simpler, internal to the unorderedTraverse for Map just call .toList on the Map, do the traverse there, then call .toMap. If you are converting toList however, I imagine converting to Vector and using traverseViaChain then converting to Map will be more efficient?

cats/core/src/main/scala/cats/data/Chain.scala

Line 995 in 9ad3aa5

def traverseViaChain[G[_], A, B](

I might take a look at it. Writing tests to check for SO should be easy.

from cats.