应用性与单子组合器以及 Scalaz 中的自由单子

几周前德拉吉萨·克斯曼诺维奇 asked 这里有一个问题关于如何在 Scala 7 中使用 free monad 来避免这种情况下的堆栈溢出（我对他的代码进行了一些调整）：

import scalaz._, Scalaz._

def setS(i: Int): State[List[Int], Unit] = modify(i :: _)

val s = (1 to 100000).foldLeft(state[List[Int], Unit](())) {
  case (st, i) => st.flatMap(_ => setS(i))
}

s(Nil)

我想只需将蹦床举升到StateT应该管用：

import Free.Trampoline

val s = (1 to 100000).foldLeft(state[List[Int], Unit](()).lift[Trampoline]) {
  case (st, i) => st.flatMap(_ => setS(i).lift[Trampoline])
}

s(Nil).run

但它仍然让堆栈崩溃，所以我只是将其作为评论发布。

戴夫·史蒂文斯 just 指出与应用程序的排序*>而不是单子flatMap实际上工作得很好：

val s = (1 to 100000).foldLeft(state[List[Int], Unit](()).lift[Trampoline]) {
  case (st, i) => st *> setS(i).lift[Trampoline]
}

s(Nil).run

（嗯，当然它超级慢，因为这是你在 Scala 中做任何有趣的事情所付出的代价，但至少没有堆栈溢出。）

这里发生了什么？我认为这种差异可能没有原则上的原因，但实际上我不知道实施过程中会发生什么，而且目前没有时间进行深入研究。但我很好奇，如果其他人知道那就太好了。

Mandubian 是正确的，StateT 的 flatMap 不允许您绕过堆栈累积，因为在调用包装的 monad 的绑定之前立即创建了新的 StateT （在您的情况下，这将是 Free[Function0] ）。

所以 Trampoline 无法提供帮助，但 State 函子上的 Free Monad 是确保堆栈安全的一种方法。

我们想要从 State[List[Int],Unit] 转到 Free[a[State[List[Int],a],Unit] 并且我们的 flatMap 调用将是 Free 的 flatMap （除了创建自由数据结构）。

val s = (1 to 100000).foldLeft( 
    Free.liftF[({ type l[a] = State[List[Int],a]})#l,Unit](state[List[Int], Unit](()))) {
      case (st, i) => st.flatMap(_ => 
          Free.liftF[({ type l[a] = State[List[Int],a]})#l,Unit](setS(i)))
    }

现在我们已经构建了一个自由数据结构，我们可以轻松地通过它来线程化状态：

s.foldRun(List[Int]())( (a,b) => b(a) )

调用 liftF 相当难看，所以我有一个 PR 来让 State 和 Kleisli monad 更容易，所以希望将来不需要 lambda 类型。

编辑：PR 已接受，所以现在我们有了

val s = (1 to 100000).foldLeft(state[List[Int], Unit](()).liftF) {
      case (st, i) => st.flatMap(_ => setS(i).liftF)
}