如何在使用狀態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解決方案開始嗆我的機器上。