适用于一元组合者和Scalaz中的免费monad

Question

几个星期前,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

但它仍然打击堆栈,所以我只是将其作为评论发布.

Dave Stevens刚刚指出用应用程序*>而不是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中做这样有趣的事情所付出的代价,但至少没有堆栈溢出.)

这里发生了什么？我不认为这种差异可能有原因,但实际上我不知道实施中会发生什么,现在没有时间去挖掘.但我很好奇,如果有人知道的话会很酷.

Answer 1

Mandubian是正确的,StateT的flatMap不允许你绕过堆栈累积,因为在调用包装的monad的绑定之前立即创建了新的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)
}

Answer 2

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

应用程序运算符*>仅针对其副作用计算其左参数,并始终忽略结果.这与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肯定会执行此优化),但是现在这似乎是一个错过的优化机会.