在使用scalaz的自由单子（free 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)

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

我想避免这种情况引起的堆栈溢出... 我认为这已经是 trampolined 的了，但我想我需要手动再次处理？在自由单子的思路中是否有一种简洁的方法？

更新：

进一步思考后，我认为问题不在于 sleep Free Monad，而是我们在评估时绑定到 Id.Id 单子...所以我尝试了类似以下的内容：

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能够阻塞直到满足某些条件（或者在这种情况下，无限循环直到我杀死它，但不会出现堆栈溢出）。

- A Question Asker

Answer 1

Id单子没有使用trampoline技术。你会陷入Id单子的bind方法和自由单子的foldMap方法之间的无限相互递归中。建议使用Trampoline或者Task代替Id单子。

- Apocalisp

Answer 2

自从@Apocalisp的回答之后，BindRec类型类和foldMapRec方法已经被添加，可用于直接对Id（或任何其他“尾递归”单子）进行堆栈安全评估。有关详情，请阅读免费的堆栈安全性。

- Tomas Mikula