StackOverflowError on traverse[Kleisli[F, A, ?], B]

[TVerse]

The following snippet throws a StackOverflowError (assuming kind-projector plugin):

import cats.data.Kleisli
import cats.implicits._

// Probably any F that has Traverse[F], I was trying to use cats.effect.IO
type F[A] = List[A]
List.fill(100000)(1).traverse[Kleisli[F, Int, ?], Int](a => Kleisli.pure(a)).run(1)

The equivalent snippet without Kleisli (List.fill(100000)(1).traverse[F, Int](a => Applicative[F].pure(a))) runs as expected.

Top of the stacktrace:

Exception in thread "main" java.lang.StackOverflowError
	at cats.data.KleisliApply.$anonfun$product$2(Kleisli.scala:422)
	at cats.data.Kleisli.$anonfun$map$1(Kleisli.scala:19)
	at cats.data.KleisliApply.$anonfun$product$2(Kleisli.scala:422)
	at cats.data.Kleisli.$anonfun$map$1(Kleisli.scala:19)
	at cats.data.KleisliApply.$anonfun$product$2(Kleisli.scala:422)
	at cats.data.Kleisli.$anonfun$map$1(Kleisli.scala:19)
	at cats.data.KleisliApply.$anonfun$product$2(Kleisli.scala:422)
	at cats.data.Kleisli.$anonfun$map$1(Kleisli.scala:19)
...

[ceedubs]

@alexandru recently did some nice stack-safety work for Kleisli in #2185. I've confirmed that this is still the case after that merge (which makes sense, since it was done on flatMap). @alexandru do you think that there might be any similar fixes possible in this sort of context?

[peterneyens]

Overriding map2 in KleisliMonad using the pure + flatMap suspension trick, doesn't overflow the stack for Eval

override def map2[B, C, D](fb: Kleisli[F, A, B], fc: Kleisli[F, A, C])(f: (B, C) => D): Kleisli[F, A, D] =
  Kleisli(a => F.flatMap(F.pure(()))(_ => F.map2(fb.run(a), fc.run(a))(f)))

Maybe we can come up with something better though ...?

---

The easiest solution at the moment (I think) is to lift to Free, like @johnynek mentioned in #1733:

List.fill(100000)(1).traverse[Free[Kleisli[F, Int, ?], ?], Int](a =>
  Free.liftF(Kleisli.pure(a))
).runTailRec.run(1)

[alexandru]

The SyncLaws in cats-effect only test for the stack safety of flatMap and map and unfortunately I missed map2 and ap 😐

This solution defers the stack safety to F[_]. The better solution for IndexedStateT was to use the AndThen implementation, but I couldn't find a way to make it work for Kleisli.

I lean towards doing the same trick for map2, like @peterneyens is suggesting and pushing it in the next release.

When is that scheduled btw?

[johnynek]

This feels a little off to me, like we are smuggling a suspend into Monad.

I mean, we could have a function like that with the only law that it is the same as identity, but it feels like code smell.

I hate to copy that pure/flatMap snippet around though because we somehow feel that is okay but naming it is not.

Maybe unsafeSuspend?

I would prefer a more direct assault on Traverse stack safety. If we could find an analog of tailRecM for applicatives we would be in business.

[alexandru]

You mean we need a name for F.unit.flatMap(f)? I could agree with a name. defer is available.

That said Kleisli's current encoding is A => F[B] and the flatMap takes an f: B => Kleisli[F, A, C]. And we are in a tough spot with this one because:

1. we need that A input twice, once for generating F[B] and a second time for generating F[C]
2. whatever we do, we'll end up building another A => F[C] that depends on the current A => F[B]

I couldn't find a way for the AndThen trick (of #2187) to work. And so deferring the stack safety to F[_] seems like the reasonable option.

Note that tailRecM does not help. Also, this feels very, very specific to Kleisli. As IndexedStateT did not need the same treatment.