Specify short-circuiting behavior and add tests or laws

[travisbrown]

There's currently some inconsistency between our collection instances with respect to where short-circuiting happens. To take a couple of examples:

scala> import cats.implicits._
import cats.implicits._

scala> import cats.Eval, cats.implicits._
import cats.Eval
import cats.implicits._

scala> List.empty[String].map2Eval(Eval.later[List[Int]](sys.error("explode")))((x, _) => x)
res0: cats.Eval[List[String]] = Now(List())

scala> res0.value
res1: List[String] = List()

scala> Vector.empty[String].map2Eval(Eval.later[Vector[Int]](sys.error("explode")))((x, _) => x)
res2: cats.Eval[scala.collection.immutable.Vector[String]] = cats.Eval$$anon$4@2030bbf1

scala> res2.value
java.lang.RuntimeException: explode
  at scala.sys.package$.error(package.scala:30)
  at .$anonfun$res2$1(<console>:19)
  at cats.Later.value$lzycompute(Eval.scala:148)
  at cats.Later.value(Eval.scala:147)
  at cats.Eval$.loop$1(Eval.scala:345)
  at cats.Eval$.cats$Eval$$evaluate(Eval.scala:366)
  at cats.Eval$FlatMap.value(Eval.scala:305)
  ... 36 elided

…or:

scala> import cats.implicits._
import cats.implicits._

scala> val f: Int => Either[String, Option[Int]] = i => {
     |   print(s"$i ")
     |   if (i > 0) Right(Some(i)) else Left("not positive")
     | }
f: Int => Either[String,Option[Int]] = $$Lambda$7369/108699853@1ccdbb90

scala> List(2, 1, 0, -1).traverse(f)
2 1 0 res0: Either[String,List[Option[Int]]] = Left(not positive)

scala> List(2, 1, 0, -1).traverseFilter(f)
2 1 0 res1: Either[String,List[Int]] = Left(not positive)

scala> Vector(2, 1, 0, -1).traverse(f)
2 1 0 res2: Either[String,scala.collection.immutable.Vector[Option[Int]]] = Left(not positive)

scala> Vector(2, 1, 0, -1).traverseFilter(f)
-1 0 1 2 res3: Either[String,scala.collection.immutable.Vector[Int]] = Left(not positive)

Some specific cases of this are tracked in #3327 and fixed in #3328, but even after those changes we don't have tests to make sure we don't introduce more inconsistency, and we don't do a very good job of communicating to users what they can expect.

[gagandeepkalra]

I'll try attempt this.

[tnielens]

Not related to the collection short-circuiting behavior, but would it make sense to implement map2Eval for Future?
It is currently not overriding the non-short-circuiting default behavior.

  import scala.concurrent.{Await, Future}
  import scala.concurrent.ExecutionContext.Implicits.global
  import cats.implicits._
  import concurrent.duration._

  val f: Int => Future[Int] = i => {
    print(s"$i ")
    if (i >= 0) Future.successful(i) else Future.failed(new RuntimeException("not positive"))
  }

@  Await.ready(List(-1, 1, 2, 3).traverse(f), 5.second)
-1 1 2 3 res0: Future[List[Int]] = Future(Failure(java.lang.RuntimeException: not positive))

[gagandeepkalra]

@montrivo

Not related to the collection short-circuiting behavior, but would it make sense to implement map2Eval for Future?
It is currently not overriding the non-short-circuiting default behavior.

  import scala.concurrent.{Await, Future}
  import scala.concurrent.ExecutionContext.Implicits.global
  import cats.implicits._
  import concurrent.duration._

  val f: Int => Future[Int] = i => {
    print(s"$i ")
    if (i >= 0) Future.successful(i) else Future.failed(new RuntimeException("not positive"))
  }

@  Await.ready(List(-1, 1, 2, 3).traverse(f), 5.second)
-1 1 2 3 res0: Future[List[Int]] = Future(Failure(java.lang.RuntimeException: not positive))

I tried a map2Eval override for future, this seems to achieve short-circuiting behaviour.

  override def map2Eval[A, B, Z](fa: Future[A], fb: Eval[Future[B]])(f: (A, B) => Z): Eval[Future[Z]] =
    Eval.later(fa.flatMap(a => fb.value.map(b => f(a, b))))

But then again it costs parallelisation, this implementation defers running f on each successive A until the previous result is available.

The original Future.traverse from standard library says

Asynchronously and non-blockingly transforms a TraversableOnce[A] into a Future[TraversableOnce[B]]

• using the provided function A => Future[B].
• This is useful for performing a parallel map. For example, to apply a function to all items of a list
• in parallel

We should not defer from something that is taken as granted or assumed to hold, but then again we have parTraverse for exactly that reason, I can't seem to reach a conclusion.