Cats IO - Make tail recursive call inside flatmap

Question

I'm trying to make my function which returns an IO tail recursive but it does not compile because I'm using it inside flatMap. I know there are things built for this purpose such as tailRec but I'm looking for some guidance on how to use them. Here's the sample code.

    import cats.effect.IO
    import scala.annotation.tailrec

    def process(since: Option[String]): IO[Seq[String]] = {

      @tailrec
      def go(startIndex: Int): IO[(Int, Seq[String])] = {

        val program = since match {
          case Some(s) =>
            for {
              r <- fetchResponse(s, startIndex)
              size = r.size
              ss = r.data
              _ <- writeResponse(ss)

            } yield (size,  r)
          case None => IO((0, Seq.empty[String]))
        }

        program.flatMap { case (size, _) =>
          if (startIndex <= size) go( startIndex + size)
          else IO((0, Seq.empty))
        }
      }

      go(0).map(o => o._2)
    }

    case class Response(size: Int, data: Seq[String])

    def fetchResponse(s: String, i: Int): IO[Response] = ???

    def writeResponse(r: Seq[String]): IO[Int] = ???

Which part of the whole construction is supposed to be tail-recursive? What did you intend to do with a @tailrec annotation on a val? — Andrey Tyukin

Joe K Joe K · Accepted Answer · 2018-02-08T19:54:21

The short answer is: don't worry about it.

The way that cats constructs and executes IO instances, especially with flatMap is pretty stack-safe, as described here.

When you do x.flatMap(f), f is not executed immediately within the same stack. It is executed later by cats in a way that essentially implements tail recursion internally. As a simplified example, you can try running:

def calculate(start: Int, end: Int): IO[Int] = {
  IO(start).flatMap { x =>
    if (x == end) IO(x) else calculate(start + 1, end)
  }
}

calculate(0, 10000000).flatMap(x => IO(println(x))).unsafeRunSync()

Which is essentially the same as what you are doing, and it prints out 10000000 just fine.

Cats IO - Make tail recursive call inside flatmap

1 Answers