Changes in Future traverse behavior between 2.6 and 2.7

[jtjeferreira]

Two different reports in discord about this:

• https://discord.com/channels/632277896739946517/632278570512678923/962027043376201739

Hi! I think I found a regression between cats 2.6 and 2.7 in some code similar to this:

def future(i: Int): Future[NonEmptyList[Either[String, Int]]] = Future.successful(NonEmptyList.one(Right(i)))
val x: Future[NonEmptyList[Either[String, Int]]] = NonEmptyList.one(1).:+(2).nonEmptyFlatTraverse{ x =>
  future(x)
}


In 2.6 the futures "run" in parallel. In 2.7 they run sequentially... I guess one solution could be to use IO and some kind "parallel traverse", but that is not practical for a big code base...

• https://discord.com/channels/632277896739946517/632278570512678923/926124987394457620

I'm seeing some change in behaviour in the Future instances between cats 2.6.0 and 2.7.0
This following code:

import java.util.concurrent.Executors
import scala.collection.mutable.ListBuffer
import scala.concurrent._
import scala.concurrent.duration._
import cats.instances.list._
import cats.instances.future._
import cats.syntax.traverse._

implicit val ec = ExecutionContext.fromExecutor(Executors.newFixedThreadPool(2))

var results = new ListBuffer[Int]()
def sideEffect(i: Int): Future[Int] = Future {
  Thread.sleep(i * 100)
  results = results :+ i
  i
}

val x = List(5, 4, 3, 2, 1)
val y = Await.result(x.traverse(sideEffect), 10.seconds)

println(x)
println(results)



It's a bit clunky - but what it should do is insert elements into results in a different order than x
Because the futures are traversed applicatively. 4 is processed before 5, as the delay is lower
This "works" in 2.6.0 (ie x != results) but does not work in 2.7.0 (x == results)

I am creating this issue to have better discoverability of this issue and discuss workarounds, because reverting to the old behavior seems not to not be a possibility...

[johnynek]

I think you may have seen a discussion on discord but there is no contract in traverse of what order the functions are applied in.

So, from a functional programming perspective, the problem is having an effectful A => Future[B]. Instead we recommend cats-effect and using A => IO[B]

As noted on discord, a workaround is change traverse(fn) to map(fn).sequence. Normally those would be the same and traverse would be preferred but in your case running the map forces your effects to start.

Side note: I have been a proponent of including this instance because it is lawful when used with lawful functions and values. Others argue that it is too dangerous since it encourages you to write code like this which leads to bugs. I think now that alleycats has been merged with this repo and it easier to edit all the code in one PR it would probably be better to move this instance to alleycats but I am concerned that now the breakage would cause problems for users and one of the reasons people trust cats to be a dependency is that we have been very careful to avoid breakages.

[BalmungSan]

Just for the record, if you have this problem another way to fix it is using Future.traverse instead of .traverse
Although, that may be even worse than map + sequence since the replacement is no longer mechanical; e.g. it wouldn't work if you have a long dot-notation chain where traverse was in the middle.

[armanbilge]

Unfortunately this is a "wontfix", since Cats does not make any guarantees about this behavior. Improving the documentation on this is tracked in:

• Recommend using cats-effect as a replacement for _every_ use case of Future #4190

Meanwhile, hopefully the workarounds above are helpful to those in a pinch.