Durum Monad ile geçiş yaparken iç içe yapı nasıl işlenir

Question

Bir scalaz devlet monad'ı kullanarak XML'e dönüştürdüğüm iç içe geçmiş yapılarım var. Çok seviyeli iç içe geçmiş yapılarla uğraşana kadar bu işe yarıyor. İşte yaptığım şeye benzeyen basitleştirilmiş bir örnek.

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

Ben devlet monad kullanan bir dönüştürücü nesneyi yazmak (Scalaz7 varsayalım ve aşağıdaki ithalatı 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)) 
    } 

benim yığın ayarlarına bağlı olarak, convert(nested(1000)).apply(Parents(0, 0)) yığın taşmasına neden olur Aşağıdaki ADT Verilen dönüşüm sürecinde. (Daha yüksek değerler taşmasına nested neden olur, ama sadece bu soru için nested oluşturulan beri bu göz ardı edilebilir.):

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) 

Sorum şu - scalaz.stateT ek bellek taşması kaçınmanın en iyi yolu nedir? XML serileştirme mantığını takip etmeyi ve sorun gidermeyi daha kolay hale getiriyorsa (gerçek giriş yapıları JDI yansır, canlı hata ayıklama oturumlarından alınan objects and arrays ve iç değerler iç içe geçmiş alanlar değerleridir) gerçek durumumda olduğu gibi, devlet monadını kullanmaya devam etmek isterim.

Düzenleme: İç içe yığın sorunu almaya:

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

Tramplen burada yığın taşması önlemeye yardımcı olabilir.

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

Ve diğerlerinden:

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

Biz kolaylık uğruna bizim MonadState örneğinin yöntemlerini aktaracağız:

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

Bazı biraz farklı tip takma adları: Aynı kurulum için ilk put, vb. tür parametrelerine ihtiyaç duymadığımızdan dolayı biraz daha kısa bir açıklama:

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

Şimdi sadece koşmak (örneğin) şunlardır:

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

Bu vanilya State çözüm benim makinede boğulmaya başladı o noktadan sonra çok çalışır.