Wie geschachtelte Struktur beim Traversieren mit State Monad behandelt werden

Question

Ich habe eine verschachtelte Strukturen, die ich mit einer Scalaz State Monade in XML umwandeln. Dies funktioniert gut, bis ich mit verschachtelten Multilevel-Strukturen umgehen muss. Hier ist ein vereinfachtes Beispiel ähnlich dem, was ich gerade mache. Angesichts der folgenden ADT:

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

Ich schreibe einen Konverter Objekt den Zustand Monade mit (nehmen Scalaz7 und die folgenden Importe 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)) 
    } 

Je nach meinen Stack-Einstellungen convert(nested(1000)).apply(Parents(0, 0)) wird einen Stapelüberlauf verursachen im Umwandlungsprozess. (Höhere Werte nested zum Überlaufen bringen, aber das ignoriert werden kann, da ich für diese Frage nur nested erstellt.):

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) 

Meine Frage ist - was ist der beste Weg, um den Stapelüberlauf in scalaz.stateT zu vermeiden? Ich würde gerne die Zustands-Monade wie in meinem realen Beispiel verwenden, wenn die XML-Serialisierungslogik einfacher zu verfolgen und zu beheben ist (die tatsächlichen Eingabestrukturen sind JDI gespiegelt objects and arrays aus Live-Debugging-Sitzungen abgerufen und die inneren Werte sind verschachtelte Felder Werte).

Edit: die verschachtelte Stapel Ausgabe nehmen:

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 können Sie den Stack-Überlauf hier vermeiden helfen. Zunächst für die gleiche Einstellung:

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

Einige etwas andere Art Aliase:

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

und der Rest:

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

Wir haben unsere Methoden MonadState Instanz aus Gründen der Bequemlichkeit importieren werden ist eigentlich etwas knapper, da wir die Typparameter put, etc .:

nicht benötigen

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

Jetzt laufen wir nur die folgende (zum Beispiel):

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

Dies funktioniert auf meinem Rechner weit über den Punkt hinaus, dass die Vanille State Lösung begann Würgen.