Scala Хвостовая рекурсия Оптимизация на короткозамкнутым операций булевой

Question

Я написал функцию, как это в Scala:

def isSorted[T](list : List[T])(compare : (T, T) => Boolean) : Boolean = { 
    list match { 
     case Nil => true 
     case x :: Nil => true 
     case x :: rest => !compare(rest.head, x) && isSorted(rest)(compare) 
    } 
} 

Мне интересно, будет ли компилятор оптимизировать на рекурсивный вызов. Рекурсивный вызов может только произойдет, если ведущее сравнение будет успешным. Если нет, есть ли способ взломать раньше и все же добиться оптимизации рекурсии хвоста?

Answer 1

Итак, как говорит @omnomnom, вы можете проверить, не является ли что-то TCO-ed, добавив аннотацию @tailrec к методу. Компилятор выдаст ошибку, если не сможет ее выбрать.

Мы можем проверить это с помощью простого примера:

@tailrec 
def fact(n : Int) : Int = fact(n - 1) * 2 

бомбы компилятор из-за ошибки:

test.scala:6: error: could not optimize @tailrec annotated method fact: it contains a recursive call not in tail position

Попытка это на вашей программе, однако, ответ ... да! Поэтому, по-видимому, компилятор с удовольствием оптимизирует ваш хвост: -)