2

続きで遊んでいるだけです。目標は、別の関数をパラメーターとして受け取り、実行量を受け取る関数を作成し、指定された量の時間パラメーターを適用する関数を返すことです。

実装はかなり明白に見えます

def n_times[T](func:T=>T,count:Int):T=>T = {
  @tailrec
  def n_times_cont(cnt:Int, continuation:T=>T):T=>T= cnt match {
        case _ if cnt < 1 => throw new IllegalArgumentException(s"count was wrong $count")
        case 1 => continuation
        case _ => n_times_cont(cnt-1,i=>continuation(func(i)))
      }
  n_times_cont(count, func)
}

def inc (x:Int) = x+1

    val res1 = n_times(inc,1000)(1)  // Works OK, returns 1001

val res = n_times(inc,10000000)(1) // FAILS

しかし、問題はありません。このコードは StackOverflow エラーで失敗します。ここにテールコールの最適化がないのはなぜですか?

Scala プラグインを使用して Eclipse で実行していますが、スレッド「メイン」で例外が返されます java.lang.StackOverflowError at scala.runtime.BoxesRunTime.boxToInteger(Unknown Source) at Task_Mult$$anonfun$1.apply(Task_Mult.scala: 25) at Task_Mult$$anonfun$n_times_cont$1$1.apply(Task_Mult.scala:18)

ps

ほぼ直訳であるF#のコードは問題なく動作しています

let n_times_cnt func count = 
    let rec n_times_impl count' continuation = 
        match count' with
        | _ when count'<1 -> failwith "wrong count"
        | 1 -> continuation
        | _ -> n_times_impl (count'-1) (func >> continuation) 
    n_times_impl count func

let inc x = x+1
let res = (n_times_cnt inc 10000000) 1

printfn "%o" res
4

2 に答える 2

4

Scala 標準ライブラリには、トランポリンの実装が含まれていscala.util.control.TailCallsます。実装を再検討しています... でネストされた呼び出しを構築するとcontinuation(func(t))、それらは末尾呼び出しであり、コンパイラによって最適化されません。T => TailRec[T]それでは、スタック フレームがヒープ内のオブジェクトに置き換えられる を作成しましょう。次に、引数を取り、そのトランポリン関数に渡す関数を返します。

import util.control.TailCalls._
def n_times_trampolined[T](func: T => T, count: Int): T => T = {
  @annotation.tailrec
  def n_times_cont(cnt: Int, continuation: T => TailRec[T]): T => TailRec[T] = cnt match {
    case _ if cnt < 1 => throw new IllegalArgumentException(s"count was wrong $count")
    case 1 => continuation
    case _ => n_times_cont(cnt - 1, t => tailcall(continuation(func(t))))
  }
  val lifted : T => TailRec[T] = t => done(func(t))
  t => n_times_cont(count, lifted)(t).result
}
于 2013-07-04T03:57:55.470 に答える
1

n_times_contここで間違っている可能性がありますが、内部関数が末尾再帰を使用するように適切に変換されていると思われます。犯人はそこにいません。

main 関数の結果を適用すると、メソッドに対して 10000000 回のネストされた呼び出しを行う、収集されたcontinuationクロージャー (つまり)によってスタックが爆破されます。i=>continuation(func(i))inc

実際に試すことができます

scala> val rs = n_times(inc, 1000000)
rs: Int => Int = <function1> //<- we're happy here

scala> rs(1) //<- this blows up the stack!

余談ですが、あなたは書き直すことができます

i=>continuation(func(i))

なので

continuation compose func

より読みやすくするために

于 2013-05-14T10:24:31.010 に答える