Where Is The Implementation for Traverse[IO]

val foo: IO[List[Int]] = List(IO.pure(100)).sequence

Where do I find the implementation for the sequence method? I presume there is a Traverse typeclass implementation for cats.effect.IO and where can I find this implementation? If I am wrong, how does foo above work? Thanks

Solution

There no Traverse for IO, well I belive there isn't, and if there is one is not relevant for this example.
There is however a Traverse for List and an Applicative to IO, and since IO also forms a Monad then that one delegate to flatMap.

In general, we know that:

def sequence[A, F[_], G[_]](fga: F[G[A]])(using Traverse[F], Applicative[G]): G[F[A]] =
  traverse(fga)(identity)

trait Traverse[F[_]]:
  def traverse[A, B, G[_]](fa: F[A])(f: A => G[B])(using Applicative[G]): G[F[B]]

And for List the implementation of traverse is as follows:

given Traverse[List] with
  override def traverse[A, B, G[_]](fa: List[A])(f: A => G[B])(Applicative[G]): G[List[B]] =
    fa.foldLeft(Appliative[G].pure(List.empty[B])) {
      case (accG: G[List[B]], a: A) =>
        val gb: G[B] = f(a)
        Appliative[G].map2(accG, gb) {
           case (acc: List[B], b: B) =>
             b :: acc
        }
    }.map(_.reverse) // Or you could use foldRight or another more optimal strategy but that is besides the point.

And we also know that when there is a Monad[G] then:

trait Monad[G[_]] extends Applicative[G]:
  override def map2[A, B, C](ga: G[A], gb: G[B])(f: (A, B) => C): G[C] =
    for
      a <- ga
      b <- gb
      c = f(a, b)
    yield c

So, in other words, this becomes just a traversal of the List using flatMaps.

Relevant sources:

The real implementations are, of course, more optimized and a little bit more complex than the ones I used. But conceptually they are equivalent.