在Option.getOrElse上断言@tailrec

Question

在下面,该行maybeNext.map{rec}.getOrElse(n)使用Optionmonad来实现递归或转义模式.

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.我认为这可以而且应该由编译器推断出来.

Answer 1

它不是一个bug,它不是一个疏忽,它不是一个尾递归.

是的,您可以以尾递归方式编写代码,但这并不意味着每个等效算法都可以进行尾递归.我们来看看这段代码:

maybeNext.map{rec].getOrElse(n)

首先,最后一个电话是getOrElse(n).此调用不是可选的 - 它始终是,并且必须调整结果.但是,让我们忽略它.

倒数第二个电话是map{rec}.不给rec.其实,rec不叫都在你的代码!其他一些函数调用它(事实上,它不是最后一次调用map),但不是你的函数.

对于尾部递归的东西,你需要能够用"goto"替换这个调用,可以这么说.像这样:

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,所以这里的一个分支会离开每个呼叫的两个栈帧.假设首先可以进行方法间分支.