scala - 尾递归问题

Question

我们在 Scala 中试验并行集合，并想检查结果是否有序。为此，我在 REPL 上编写了一个小函数来检查我们正在生成的非常大的列表：

def isOrdered(l:List[Int]):Boolean = { l match { 
  case Nil => true
  case x::Nil => true
  case x::y::Nil => x>y
  case x::y::tail => x>y & isOrdered(tail) 
  }
}

它以 stackOverflow 失败（这里的问题多么合适！）。我期待它是尾部优化的。怎么了？

Answer 1

isOrdered 不是代码中的最后一次调用， & 运算符是。试试这个：

@scala.annotation.tailrec def isOrdered(l:List[Int]):Boolean = { l match { 
  case Nil => true
  case x::Nil => true
  case x::y::Nil => x>y
  case x::y::tail => if (x>y) isOrdered(tail) else false
  }
}

Answer 2

你的算法不正确。即使@Kim 有所改进，也会isOrdered(List(4,3,5,4))返回true.

尝试这个：

def isOrdered(l:List[Int]): Boolean = l match {
  case Nil => true
  case x :: Nil => true
  case x :: y :: t => if (x <= y) isOrdered(l.tail) else false
}

（也更新，以便标志是正确的）

编辑：我的首选布局是这样的：

def isOrdered(list: List[Int]): Boolean = list match {
  case Nil      => true
  case x :: Nil => true
  case x :: xs  => if (x > xs.head) false
                   else isOrdered(xs)
}

如果性能不是问题的快速方法是

def isOrdered(l: List[Int]) = l == l.sorted

Answer 3

它不能进行尾部优化，因为您返回：'x>y & isOrdered(tail)'。这意味着它将需要将其保留在堆栈中。

当您期望函数是尾递归的时，使用 @tailrec 注释强制错误。它还将解释为什么不能。

Answer 4

我认为问题在于您在最后一种情况下使用了按位与运算符 (&)。由于运行时需要知道 isOrdered 调用的值才能评估 &，所以它不能对函数进行尾部优化。（也就是说，在调用 isOrdered 之后，还有更多代码要运行——按位与运算。）

使用 && 或 if 语句可能会有所帮助。