使用 scalaz 的免费 monad 时如何避免堆栈溢出？

Question

我之前认为实施的部分目标是避免这个问题，所以也许我在做一些明显愚蠢的事情？

这是一些代码：

    // Stack overflow
import scalaz._

sealed trait Command[T]
case class Wait(ms: Long) extends Command[Unit]

case object Evaluator extends (Command ~> Id.Id) {
  override def apply[T](cmd: Command[T]) = cmd match {
    case Wait(t)  => Thread.sleep(t)
  }
}

object Api {
  def sleep(ms: Long): Free.FreeC[Command, Unit] = Free.liftFC(Wait(ms))
}

val sleep: Free.FreeC[Command, Unit] =
  Api.sleep(1).flatMap { _ => sleep }

Free.runFC(sleep)(Evaluator)

注意：我意识到这很愚蠢 :) 实际上，我的命令 class 有很多命令，我有一个执行相同循环的命令...基本上，轮询一些状态，如果为真则中止, 如果为假，请继续等待。

我想避免这导致的堆栈溢出...我以为这已经被蹦床了，但我想我需要手动再做一次？在自由 monad 的思维方式中有没有一种干净的方法来做到这一点？

更新：

进一步思考这个问题，我认为问题不在于 sleep Free Monad，而是我们在评估时绑定的 Id.Id monad taht...所以我尝试了类似的方法：

case object Evaluator2 extends (Command ~> ({ type t[x] = Free[Id.Id, x] })#t) {
  override def apply[T](cmd: Command[T]) = cmd match {
    case Wait(t)  => Thread.sleep(t); Free.liftF[Id.Id, Unit](())
  }
}

Free.runFC[Command, ({ type t[x] = Free[Id.Id, x] })#t, Unit](sleep)(Evaluator2)(Free.freeMonad[Id.Id])

但这样做的问题是它只会评估一步。理想情况下，我希望 runFC 阻塞直到满足某些条件（或者在这种情况下，永远循环直到我杀死它，但没有堆栈溢出）

Answer 1

Id monad 不是 trampolined。您最终会在 Id monad 的 bind 方法和自由 monad 的 foldMap 方法之间无限相互递归。使用 Trampoline 或 Task 而不是 Id.

Answer 2

自从@Apocalisp 的回答以来，增加了 BindRec typeclass and foldMapRec method that can be used for stack-safe evaluation directly to Id (or any other "tail-recursive" monad). For details, read Stack Safety for Free。

使用 scalaz 的免费 monad 时如何避免堆栈溢出？

How to avoid stack overflow when using scalaz's free monad?

scala

scalaz

free-monad