Applicative 与 monadic 组合器和 Scalaz 中的自由 monad [英] Applicative vs. monadic combinators and the free monad in Scalaz

问题描述

几周前Dragisa Krsmanovic问这里有一个问题，关于如何在 Scalaz 7 中使用 free monad 来避免这种情况下的堆栈溢出(我稍微修改了他的代码):

A couple of weeks ago Dragisa Krsmanovic asked a question here about how to use the free monad in Scalaz 7 to avoid stack overflows in this situation (I've adapted his code a bit):

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 就应该工作:

I thought that just lifting a trampoline into StateT should work:

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

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

But it still blows the stack, so I just posted it as a comment.

Dave Stevens 只是 指出使用应用*>而不是monadicflatMap的排序实际上工作得很好:

Dave Stevens just pointed out that sequencing with the applicative *> instead of the monadic flatMap actually works just fine:

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

s(Nil).run

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

(Well, it's super slow of course, because that's the price you pay for doing anything interesting like this in Scala, but at least there's no stack overflow.)

这是怎么回事?我不认为这种差异可能存在原则性原因，但我真的不知道实施过程中会发生什么，目前没有时间深入研究.但我很好奇，如果别人知道就好了.

What's going on here? I don't think there could be a principled reason for this difference, but really I have no idea what could be going on in the implementation and don't have time to dig around at the moment. But I'm curious and it would be cool if someone else knows.

推荐答案

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

Mandubian is correct, the flatMap of StateT doesn't allow you to bypass stack accumulation because of the creation of the new StateT immediately before calling the wrapped monad's bind (which would be a Free[Function0] in your case).

所以 Trampoline 无济于事，但是 State 仿函数上的 Free Monad 是确保堆栈安全的一种方法.

So Trampoline can't help, but the Free Monad over the functor for State is one way to ensure stack safety.

我们想从 State[List[Int],Unit] 到 Free[a[State[List[Int],a],Unit] 并且我们的 flatMap 调用将是 Free 的 flatMap(它什么都不做除了创建自由数据结构).

We want to go from State[List[Int],Unit] to Free[a[State[List[Int],a],Unit] and our flatMap call will be to Free's flatMap (that doesn't do anything other than create the Free data structure).

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)))
    }

现在我们构建了一个免费的数据结构，我们可以轻松地将状态线程化:

Now we have a Free data structure built that we can easily thread a state through as such:

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

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

Calling liftF is fairly ugly so I have a PR in to make it easier for State and Kleisli monads so hopefully in the future there won't need to be type lambdas.

公关接受，所以现在我们有

PR accepted so now we have

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

这篇关于Applicative 与 monadic 组合器和 Scalaz 中的自由 monad的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！