问题 适用于一元组合者和Scalaz中的免费monad
几个星期前 Dragisa Krsmanovic 问 这里有个问题 关于如何在Scalaz 7中使用免费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
但它仍然打击堆栈，所以我只是将其作为评论发布。
戴夫史蒂文斯 只是 指出 用应用程序排序 *> 而不是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中做这样有趣的事情所付出的代价，但至少没有堆栈溢出。）
这里发生了什么？我不认为这种差异可能有原因，但实际上我不知道实施中会发生什么，现在没有时间去挖掘。但我很好奇，如果有人知道的话会很酷。
3817
2018-06-10 22:18
起源
答案:
Mandubian是正确的，StateT的flatMap不允许你绕过堆栈累积，因为在调用包装monad的bind之前立即创建了新的StateT（在你的情况下将是Free [Function0]）。
所以Trampoline无法帮助，但Free Monad对状态的仿函数是确保堆栈安全的一种方法。
我们想从State [List [Int]，Unit]到Free [a [State [List [Int]，a]，Unit]，我们的flatMap调用将是Free的flatMap（除了create之外什么都不做）免费数据结构）。
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是相当丑陋的所以我有一个公关，使State和Kleisli monad更容易，所以希望将来不需要输入lambdas。
编辑：公关接受所以现在我们有
val s = (1 to 100000).foldLeft(state[List[Int], Unit](()).liftF) {
case (st, i) => st.flatMap(_ => setS(i).liftF)
}
6
2017-07-20 02:09
这种差异有一种原则性的直觉。
适用的运营商 *> 仅考虑其左侧参数的副作用，并且 总是 忽略了结果。这与Haskell类似（在某些情况下是等效的） >> monad的功能。这是源头 *>：
/** 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肯定会执行此优化），但是现在这似乎是一个错过的优化机会。
5
2018-06-16 19:10
答案:
Mandubian是正确的，StateT的flatMap不允许你绕过堆栈累积，因为在调用包装monad的bind之前立即创建了新的StateT（在你的情况下将是Free [Function0]）。
所以Trampoline无法帮助，但Free Monad对状态的仿函数是确保堆栈安全的一种方法。
我们想从State [List [Int]，Unit]到Free [a [State [List [Int]，a]，Unit]，我们的flatMap调用将是Free的flatMap（除了create之外什么都不做）免费数据结构）。
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是相当丑陋的所以我有一个公关，使State和Kleisli monad更容易，所以希望将来不需要输入lambdas。
编辑：公关接受所以现在我们有
val s = (1 to 100000).foldLeft(state[List[Int], Unit](()).liftF) {
case (st, i) => st.flatMap(_ => setS(i).liftF)
}
6
2017-07-20 02:09
这种差异有一种原则性的直觉。
适用的运营商 *> 仅考虑其左侧参数的副作用，并且 总是 忽略了结果。这与Haskell类似（在某些情况下是等效的） >> monad的功能。这是源头 *>：
/** 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肯定会执行此优化），但是现在这似乎是一个错过的优化机会。
5
2018-06-16 19:10
只是为了加入讨论......
在 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 flatMap （并且 map）...
3
2018-06-17 09:49