scala - Applicative 与 monadic 组合器和 Scalaz 中的自由 monad

几周前 Dragisa Krsmanovic 向 a question here 询问了如何在 Scalaz 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)

我认为 that just lifting a trampoline into 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

但它仍然炸毁了堆栈，所以我只是将其作为评论发布。

Dave Stevens 只是 pointed out 与应用 *> 而不是 monadic flatMap 的排序实际上工作得很好:

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

s(Nil).run

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

这里发生了什么？我不认为这种差异可能存在原则性原因，但我真的不知道实现过程中会发生什么，目前没有时间深入研究。但我很好奇，如果其他人知道会很酷。

最佳答案

Mandubian 是正确的，StateT 的 flatMap 不允许您绕过堆栈累积，因为在调用包装的 monad 的绑定(bind)之前立即创建了新的 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 monads 更容易，所以希望将来不需要类型 lambdas。

编辑:公关接受了，所以现在我们有了

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

关于scala - Applicative 与 monadic 组合器和 Scalaz 中的自由 monad，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/24151771/