蹦床 scalaz' Monad.whileM_，防止烟囱溢出

Question

我使用scalaz' Monad.whileM_以函数方式实现while循环，如下所示:

object Main {
  import scalaz._
  import Scalaz._
  import scala.language.higherKinds
  case class IState(s: Int)
  type IStateT[A] = StateT[Id, IState, A]
  type MTransT[S[_], A] = EitherT[S, String, A]
  type MTrans[A] = MTransT[IStateT, A]
  def eval(k: Int): MTrans[Int] = {
    for {
      state <- get[IState].liftM[MTransT]
      _ <- put(state.copy(s = (state.s + 1) % k)).liftM[MTransT]
    } yield (k + 1)
  }
  def evalCond(): MTrans[Boolean] = {
    for {
      state <- get[IState].liftM[MTransT]
    } yield (state.s != 0)
  }

  def run() = {
    val k = 10
    eval(k).whileM_(evalCond()).run(IState(1))
  }
}

虽然这适用于小k，但它会导致大k(例如1000000)的StackOverflow错误。有没有办法蹦床whileM_或有一个更好的方法是堆栈安全?

Answer 1

使用scalaz.Free.Trampoline代替scalaz.Id.Id。

type IStateT[A] = StateT[Trampoline, IState, A]

这里使用的状态操作返回State[S, A]，它只是StateT[Id, S, A]的别名。您需要使用StateT上定义的lift[M[_]]函数将StateT[Id, S, A]提升到StateT[Trampoline, S, A]。

def eval(k: Int): MTrans[Int] = {
  for {
    state <- get[IState].lift[Trampoline].liftM[MTransT]
    _ <- put(state.copy(s = (state.s + 1) % k)).lift[Trampoline].liftM[MTransT]
  } yield (k + 1)
}
def evalCond(): MTrans[Boolean] = {
  for {
    state <- get[IState].lift[Trampoline].liftM[MTransT]
  } yield (state.s != 0)
}

最后，调用.run(IState(1))现在会得到Trampoline[(IState, String / Unit)]。您必须另外添加run。

eval(k).whileM_(evalCond()).run(IState(1)).run