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

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

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 не находится в хвостовой позиции. Но он ЕСТЬ в хвостовом положении. Есть ли способ исправить это без батута?


recursion scala functional-programming purely-functional tail-recursion
person Savenkov Alexey    schedule 27.12.2016    source источник

Ответы (1)


arrow_upward
6
arrow_downward

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

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

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