只是玩延续。目标是创建将接收另一个函数作为参数和执行量的函数,并返回将应用参数给定次数的函数。
实现看起来很明显
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 中运行它,它返回
线程“main”中的异常 java.lang.StackOverflowError
在 scala.runtime.BoxesRunTime.boxToInteger(来源未知)
在 Task_Mult$$anonfun$1.apply(Task_Mult.scala:25)
在 Task_Mult$$anonfun$n_times_cont$1$1.apply(Task_Mult.scala:18)
p.s.
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
Scala 标准库has蹦床的实现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
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)