Scala:为什么这个函数不是尾递归的?
Scala: Why this function is not tail recursive?
我有这样的合并排序实现:
import scala.annotation.tailrec
object MergeSort {
def sortBy[T]: ((T, T) => Int) => Seq[T] => Seq[T] = comparator => seqToSort => {
@tailrec
def merge(xs : Seq[T], ys : Seq[T], accum : Seq[T] = Seq()) : Seq[T] = (xs, ys) match {
case (Seq(), _) => ys ++ accum
case (_, Seq()) => xs ++ accum
case (x::rx, y::ry) =>
if(comparator(x, y) < 0)
merge(xs, ry, y +: accum)
else
merge(rx, ys, x +: accum)
}
@tailrec
// Problem with this function
def step : Seq[Seq[T]] => Seq[T] = {
case Seq(xs) => xs
case xss =>
val afterStep = xss.grouped(2).map({
case Seq(xs) => xs
case Seq(xs, ys) => merge(xs, ys)
}).toSeq
// Error here
step(afterStep)
}
step(seqToSort.map(Seq(_)))
}
}
它不编译。它说 step 函数中的递归调用不在尾部位置。
但它处于尾部位置。有什么办法可以不用蹦床来修复吗?
原因是 step
是一个函数,returns 是签名函数:Seq[Seq[T]] => Seq[T]
。所以递归调用不是直接调用同一个方法,而是先获取这个函数,然后给定参数调用它,这不是尾递归。
要解决此错误,您必须这样声明 step
:
@tailrec
def step(seq: Seq[Seq[T]]): Seq[T] = seq match {
...
}
我有这样的合并排序实现:
import scala.annotation.tailrec
object MergeSort {
def sortBy[T]: ((T, T) => Int) => Seq[T] => Seq[T] = comparator => seqToSort => {
@tailrec
def merge(xs : Seq[T], ys : Seq[T], accum : Seq[T] = Seq()) : Seq[T] = (xs, ys) match {
case (Seq(), _) => ys ++ accum
case (_, Seq()) => xs ++ accum
case (x::rx, y::ry) =>
if(comparator(x, y) < 0)
merge(xs, ry, y +: accum)
else
merge(rx, ys, x +: accum)
}
@tailrec
// Problem with this function
def step : Seq[Seq[T]] => Seq[T] = {
case Seq(xs) => xs
case xss =>
val afterStep = xss.grouped(2).map({
case Seq(xs) => xs
case Seq(xs, ys) => merge(xs, ys)
}).toSeq
// Error here
step(afterStep)
}
step(seqToSort.map(Seq(_)))
}
}
它不编译。它说 step 函数中的递归调用不在尾部位置。 但它处于尾部位置。有什么办法可以不用蹦床来修复吗?
原因是 step
是一个函数,returns 是签名函数:Seq[Seq[T]] => Seq[T]
。所以递归调用不是直接调用同一个方法,而是先获取这个函数,然后给定参数调用它,这不是尾递归。
要解决此错误,您必须这样声明 step
:
@tailrec
def step(seq: Seq[Seq[T]]): Seq[T] = seq match {
...
}