Come gestire la struttura nidificata durante lo spostamento con monade di stato

Question

Ho una struttura nidificata che sto convertendo in XML utilizzando una monade di stato scalaz. Funziona bene finché non ho a che fare con strutture nidificate a più livelli. Ecco un esempio semplificato simile a quello che sto facendo. Dato il seguente ADT:

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

scrivo un oggetto convertitore utilizzando la monade stato (assumere Scalaz7 e le seguenti importazioni 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)) 
    } 

A seconda delle mie impostazioni di stack, convert(nested(1000)).apply(Parents(0, 0)) causerà un overflow dello stack nel processo di conversione. (Valori più elevati causerà nested a traboccare, ma questo può essere ignorato dal momento Ho appena creato nested per questa domanda.):

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) 

La mia domanda è - qual è il modo migliore per evitare l'overflow dello stack in scalaz.stateT? Vorrei continuare a utilizzare la monade di stato come nel mio esempio reale se rende più semplice seguire la logica di serializzazione XML e risolvere i problemi (le strutture di input effettive sono il mirroring JDI objects and arrays recuperato dalle sessioni di debug in tempo reale ei valori interni sono valori dei campi nidificati).

Edit: per estrarre il numero di stack nidificato:

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

trampolino può aiutare a evitare l'overflow dello stack qui. In primo luogo per la stessa impostazione:

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)) 
) 

Alcuni leggermente diverse di tipo alias:

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

ti importare i metodi della nostra istanza MonadState per comodità:

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

E il resto è in realtà un po 'più conciso, dal momento che non abbiamo bisogno dei parametri di tipo su put, ecc .:

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) 
} 

Ora dobbiamo solo eseguire il seguente (per esempio):

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

questo funziona gran lunga oltre il punto che la soluzione alla vaniglia State iniziato soffocamento sulla mia macchina.