如何在使用状态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 

我写的使用状态单子转换器对象（假设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镜像objects and arrays，内部值是嵌套字段值），我想继续使用状态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))) 

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解决方案开始呛我的机器上。