Scala: Почему эта функция не является хвостовой рекурсивной?

Question

У меня есть такая реализация Merge Sort:

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(_))) 
    } 
} 

Это не компилируется. Он говорит, что рекурсивный вызов в шаг Функция не находится в положении хвоста. Но это находится в положении хвоста. Есть ли способ исправить это без батута?

Answer 1

Причина в том, что step - это функция, которая возвращает функцию подписи: Seq[Seq[T]] => Seq[T]. Таким образом, рекурсивный вызов не вызывает тот же метод напрямую, но сначала получает эту функцию, а затем вызывает его для заданного аргумента, который не является хвостовым рекурсивным.

Чтобы решить эту ошибку вы должны объявить step таким образом:

@tailrec 
def step(seq: Seq[Seq[T]]): Seq[T] = seq match { 
    ... 
}