Как обрабатывать вложенную структуру при обходе с монадой состояний

У меня есть вложенные структуры, которые я конвертирую в XML с помощью монады состояния scalaz. Это хорошо работает, пока мне не придется иметь дело с многоуровневыми вложенными структурами. Вот упрощенный пример, похожий на то, что я делаю. Учитывая следующий ADT:

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

Я пишу объект-преобразователь, используя монаду состояния (предположим, что Scalaz7 и следующий импорт 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))
  }

В зависимости от настроек моего стека convert(nested(1000)).apply(Parents(0, 0)) вызовет переполнение стека в процессе преобразования. (более высокие значения вызовут переполнение nested, но это можно игнорировать, поскольку я только что создал nested для этого вопроса.):

    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)

У меня вопрос - как лучше всего избежать переполнения стека в scalaz.stateT? Я хотел бы продолжать использовать монаду состояния, как в моем реальном примере, если упростит отслеживание логики сериализации XML и устранение неполадок (фактические входные структуры являются зеркальными JDI объекты и массивы, полученные из сеансов отладки в реальном времени, а внутренние значения являются значениями вложенных полей).

Изменить: чтобы устранить проблему с вложенным стеком:

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

scala stack-overflow state-monad scalaz
person huynhjl    schedule 17.12.2012    source источник
comment
Мне вспомнилась эта ветка, которую я добавил в закладки. Я только что заметил, что вы это начали - groups.google.com/forum/#!topic / scalaz / QPUs6TWTAm4 Я постоянно использую StateT, но в итоге получаю что-то менее элегантное, когда я знаю, что собираюсь пройти более 200 или около того.   -  person drstevens    schedule 18.12.2012
comment
Я получил StackOverflow, просто запустив ваш вложенный метод с n = 1000 (без использования какого-либо кода Scalaz).   -  person paradigmatic    schedule 18.12.2012
comment
@paradigmatic, используйте батут nested2, который я только что добавил. Я подозреваю, что ответом на мою проблему также является батут convert, но для меня не очевидно, как это сделать элегантно.   -  person huynhjl    schedule 18.12.2012

Ответы (1)


arrow_upward
4
arrow_downward

Прыжки на батуте могут помочь вам избежать переполнения стека здесь. Сначала для той же настройки:

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

Несколько разных псевдонимов типов:

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

Для удобства мы импортируем методы нашего MonadState экземпляра:

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

А остальное на самом деле немного короче, поскольку нам не нужны параметры типа на put и т. Д .:

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

Теперь мы просто запускаем следующее (например):

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

Это работает далеко не тогда, когда ванильное State решение начало подавляться на моей машине.

person Travis Brown    schedule 17.12.2012
comment
Спасибо! Хотел бы я +10 к этому. Я использовал этот общий подход, чтобы предотвратить SO в нескольких местах, где я раньше выполнял List[A].traverse[({type λ[α] = State[S, α]})#λ, A]. Потребовалось некоторое время, чтобы понять, как это работает с Scalaz 6, но в конце концов я получил это. - person drstevens; 20.12.2012