如何在使用状态monad进行遍历时处理嵌套结构
我有一个嵌套结构，我正在使用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
我使用state 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避免堆栈溢出的最佳方法是什么？ 如果让XML序列化逻辑更易于跟踪和排除故障（实际的输入结构是实时调试会话中检索的JDI镜像对象和数组，而内部值是嵌套字段值），我想继续使用状态monad， 。
编辑：取出嵌套的堆栈问题：
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)))
蹦床可以帮助您避免堆栈溢出。 首先进行相同的设置：
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解决方案在我的机器上开始窒息的问题。
上一篇: How to handle nested structure when traversing with state monad