Trampolining can help you avoid the stack overflow here. First for the same 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))
)
Some slightly different type aliases:
type TrampolinedState[S, A] = StateT[Free.Trampoline, S, A]
type ParentsS[A] = TrampolinedState[Parents, A]
We'll import our MonadState
instance's methods for the sake of convenience:
val monadState = MonadState[TrampolinedState, Parents]
import monadState._
And the rest is actually a little more concise, since we don't need the type parameters on put
, etc.:
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)
}
Now we just run the following (for example):
convert(nested(2000).result).apply(Parents(0, 0)).run
This works far past the point that the vanilla State
solution started choking on my machine.