0

I was trying to do an exercise for a Cats Effect course in which I was required, among other things, to read a document line by line and wait a certain amount of time between lines.

The teacher's solution was the following:

def readLines(sc: Scanner): IO[Unit] =
  if sc.hasNextLine then IO(sc.nextLine).debug *> IO.sleep(1.second) *> readLines(sc)
  else IO.unit

However, I attempted to create a tail-recursive function from the same function above, and it looked something like this:

def readLines(sc: Scanner): IO[Unit] =

  @tailrec
  def tailReader(accum: IO[Unit]): IO[Unit] =

    if sc.hasNextLine then tailReader(accum *> IO(sc.nextLine).debug *> IO.sleep(1.second))
    else accum

  tailReader(IO.unit)

end readLines

The problem is, the first implementation does read line by line and finishes. On the other hand, my implementation never finishes and never reads even the first line of the document, and is then followed by an OutOfMemoryError.

My question is, is there any way to implement the first function in a way that is tail-recursive and purely functional?

I know there is a way to make the first implementation stack-safe by using the >> operator instead of the *> one. However that's not what I'm looking for, instead I'm looking to be able to use the @tailrec annotation.

The way I was able to partially fix the error was to create a value at the beginning of the function that saves the current line from the scanner, like this:

def readLines(sc: Scanner): IO[Unit] =

  @tailrec
  def tailReader(accum: IO[Unit]): IO[Unit] =

    val currentLine = sc.nextLine

    if sc.hasNextLine then tailReader(accum *> IO(currentLine).debug *> IO.sleep(1.second))
    else accum >> IO(currentLine).debug.void

  tailReader(IO.unit)

end readLines

Although this solved the problem, I am pretty sure that the solution is not purely functional.

I would be very grateful if you could give me a hand with this problem, I am just starting to understand the world of effects, and your help would come in handy!

For everything else, have a really nice day.

Improve this question
5
  • 1
    Two things, first your professor solution is wrong, sc.hasNextLine must be suspended in IO, second, why are you focused on using tailrec? There is no point in that. Commented Jun 4, 2022 at 12:44
  • I just wanted to do it as a mental gymastics exercise, no actual reason to do it other than practice the design pattern. Also, thanks so much por the aclaration about sc.hasNextLine! It clearearly mutates some internal state. Thanks again! Commented Jun 4, 2022 at 19:58
  • It does not mutate internal state, rather it access / read some mutable state. Also, which design pattern you want to practice? Because, again, you don't write tail rec algorithms using IO Commented Jun 4, 2022 at 20:10
  • Thanks for the clarification! Also, I usually try to optimise algorithms using dynamic programming. And I have understood that optimising a function by making it tail-recursive overlaps with the previously mentioned technique. So that's why I was trying to make the function tail-recursive, just as an exercise. On the other hand, is there any reason not to do tail-recursive algorithms with IOs other than they are already implemented in a stack-safe way? Commented Jun 4, 2022 at 20:21
  • 1
    There is only one reason to write a tail-recursive algorithm, to avoid blowing up the stack. If the function is stack safe without being tail-recursive there is no need to complicar the code. Also, as you saw, trying to make it tail-recursive is very difficult and complicates the code. So, again, there is no reason for doing that. The number one reason to use IO is to increase the maintainability of the code, thus deliberately going against that makes no sense. Commented Jun 4, 2022 at 20:49

1 Answer 1

Reset to default
2

Some clarifications:

  1. Regarding >> and *>:
  def *>[B](that: IO[B]): IO[B] =
    productR(that)

  def productR[B](that: IO[B]): IO[B] =
    flatMap(_ => that)

  def >>[B](that: => IO[B]): IO[B] =
    flatMap(_ => that)
  1. You can do stack safe recursion with flatMap because of how Monad is designed in Cats.

I'll swap >> and *> with flatMap in the following examples and drop @tailrec as stack safety is already guaranteed.

Now what's wrong here

def readLines(sc: Scanner): IO[Unit] = {

  def tailReader(accum: IO[Unit]): IO[Unit] = {
    if (sc.hasNextLine)
      tailReader { 
        accum
          .flatMap(_ => IO(sc.nextLine()))
          .flatMap(_ => IO.sleep(1.second))
      }
    else
      tailReader(accum)
  }

  tailReader(IO.unit)
}

We're checking sc.hasNextLine continually while not evaluating sc.nextLine. IO(sc.nextLine) is only a description at this point, nothing is evaluated.

Make the recursive call part of the flatMap chain to solve this:

  def tailReader(accum: IO[Unit]): IO[Unit] = {
    if (sc.hasNextLine)
      IO(sc.nextLine())
        .flatMap(_ => IO.sleep(1.second))
        .flatMap(_ => tailReader(accum)) //make the call here
    else
      tailReader(accum)
  }

then there's another small issue with the recursive method.
tailReader(..) returns an IO only after it checks for next line once.

Use IO.suspend to completely separate definition from evaluation.

   def tailReader(accum: IO[Unit]): IO[Unit] = IO.suspend {
    if (sc.hasNextLine)
      IO(sc.nextLine())
        .flatMap(_ => IO.sleep(1.second))
        .flatMap(_ => accum)
    else
      tailReader(accum)
  }

Now tailReader(IO.unit) returns the IO without calling hasNextLine even once.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks for your answer and the other recomendations! Now I understand a bit more why the function did not work in the first place. Have a nice day!

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.