Scalaz中的应用组合子与单子组合子和自由单子

Question

几周前，Dragisa Krsmanovic问a question here如何在这种情况下使用Scalaz7中的免费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只需使用应用型*>而不是一元型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中做任何有趣的事情所要付出的代价，但至少没有堆栈溢出。)

这里发生了什么事？我不认为这可能是一个原则性的原因，但我真的不知道在实现中会发生什么，目前也没有时间去钻研。但我很好奇，如果别人知道那就太酷了。

Answer 1

Mandubian是正确的，StateT的flatMap不允许您绕过堆栈累积，因为在调用包装的monad的绑定(在您的例子中可能是一个FreeFunction0 )之前会立即创建新的绑定。

所以Trampoline无能为力，但是在State的functor上的Free Monad是确保堆栈安全的一种方法。

我们想要从状态[ListInt，单元]转到自由[a[状态[ListInt，a]，单元]，并且我们的flatMap调用将是对自由的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，以使它更容易为国家和克莱斯利monads，所以希望在未来将不需要类型的lambda。

编辑: PR已接受，因此现在我们有

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

Answer 2

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

应用运算符*>只评估其左参数的副作用，并始终忽略结果。这类似于(在某些情况下等同于)Haskell用于monads的>>函数。这是*>的源代码

/** 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不能执行这种优化，因此每次调用都会通过保留未使用的left结果来增加堆栈。

这可能会在编译器(scalac)或JIT (HotSpot)级别进行优化(Haskell的GHC肯定会执行这种优化)，但就目前而言，这似乎是一个错失的优化机会。

Answer 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 definition急切地解释它的参数来捕获引用，因为它需要：

  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 flatMap (以及map)...