scala – 是否可以使用延续来使foldRight的尾部递归?
发布时间:2020-12-16 18:58:20 所属栏目:安全 来源:网络整理
导读:以下 blog article显示了如何在F#foldBack中使用延续传递风格进行尾递归递归. 在Scala中,这意味着: def foldBack[T,U](l: List[T],acc: U)(f: (T,U) = U): U = { l match { case x :: xs = f(x,foldBack(xs,acc)(f)) case Nil = acc }} 可以通过这样做来做
以下
blog article显示了如何在F#foldBack中使用延续传递风格进行尾递归递归.
在Scala中,这意味着: def foldBack[T,U](l: List[T],acc: U)(f: (T,U) => U): U = { l match { case x :: xs => f(x,foldBack(xs,acc)(f)) case Nil => acc } } 可以通过这样做来做尾巴递归: def foldCont[T,U](list: List[T],U) => U): U = { @annotation.tailrec def loop(l: List[T],k: (U) => U): U = { l match { case x :: xs => loop(xs,(racc => k(f(x,racc)))) case Nil => k(acc) } } loop(list,u => u) } 不幸的是,我仍然为长列表获得堆栈溢出.循环是尾递归和优化,但我猜,堆栈积累只是移动到继续调用. 为什么这不是F#的问题?有没有办法解决这个与Scala? 编辑:这里显示堆栈深度的一些代码: def showDepth(s: Any) { println(s.toString + ": " + (new Exception).getStackTrace.size) } def foldCont[T,k: (U) => U): U = { showDepth("loop") l match { case x :: xs => loop(xs,(racc => { showDepth("k"); k(f(x,racc)) })) case Nil => k(acc) } } loop(list,u => u) } foldCont(List.fill(10)(1),0)(_ + _) 打印: loop: 50 loop: 50 loop: 50 loop: 50 loop: 50 loop: 50 loop: 50 loop: 50 loop: 50 loop: 50 loop: 50 k: 51 k: 52 k: 53 k: 54 k: 55 k: 56 k: 57 k: 58 k: 59 k: 60 res2: Int = 10 解决方法
问题是连续函数(racc => k(f(x,racc)))本身.它应该是尾部优化的整个企业的工作,但不是.
Scala无法对任意尾部调用进行尾部调整优化,只能将其转换为循环(即函数调用自身而不是其他函数). (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |