scalaz Trampoline and IO

Question

This question is related to this other question but reduced to a much simpler case:

I assume the following imports:

import scalaz._, Scalaz._
import Free._, effect._

I have the following generators:

val fromOneIO: () => IO[Int] = {
  var i = 0; () => { i += 1; IO(i) }
} 
val fromOne: () => Int = {
  var i = 0; () => { i += 1; i }
}

and the following non-tail recursive definitions:

def rec(i: Int): Int = {
  if (i == 0) {
    fromOne()
  } else {
    rec(i - 1) + fromOne()
  }
}
def rec1(i: Int): Trampoline[Int] = {
  if (i == 0) {
    Return(fromOne())
  } else {
    suspend {
      for {
        a <- rec1(i - 1)
        b <- Return(fromOne()): Trampoline[Int]
      } yield a + b
    }
  }
}
def recio(i: Int): Trampoline[IO[Int]] = {
  if (i == 0) {
    Return(fromOneIO())
  } else {
    suspend {
      for {
        ioa <- recio(i - 1)
        iob <- Return(fromOneIO()): Trampoline[IO[Int]]
      } yield {
        for (a <- ioa; b <- iob) yield a + b
      }
    }
  }
}

The result is:

rec(100) // overflows for arg 10000
rec1(10000).run // works
recio(10000).run.unsafePerformIO() //overflows

How to manage to make IO map/flatMap be trampolined as well? It seems I have other nested stacks created inside the second for comprehension. Do I need to write a TrampolineT that will use unsafePerformIO and rewrap the extracted io value into a suspend?

For this particular example a `Monoid` instance for `IO[A: Monoid]` seems to be working. That is, just change your `yield` statement to `ioa |+| iob`. I don't have anything to recommend for the broader picture though. — George, Apr 23 '13 at 14:36
Actually, the problem seems to be in the `Monad` instance for the `IO`. If you use it's `Applicative` instance, it seems to be working just fine. `yield (ioa |@| iob){_ + _}` — George, Apr 23 '13 at 14:42
You want the `IO` itself to be trampolined, not the function building up a huge chain of nested `IO` actions. Your code is allowing you to build up an `IO` action without overflowing your stack, but the way you're building it will lead to a stack overflow when you run the `IO` action. — Mysterious Dan, Apr 23 '13 at 14:57
@folone, interesting that applicative does not overflow. I tried to track it down, but could not find the implementation of `F.lift2`. I wished scalaz7 still had the cross-referenced source built from Harrah's x-ray. — huynhjl, Apr 24 '13 at 13:21
@MyseriousDan, well I still need to deal with the fact that `recio` is not tail recursive. So I sort of need two levels of trampoline. So my question is really how to achieve that second one for IO. — huynhjl, Apr 24 '13 at 13:48

score 3 · Answer 1 · edited Apr 24 '13 at 14:02

So IO(_) is already trampolined, for what it's worth. In addition to the suggestion from folone, I am able to avoid the overflow by changing the second for like this:

val s = for (a <- ioa; b <- iob) yield a + b
val s1 = s.unsafePerformIO()
IO(s1)

Or like this:

IO(for (a <- ioa; b <- iob) yield a + b).flatMap(identity)

Also IO(_) takes a by name parameter, so IO(expr) and val e = expr; IO(e) does not behave the same. This will overflow!

val s = for (a <- ioa; b <- iob) yield a + b
IO(s.unsafePerformIO())

So although it's not a very satisfying answer it seems using the applicative where possible or wrapping in another IO and flattening would be workarounds to blowing the stack.

scalaz Trampoline and IO

1 Answers1