下面,sumAllIf是尾部递归的,而sumAllFold不是。然而,sumAllIf实际上具有相同的实现。这是Scala编译器(或者Scala库)的一个缺点,还是我忽略了什么?
def maybeNext(in: Int): Option[Int] = if in < 10 then Some(in + 1) else None
// The Scala library implements Option.fold like this:
// @inline final def fold[B](ifEmpty: => B)(f: A => B): B =
// if
在这个站点和web的其他地方搜索,JVM不支持尾调用优化。因此,这是否意味着如果要在JVM上运行,就不应该编写尾部递归Scala代码,例如可以在非常大的输入列表上运行的以下代码?
// Get the nth element in a list
def nth[T](n : Int, list : List[T]) : T = list match {
case Nil => throw new IllegalArgumentException
case _ if n == 0 => throw new IllegalArgu
我在下面的F#定义中看到了一个连续传递风格的斐波纳契函数,我一直认为它是尾递归的:
let fib k =
let rec fib' k cont =
match k with
| 0 | 1 -> cont 1
| k -> fib' (k-1) (fun a -> fib' (k-2) (fun b -> cont (a+b)))
fib' k id
在Scala中尝试等效代码时,我使用了现有的@ tail are,当Scala编译器通知我递归调用不处于尾位置时,我感到措手不及:
def fib(k
这是“Scala中的函数编程”(Functional in Scala)第13章中的一个练习,用于实现用于解释尾递归函数的蹦床。
runTrampoline2不是尾递归的,它用我的测试输入溢出堆栈.此外,tailrec注释为runTrampoline2提供了一个编译器错误。runTrampoline是尾递归的,并通过注释的编译时检查。
我的最佳选择是,这两个蹦床之间的区别在于val捕获或不捕获一个单元的方式,就像下面这样:
scala> val foo = println("abc")
val foo = println("abc")
abc
foo: U
我来自一个面向对象的背景,在那里我主要用Java编写应用程序。我最近开始探索更多关于Scala的内容,我一直在阅读一些文本。因此,我遇到了一种叫做尾递归的东西。我知道如何编写尾递归方法。
例如-添加列表中的元素(当然可以使用reduce方法完成),但为了理解,我编写了一个尾递归方法:
@scala.annotation.tailrec
def sum(l: List[Int], acc: Int): Int = l match {
case Nil => acc
case x :: xs => sum(xs, acc + x)
}
Scala运行时如何在内部处理这种递归?
列出了关于组合函数如何导致StackOverflowError的以下示例。
scala> val f = (x: Int) => x
f: Int => Int = <function1>
scala> val g = List.fill(100000)(f).foldLeft(f)(_ compose _)
g: Int => Int = <function1>
scala> g(42)
java.lang.StackOverflowError
正如书中所解释的那样,g是一个复合函数,它有10万个函数,每个函数都调用下一个函数。
运行这段代码时:
object P01 {
@annotation.tailrec
final def lastRecursive[A] (ls:List[A]):A = {
def lr[A] (l:List[A]):A = l match {
case h :: Nil => h
case _ :: tail => lr(tail)
case _ => throw new NoSuchElementException
}
我是Scala的新手,在阅读David Pollack的“乞讨Scala”时尝试了一下。他定义了一个简单的递归函数来加载文件中的所有字符串:
def allStrings(expr: => String): List[String] = expr match {
case null => Nil
case w => w :: allStrings(expr)
}
它非常优雅和令人敬畏,除了在我试图加载一个巨大的字典文件时抛出了一个StackOverflow异常。
据我所知,Scala支持尾递归,所以函数调用不可能溢出堆栈,可能是编译器无法识别它?因此,在谷歌搜
我想知道是否有"functional“原因使函数heads不能在List中实现(或者更一般地说是在中实现)。对我来说,heads与tails完全相反,但我必须错过一些东西。
由于Scala很容易阅读,下面是我将看到的内容(对于List案例):
def heads[T](li:List[T]):List[List[T]] = li match {
case Nil => Nil
case head::tail => (Nil::heads(tail)).map(head::_)
}
因此,以下是我所想到的不执行此功能的几种可能性:
head代表了一个List的第一
我是Scala的新手,并开始学习尾递归。我了解到,函数编程中的尾递归是命令式编程中迭代(用于循环)的一个反部分:
简单的C++循环以求和列表元素:
uint32_t sum = 0;
for (size_t i = 0; i < list.length(); ++i) {
sum += list[i];
}
Scala递归等效:
def listSum(list: List[Int]): Int = {
def listSumHelper(list: List[Int], sum: Int): Int = {
if (list.isEmpty) sum
els
我有以下代码: val ls = List(0, -1, 2, -2)
var removeNegative = List[Int]()
def removeNegative(ls: List[Int]): Int = ls match {
case Nil => 0
case l::for(ls <- ls){
var removeNegative = List[Int]()
if(ls >= 0){
removeNegative = removeNegative :+ ls
}
最近,我开始用Scala编写大量的编程竞赛代码。(您可以看看这里的平台- )
关于问题的本质,我经常需要对数组或输入数据进行迭代。例如,有一个问题说明,在第一个输入行上,我将得到数字M,然后我需要读取M行,或整数或其他什么。我试着用不同的方法:
for (i <- 0 until M)
----
(0 until M).foreach
----
var i = 0
while (i < M)
---
甚至尾递归
@tailrec
def recursion(i: Int): Unit = {
if (i < M) {
doSomething()
下面是一段最低限度的代码,它会导致编译错误“递归调用不在尾部位置”。但是,我使用的是@inline,递归调用位于尾位置。我使用这个@inline的原因是我将原始reccall的代码复制了两次。
import scala.annotation._
object Test {
@tailrec private def test(i: Int): Int = {
@inline def reccall(i: Int): Int = test(i-1)
i match {
case 0 => 0
case i => reccall(i)
我正试图在scala中使用quicksort的非递归版本,但每当我尝试实现它时,我都会卡住,最终使用尾递归。在Scala中有没有实现快速排序而不使用递归的简单方法?
感谢所有的帮助。谢谢!
编辑:已添加递归解决方案。在这个解决方案中,sortingHelper方法是尾递归的。
def quickSortRecursive(values: Array[Int]) {
// Swap the elements so that they aren't impacting recursion performance.
// This swap helps the pivot get t
我正在读M. Odersky的Scala编程,他说
像“近似”这样的函数称为“尾递归”,称自己为它们的最后一个动作。
所以,我试过这个
object Main extends App {
implicit val mc = new MyClass(8)
val ti = new TestImplct
ti.test
}
class TestImplct {
def test(implicit mc : MyClass): Unit = {
println(mc.i)
mc.i -= 1
if(mc.i < 0){
考虑以下递归幂法乘法:
import scala.annotation.tailrec
@tailrec def mult(x: Double, n:Int) : Double = {
n match {
case 0 => 1
case 1 => x
case _ if ((n & 0x01) != 0) => x * mult(x*x, (n-1)/2)
case _ => mult(x*x, n/2)
}
}
编译错误是:
<console>:28: error: could not op