11

几周前Dragisa Krsmanovic在这里问了一个问题，关于如何在 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)

我认为只需将蹦床举起来就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刚刚指出，使用 applicative*>而不是 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

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

这里发生了什么？我认为这种差异可能没有原则上的原因，但我真的不知道实施中会发生什么，并且目前没有时间进行挖掘。但我很好奇，如果其他人知道会很酷。

4

3 回答 3

6

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

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

现在我们已经构建了一个 Free 数据结构，我们可以轻松地通过以下方式线程化一个状态：

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)
}
于 2014-07-20T02:09:48.323 回答
5

这种差异有一种原则性的直觉。

applicative 运算符*>仅针对其副作用评估其左参数，并且始终忽略结果。这类似于（在某些情况下等效）Haskell 的>>单子函数。以下是 的来源*>：

/** Combine `self` and `fb` according to `Apply[F]` with a function that discards the `A`s */
final def *>[B](fb: F[B]): F[B] = F.apply2(self,fb)((_,b) => b)

和Apply#apply2：

def apply2[A, B, C](fa: => F[A], fb: => F[B])(f: (A, B) => C): F[C] =
  ap(fb)(map(fa)(f.curried))

通常，flatMap取决于左参数的结果（它必须，因为它是右参数中函数的输入）。即使在这种特定情况下，您忽略了左侧结果，flatMap也不知道这一点。

鉴于您的结果，对于不需要左参数结果的情况，似乎对实现进行了*>优化。但是flatMap无法执行此优化，因此每次调用都会通过保留未使用的左侧结果来增加堆栈。

有可能这可以在编译器 (scalac) 或 JIT (HotSpot) 级别进行优化（Haskell 的 GHC 肯定会执行此优化），但现在这似乎是一个错失的优化机会。

于 2014-06-16T19:10:58.883 回答
3

只是为了加入讨论......

在StateT中，您有：

  def flatMap[S3, B](f: A => IndexedStateT[F, S2, S3, B])(implicit F: Bind[F]): IndexedStateT[F, S1, S3, B] = 
  IndexedStateT(s => F.bind(apply(s)) {
    case (s1, a) => f(a)(s1)
  })

将apply(s)当前状态引用固定在下一个状态。

bind定义急切地解释其捕获引用的参数，因为它需要它：

  def bind[A, B](fa: F[A])(f: A => F[B]): F[B]

不同的是ap，可能不需要解释其参数之一：

  def ap[A, B](fa: => F[A])(f: => F[A => B]): F[B]

使用此代码，（也）无能为力Trampoline...StateT flatMapmap

于 2014-06-17T09:49:41.623 回答