Утверждение @tailrec на Option.getOrElse - PullRequest
Новая
       11

Утверждение @tailrec на Option.getOrElse

2 голосов
/ 04 мая 2011

Далее строка maybeNext.map{rec}.getOrElse(n) использует монаду Option для реализации шаблона рекурсии или выхода. 

scala> @tailrec                                          
     | def rec(n: Int): Int = {                          
     |   val maybeNext = if (n >= 99) None else Some(n+1)
     |   maybeNext.map{rec}.getOrElse(n)                 
     | }

Хорошо выглядит, однако: 

<console>:7: error: could not optimize @tailrec annotated method: 
it contains a recursive call not in tail position
       def rec(n: Int): Int = {
           ^

Я чувствую, что компилятор должен быть в состоянии разобраться с хвостовой рекурсией в этом случае. Это эквивалентно следующему (несколько отталкивающему, но компилируемому) образцу: 

scala> @tailrec                                          
     | def rec(n: Int): Int = {                          
     |   val maybeNext = if (n >= 99) None else Some(n+1)
     |   if (maybeNext.isEmpty) n                        
     |   else rec(maybeNext.get)                         
     | }
rec: (n: Int)Int

Может ли кто-нибудь обеспечить освещение здесь? Почему компилятор не может понять это? Это ошибка или недосмотр? Проблема слишком сложна?

Редактировать: удалить @tailrec из первого примера и метод компилируется; цикл заканчивается. Последний вызов всегда getOrElse, что эквивалентно if option.isEmpty defaultValue else recurse. Я думаю, что это может и должно быть выведено компилятором.

1 Ответ

8 голосов
/ 04 мая 2011

Это не ошибка, это не недосмотр и не хвостовая рекурсия.

Да, вы можете написать код в хвостовой рекурсивной манере, но этоне означает, что каждый эквивалентный алгоритм можно сделать хвостовым рекурсивным.Давайте возьмем этот код: 

maybeNext.map{rec].getOrElse(n)

Во-первых, последний звонок - getOrElse(n).Этот вызов не является обязательным - он всегда выполняется, и необходимо скорректировать результат.Но давайте проигнорируем это.

Следующий за последним вызовом - map{rec}. Не до rec.На самом деле, rec не называется вообще в вашем коде!Некоторая другая функция вызывает его (и, фактически, это не последний вызов map), но не ваша функция.

Чтобы что-то было хвостовым рекурсивно, вам нужно иметь возможность заменитьзвонить с "гото", так сказать.Например: 

def rec(n: Int): Int = { 
  BEGINNING:                         
  val maybeNext = if (n >= 99) None else Some(n+1)
  if (maybeNext.isEmpty) n                        
  else { 
    n = maybeNext.get
    goto BEGINNING
   }                         
}

Как это могло бы произойти в другом коде? 

def rec(n: Int): Int = {                  
  BEGINNING:        
  val maybeNext = if (n >= 99) None else Some(n+1)
  maybeNext.map{x => n = x; goto BEGINNING}.getOrElse(n)                 
}

Goto здесь не внутри rec.Он находится внутри анонимного Function1 apply, который, в свою очередь, находится внутри Option map, поэтому ветвь здесь будет оставлять два стековых фрейма при каждом вызове.Предполагая, что ветвление между методами было возможно в первую очередь.

...