Jak obsłużyć strukturę zagnieżdżoną podczas przechodzenia przez monadę stanu

Question

Mam zagnieżdżone struktury, które konwertuję do formatu XML za pomocą monady stanu skalowania. Działa to dobrze, dopóki nie mam do czynienia z wielopoziomowymi strukturami zagnieżdżonymi. Oto uproszczony przykład podobny do tego, co robię. Biorąc pod uwagę następujące ADT:

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

piszę obiektu konwertera używając monady państwowej (zakładając Scalaz7 oraz następujące import 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)) 
    } 

zależności od moich ustawieniach stosie convert(nested(1000)).apply(Parents(0, 0)) spowoduje przepełnienie stosu w procesie konwersji. (Wyższe wartości spowoduje nested przepełnienie, ale to może być ignorowane, ponieważ po prostu stworzony nested na to pytanie.):

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) 

Moje pytanie brzmi - co jest najlepszym sposobem, aby uniknąć przepełnienia stosu w scalaz.stateT? Chciałbym dalej używać monady stanu, jak w moim prawdziwym przykładzie, jeśli ułatwi to logikę serializacji XML i rozwiązywanie problemów (rzeczywiste struktury wejściowe są JDI dublowane objects and arrays pobrane z sesji debugowania na żywo, a wartości wewnętrzne są zagnieżdżonymi wartościami pól).

Edycja: aby wykupić zagnieżdżony problem stosu:

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

Trampolining może pomóc uniknąć przepełnienia stosu tutaj. Po pierwsze w tym samym Setup:

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

Niektóre nieznacznie różne aliasy Typ:

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

Będziemy importować metod naszego MonadState Instancji dla wygody:

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

i reszta jest trochę bardziej zwięzły, ponieważ nie potrzebujemy parametrów typu na put, itp .:

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

Teraz wystarczy uruchomić następujące (na przykład):

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

Działa to daleko poza punkt, że rozwiązanie wanilia State rozpoczęła dławiąc na moim komputerze.