Оптимизация рекурсии Scala Tail для логических операций с коротким замыканием

Я написал такую ​​функцию на 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)
    }
}

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


scala short-circuiting tail-recursion
person Travis Parks    schedule 19.03.2013    source источник
comment
вот что _1 _ для   -  person om-nom-nom    schedule 19.03.2013
comment
Прохладный. Вроде оптимизирован. Спасибо!   -  person Travis Parks    schedule 19.03.2013
comment
Чтобы было ясно, @tailrec не делает метод хвостовой рекурсивным волшебным образом, он делает ошибку, если он не является хвостовой рекурсией.   -  person Randall Schulz    schedule 19.03.2013

Ответы (1)


arrow_upward
3
arrow_downward

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

В этом можно убедиться на простом примере:

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

Компилятор вылетает со следующей ошибкой:

test.scala: 6: ошибка: не удалось оптимизировать аннотированный метод @tailrec факт: он содержит рекурсивный вызов не в хвостовой позиции

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

person Impredicative    schedule 19.03.2013
comment
Интересное определение fact у вас там :) - person Mysterious Dan; 19.03.2013