Surprise behavior with map2, map2Eval, and flatMap

[adelbertc]

Playing with some finally tagless as one would expect of me. Some surprising behavior, not sure if intended. Here's the Scalaz version, which works fine, doesn't blow stack (scroll to the bottom of the snippet to ScalazApp to get to the point):

package taglessStackSafety

import scalaz._
import scalaz.Free.Trampoline
import scalaz.Scalaz._

trait MonadSet[F[_]] extends Monad[F] {
  def add(int: Int): F[Unit]
  def exists(int: Int): F[Boolean]
}

object MonadSet {
  def apply[F[_]](implicit F: MonadSet[F]): MonadSet[F] = F

  // Dummy impl for a stack safe target monad
  implicit val trampolineInterpreter: MonadSet[Trampoline] = new MonadSet[Trampoline] {
    def add(int: Int): Trampoline[Unit] = Trampoline.done(())
    def exists(int: Int): Trampoline[Boolean] = Trampoline.done(true)
    def point[A](x: => A): Trampoline[A] = Trampoline.delay(x)
    def bind[A, B](fa: Trampoline[A])(f: A => Trampoline[B]): Trampoline[B] = fa.flatMap(f)
  }
}

trait TaglessSet[A] {
  def apply[F[_]: MonadSet]: F[A]
}

object TaglessSet {
  implicit val instance: Monad[TaglessSet] =
    new Monad[TaglessSet] {
      def point[A](x: => A): TaglessSet[A] = new TaglessSet[A] {
        def apply[F[_]: MonadSet]: F[A] = MonadSet[F].point(x)
      }

      def bind[A, B](fa: TaglessSet[A])(f: A => TaglessSet[B]): TaglessSet[B] = new TaglessSet[B] {
        def apply[F[_]: MonadSet]: F[B] = MonadSet[F].bind(fa[F])(a => f(a)[F])
      }
    }

  def add(int: Int): TaglessSet[Unit] = new TaglessSet[Unit] {
    def apply[F[_]: MonadSet]: F[Unit] = MonadSet[F].add(int)
  }

  def exists(int: Int): TaglessSet[Boolean] = new TaglessSet[Boolean] {
    def apply[F[_]: MonadSet]: F[Boolean] = MonadSet[F].exists(int)
  }
}

// Usage - STACK SAFE!
package taglessStackSafety

import scalaz._
import scalaz.Free.Trampoline
import Scalaz._

object ScalazApp extends App {
  def largeExpr[F[_]: Apply](add: Int => F[Unit], exists: Int => F[Boolean]): F[Boolean] =
    NonEmptyList(0, List.range(1, 10000 - 1): _*).map(i => add(i) *> exists(i)).foldLeft1((x, y) => (x |@| y)(_ && _))

  val set = largeExpr(TaglessSet.add, TaglessSet.exists)
  val state = set[Trampoline]
  val result = state.run
  println(result)
}

Here's the Cats equivalent I think (only things changed are Cats Monad definitions and using Eval instead of Trampoline).

package taglessStackSafety

import cats.{Eval, Monad, RecursiveTailRecM}
import cats.data.{State, StateT, Xor}

trait MonadSet[F[_]] extends Monad[F] with RecursiveTailRecM[F] {
  def add(int: Int): F[Unit]
  def exists(int: Int): F[Boolean]
}

object MonadSet {
  def apply[F[_]](implicit F: MonadSet[F]): MonadSet[F] = F

  implicit val evalInterpreter: MonadSet[Eval] = new MonadSet[Eval] {
    def add(int: Int): Eval[Unit] = Eval.now(())
    def exists(int: Int): Eval[Boolean] = Eval.now(true)
    def pure[A](x: A): Eval[A] = Eval.now(x)
    def flatMap[A, B](fa: Eval[A])(f: A => Eval[B]): Eval[B] = fa.flatMap(f)
    def tailRecM[A, B](a: A)(f: A => Eval[Xor[A, B]]): Eval[B] = defaultTailRecM(a)(f)
  }
}

trait TaglessSet[A] {
  def apply[F[_]: MonadSet]: F[A]
}

