cats-effect:How to transform Map[x,IO[y]] to IO[Map[x,y]]

You'll have to be a little careful with this one. Maps in Scala are unordered, so if you try to use cats's sequence like this…

import cats.instances.map._
import cats.effect.IO
import cats.UnorderedTraverse

object Example1 {
    type StringMap[V] = Map[String, V]
    val m: StringMap[IO[String]] = Map("1" -> IO{println("1"); "1"})
    val n: IO[StringMap[String]] = UnorderedTraverse[StringMap].unorderedSequence[IO, String](m)
}

you'll get the following error:

Error: could not find implicit value for evidence parameter of type cats.CommutativeApplicative[cats.effect.IO]

The issue here is that the IO monad is not actually commutative. Here is the definition of commutativity:

map2(u, v)(f) = map2(v, u)(flip(f)) // Commutativity (Scala)

This definition shows that the result is the same even when the effects happen in a different order.

You can make the above code compile by providing an instance of CommutativeApplicative[IO] but that still doesn't make the IO monad commutative. If you run the following code you can see the side effects are not processed in the same order:

import cats.effect.IO
import cats.CommutativeApplicative

object Example2 {
  implicit object FakeEvidence extends CommutativeApplicative[IO] {
    override def pure[A](x: A): IO[A] = IO(x)
    override def ap[A, B](ff: IO[A => B])(fa: IO[A]): IO[B] =
      implicitly[Applicative[IO]].ap(ff)(fa)
  }

  def main(args: Array[String]): Unit = {
    def flip[A, B, C](f: (A, B) => C) = (b: B, a: A) => f(a, b)
    val fa = IO{println(1); 1}
    val fb = IO{println(true); true}
    val f  = (a: Int, b: Boolean) => s"$a$b"
    println(s"IO is not commutative: ${FakeEvidence.map2(fa, fb)(f).unsafeRunSync()} == ${FakeEvidence.map2(fb, fa)(flip(f)).unsafeRunSync()} (look at the side effects above^^)")
  }
}

Which outputs the following:

1
true
true
1
IO is not commutative: 1true == 1true (look at the side effects above^^)

In order to get around this I would suggest making your map something with an order, like a List, where sequence will not require commutativity. The following example is just one way to do this:

import cats.effect.IO
import cats.implicits._

object Example3 {
  val m: Map[String, IO[String]] = Map("1" -> IO {println("1"); "1"})
  val l: IO[List[(String, String)]] = m.toList.traverse[IO, (String, String)] { case (s, io) => io.map(s2 => (s, s2))}
  val n: IO[Map[String, String]] = l.map { _.toMap }
}

It would be nice to use unorderedTraverse here, but as codenoodle pointed out, it doesn't work because IO is not a commutative applicative. However there is a type that is, and it's called IO.Par. Like the name suggests, its ap combinator won't execute things sequentially but in parallel, so it's commutative – doing a and then b is not the same as doing b and then a, but doing a and b in parallel is the same as doing b and a in parallel.

So you can use unorderedTraverse using a function that doesn't return IO but IO.Par. However the downside to that is that now you need to convert from IO to IO.Par and then back – hardly an improvement.

To solve this problem, I have added the parUnorderedTraverse method in cats 2.0 that will take care of these conversions for you. And because it all happens in parallel it will also be more efficient! There are also parUnorderedSequence, parUnorderedFlatTraverse and parUnorderedFlatSequence.

I should also point out that this works not only for IO but also for everything else with a Parallel instance, such as Either[A, ?] (where A is a CommutativeSemigroup). It should also be possible for List/ZipList, but nobody appears to have bothered to do it yet.