5

ScalaでData Types ala CartefoldTermから関数を書き込もうとしています。ここに私がこれまでに持っているものがあります

def foldTerm[F[+_], A, B](e: Free[F, A], pure: A ⇒ B, imp: F[B] ⇒ B)(implicit F: Functor[F]): B =
  e.resume match { 
    case Right(a) ⇒ pure(a)
    case Left(x)  ⇒ imp(F.map(x)(foldTerm(_, pure, imp)))
}

これは機能しますが、Scala は末尾再帰を適切に最適化できないため、SOE が発生します。私はそれを修正しようとしましTrampolineたが、これまでのところ運がありません。既存の方法でこれを行うことができるはずだと思いますFreeが、私の試みはすべて欲求不満に終わりました。

私は何が欠けていますか？

4

2 に答える 2

2

結局のところ、これは私の問題ではなかったことがわかりました。私はListT.fromList大きなリストで a を使用していましたが、それがスタックを吹き飛ばしていました。使用するように切り替えるとStreamT、問題が修正されました。

于 2012-07-13T17:18:21.380 に答える
2

Scala は末尾の再帰呼び出しを適切に排除できます。しかし、あなたの方法は末尾再帰ではありません。@annotaion.tailrec注釈で確認できます。

@annotation.tailrec
def foldTerm[F[+_], A, B](e: Free[F, A], pure: A ⇒ B, imp: F[B] ⇒ B)(implicit F: Functor[F]): B =
  e.resume match { 
    case Right(a) ⇒ pure(a)
    case Left(x)  ⇒ imp(F.map(x)(foldTerm(_, pure, imp)))
}

<console>:19: error: could not optimize @tailrec annotated method foldTerm: it contains a recursive call not in tail position
           case Left(x)  ⇒ imp(F.map(x)(foldTerm(_, pure, imp)))

ここでの最後の呼び出しはimpではなくfoldTermです。

于 2012-07-13T08:06:53.370 に答える