object TaglessSet {
  implicit val instance: Monad[TaglessSet] with RecursiveTailRecM[TaglessSet] =
    new Monad[TaglessSet] with RecursiveTailRecM[TaglessSet] {
      def pure[A](x: A): TaglessSet[A] = new TaglessSet[A] {
        def apply[F[_]: MonadSet]: F[A] = MonadSet[F].pure(x)
      }

      def flatMap[A, B](fa: TaglessSet[A])(f: A => TaglessSet[B]): TaglessSet[B] = new TaglessSet[B] {
        def apply[F[_]: MonadSet]: F[B] = MonadSet[F].flatMap(fa[F])(a => f(a)[F])
      }

      def tailRecM[A, B](a: A)(f: A => TaglessSet[Xor[A, B]]): TaglessSet[B] = new TaglessSet[B] {
        def apply[F[_]: MonadSet]: F[B] = MonadSet[F].tailRecM(a)(a => f(a)[F])
      }
    }

  def add(int: Int): TaglessSet[Unit] = new TaglessSet[Unit] {
    def apply[F[_]: MonadSet]: F[Unit] = MonadSet[F].add(int)
  }

  def exists(int: Int): TaglessSet[Boolean] = new TaglessSet[Boolean] {
    def apply[F[_]: MonadSet]: F[Boolean] = MonadSet[F].exists(int)
  }
}

// Usage - BLOWS STACK!
import cats.{Apply, Eval, Monad, RecursiveTailRecM}
import cats.data.{NonEmptyList, State, Xor}
import cats.implicits._

object CatsApp extends App {
  def largeExpr[F[_]: Apply](add: Int => F[Unit], exists: Int => F[Boolean]): F[Boolean] =
    NonEmptyList(0, List.range(1, 10000 - 1)).map(i => add(i) *> exists(i)).reduceLeft(_.map2(_)(_ && _))

  val set = largeExpr(TaglessSet.add, TaglessSet.exists)
  val state = set[Eval]
  val result = state.value
  println(result)
}

This blows stack. The point of interest in the Cats version appears to be:

def largeExpr[F[_]: Apply](add: Int => F[Unit], exists: Int => F[Boolean]): F[Boolean] =
  NonEmptyList(0, List.range(1, 10000 - 1)).
    map(i => add(i) *> exists(i)).
    reduceLeft(_.map2(_)(_ && _))

Recalling @ceedubs 's map2Eval addition, I turned it into:

NonEmptyList(0, List.range(1, 10000 - 1)).
  map(i => add(i) *> exists(i)).
  reduceRight((x, y) => x.map2Eval(y)(_ && _)).
  value

which works! So I thought OK maybe it's just map2, so let's change it into flatMap:

NonEmptyList(0, List.range(1, 10000 - 1)).
  map(i => add(i) *> exists(i)).
  reduceLeft { (x, y) =>
    for {
      a <- x
      b <- y
    } yield a && b
  }

Back to blowing stack. Related tweet stream: https://twitter.com/adelbertchang/status/764499222020263936

EDIT OK I tried the for-comprehension equivalent in Scalaz and that also blows stack as well. I think the earlier Scalaz example works because ap in Scalaz in by-name: https://github.com/scalaz/scalaz/blob/series/7.3.x/core/src/main/scala/scalaz/Apply.scala#L21 and in Cats it's by-value, but we work around that with map2Eval?

EDIT2 OK what in the world, in Scalaz foldLeft1 with for-comp blows stack, foldRight does not. Probably because foldRight is lazy in Scalaz and in Cats we use Eval: https://github.com/scalaz/scalaz/blob/series/7.3.x/core/src/main/scala/scalaz/Foldable1.scala#L38

EDIT3 OK so:

Cats

• reduceLeft + map2 = blows stack
• reduceLeft + for-comp = blows stack
• reduceRight + map2Eval = good
• reduceRight + for-comp = good

Scalaz

• foldLeft1 + |@| = good
• foldLeft1 + for-comp = blows stack
• foldRight1 + |@| = good
• foldRight1 + for-comp = good

[ceedubs]

@adelbertc Is this resolved? I noticed that you closed the issue but it seems like we might potentially still have some surprises here (such as your reduceLeft + map2 example).

[adelbertc]

@ceedubs I closed it because I thought it was one of those "that's just the way it is" situations. But if you think this is a bug then let's go ahead and open up the books again