7

私は、scalaz 状態モナドを使用して XML に変換しているネストされた構造を持っています。これは、複数レベルのネストされた構造を処理する必要があるまではうまく機能します。これは、私がやっていることと同様の単純化された例です。次の ADT があるとします。

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

state モナドを使ってコンバーターオブジェクトを書きます (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)))
4

1 に答える 1

4

ここでトランポリンを使用すると、スタック オーバーフローを回避できます。最初に同じセットアップの場合:

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残りの部分は、 onなどの型パラメーターを必要としないため、実際にはもう少し簡潔です。

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これは、バニラソリューションが私のマシンで窒息し始めた時点をはるかに超えて機能します。

于 2012-12-17T22:55:47.750 に答える