Scalaz中的Applicative和单子组合器以及自由单子。

Question

几周前Dragisa Krsmanovic提出了一个问题, 关于如何使用Scalaz 7中的自由单子来避免在这种情况下发生堆栈溢出（我稍微改编了他的代码）:

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 刚刚 指出，使用应用程序 *> 而不是单调的 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中进行任何有趣操作的代价，但至少没有堆栈溢出。）

这里发生了什么？我不认为有什么原则上的差异，但实际上我不知道实现中可能正在发生什么，并且暂时没有时间挖掘。 但我很好奇，如果有人知道会很酷。

- Travis Brown

Answer 1

Mandubian说得对，StateT的flatMap不能绕过堆栈积累，因为在调用包装的单子的bind之前立即创建了新的StateT（在你的情况下将是Free [Function0]）。

所以Trampoline无法帮助解决这个问题，但是使用State的functor上的Free Monad是确保堆栈安全的一种方法。

我们想从State [List [Int]，Unit]转换为Free [a [State [List [Int]，a]，Unit]，并且我们的flatMap调用将是Free的flatMap（除了创建Free数据结构外不做任何其他事情）。

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更容易使用，因此希望未来不再需要有类型λ。

编辑：PR已被接受，现在我们有

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

- Vincent

Answer 2

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

应用操作符 *> 仅对其左侧参数进行副作用评估，并始终忽略结果。这在某些情况下类似于 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 当然可以执行此优化），但目前看来这似乎是一个被忽视的优化机会。

- cdk

---

+1并感谢，但我的理解是，跳板的flatMap重新定义了堆上的绑定方式，这意味着即使我们不丢弃该结果，在这里我们也是安全的？ - Travis Brown

@cdk我认为这不是答案。选择另一个运算符，它依赖于左侧的结果 并且 需要Apply而不是Bind。例如 |@| https://gist.github.com/drstevens/3ea464446ee59463af1e - drstevens

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 的定义会立即解释其参数并捕获引用，因为它需要它：

  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无法帮助StateTflatMap（以及map）...

- mandubian