scala - 使用状态 monad 遍历时如何处理嵌套结构

Question

我有一个嵌套结构，我正在使用 scalaz 状态 monad 将其转换为 XML。在我必须处理多层嵌套结构之前，这很有效。这是一个类似于我正在做的事情的简化示例。给定以下 ADT:

sealed trait Nested
case object Leaf extends Nested
case class Foo(inner: Nested) extends Nested
case class Bar(inner: Nested) extends Nested

我使用状态 monad 编写一个转换器对象(假设 Scalaz7 和以下导入 import scalaz.{Node => _, _}; import Scalaz._; import scala.xml._) :

case class Parents(foos: Int, bars: Int)
type ParentsS[X] = State[Parents, X]

def convertFoo(foo: Foo): ParentsS[Seq[Node]] = for {
  parents <- init[Parents]
  _ <- put[Parents](Parents(parents.foos + 1, parents.bars))
  inner <- convert(foo.inner)
  _ <- put[Parents](parents)
} yield <foo count={ parents.foos.toString }/>.copy(child=inner)

def convertBar(bar: Bar): ParentsS[Seq[Node]] = for {
  parents <- init[Parents]
  _ <- put[Parents](Parents(parents.foos, parents.bars + 1))
  inner <- convert(bar.inner)
  _ <- put[Parents](parents)
} yield <bar count={ parents.bars.toString }/>.copy(child=inner)

def convert(nested: Nested): ParentsS[Seq[Node]] = nested match {
  case Leaf => Seq[Node]().point[ParentsS]
  case foo@Foo(_) => convertFoo(foo)
  case bar@Bar(_) => convertBar(bar)
}

def nested(n: Int): Nested =
  if (n == 0) Leaf
  else {
    if (n % 2 == 0) Bar(nested(n - 1))
    else Foo(nested(n - 1))
  }

根据我的堆栈设置，convert(nested(1000)).apply(Parents(0, 0)) 将在转换过程中导致堆栈溢出。 (较高的值将导致 nested 溢出，但这可以忽略，因为我刚刚为此问题创建了 nested。):

    at scalaz.IdInstances$$anon$1.bind(Id.scala:20)
    at scalaz.StateT$$anonfun$flatMap$1.apply(StateT.scala:48)
    at scalaz.StateT$$anon$7.apply(StateT.scala:72)
    at scalaz.StateT$$anonfun$flatMap$1.apply(StateT.scala:48)
    at scalaz.StateT$$anon$7.apply(StateT.scala:72)
    at scalaz.StateT$$anonfun$flatMap$1$$anonfun$apply$2.apply(StateT.scala:49)
    at scalaz.StateT$$anonfun$flatMap$1$$anonfun$apply$2.apply(StateT.scala:48)

我的问题是 - 避免 scalaz.stateT 中堆栈溢出的最佳方法是什么？我想继续使用状态单子(monad)，就像在我的真实示例中一样，如果使 XML 序列化逻辑更容易遵循和排除故障(实际输入结构是 JDI 镜像 objects and arrays 从实时调试 session 检索，内部值是嵌套字段值) .

编辑:解决嵌套堆栈问题:

import util.control.TailCalls
def nested2(n: Int, acc: Nested = Leaf): TailCalls.TailRec[Nested] =
  if (n == 0) TailCalls.done(acc)
  else TailCalls.tailcall(nested2(n - 1, if (n % 2 == 0) Bar(acc) else Foo(acc)))

Answer 1

蹦床可以帮助您避免此处的堆栈溢出。首先进行相同的设置:

sealed trait Nested
case object Leaf extends Nested
case class Foo(inner: Nested) extends Nested
case class Bar(inner: Nested) extends Nested

import scalaz.{Node => _, _}; import Scalaz._;
import scala.util.control.TailCalls, scala.xml._

case class Parents(foos: Int, bars: Int)

def nested(n: Int, acc: Nested = Leaf): TailCalls.TailRec[Nested] =
  if (n == 0) TailCalls.done(acc) else TailCalls.tailcall(
    nested(n - 1, if (n % 2 == 0) Bar(acc) else Foo(acc))
  )

一些略有不同的类型别名:

type TrampolinedState[S, A] = StateT[Free.Trampoline, S, A]
type ParentsS[A] = TrampolinedState[Parents, A]

为了方便起见，我们将导入 MonadState 实例的方法:

val monadState = MonadState[TrampolinedState, Parents]
import monadState._

其余部分实际上更加简洁，因为我们不需要 put 等上的类型参数:

def convertFoo(foo: Foo): ParentsS[Seq[Node]] = for {
  parents <- init
  _ <- put(Parents(parents.foos + 1, parents.bars))
  inner <- convert(foo.inner)
  _ <- put(parents)
} yield <foo count={ parents.foos.toString }/>.copy(child=inner)

def convertBar(bar: Bar): ParentsS[Seq[Node]] = for {
  parents <- init
  _ <- put(Parents(parents.foos, parents.bars + 1))
  inner <- convert(bar.inner)
  _ <- put(parents)
} yield <bar count={ parents.bars.toString }/>.copy(child=inner)

def convert(nested: Nested): ParentsS[Seq[Node]] = nested match {
  case Leaf => Seq[Node]().point[ParentsS]
  case foo@Foo(_) => convertFoo(foo)
  case bar@Bar(_) => convertBar(bar)
}

现在我们只需运行以下命令(例如):

convert(nested(2000).result).apply(Parents(0, 0)).run

这远远超出了普通 State 解决方案在我的机器上开始阻塞的程度。