为什么在getOrElse中返回使尾部递归不可能？

Question

我很困惑下面的代码：代码是人为的，但我仍然认为它是尾递归。编译器不同意并产生一条错误消息：

@annotation.tailrec 
def listSize(l : Seq[Any], s: Int = 0): Int = { 
    if (l.isEmpty) { 
    None.getOrElse(return s) 
    } 
    listSize(l.tail, s + 1) 
} 

上面的代码如何使tail tail recusion不可能？为什么编译器告诉我：

could not optimize @tailrec annotated method listSize: it contains a recursive call not in tail position

类似的代码（与return的map内）编译罚款：

@annotation.tailrec 
def listSize(l : Seq[Any], s: Int = 0): Int = { 
    if (l.isEmpty) { 
    Some(()).map(return s) 
    } 
    listSize(l.tail, s + 1) 
} 

即使通过内联None.isEmpty获得的代码编译好：

@annotation.tailrec 
def listSize(l : Seq[Any], s: Int = 0): Int = { 
    if (l.isEmpty) { 
    if (None.isEmpty) { 
     return s 
    } else None.get 
    } 
    listSize(l.tail, s + 1) 
} 

另一方面，代码略有修改的地图是被排除呃并产生错误：

@annotation.tailrec 
def listSize(l : Seq[Any], s: Int = 0): Int = { 
    if (l.isEmpty) { 
    Some(()).map(x => return s) 
    } 
    listSize(l.tail, s + 1) 
} 

Answer 1

这是因为您的第一个片段中的return是非本地片段（它嵌套在lambda中）。斯卡拉使用了异常编译非本地return表情，所以代码被编译器从这一转变：

@annotation.tailrec 
def listSize(l : Seq[Any], s: Int = 0): Int = { 
    if (l.isEmpty) { 
    None.getOrElse(return s) 
    } 
    listSize(l.tail, s + 1) 
} 

的东西类似这（与scalac -Xprint:tailcalls编译）：

def listSize2(l : Seq[Any], s: Int = 0): Int = { 
    val key = new Object 

    try { 
    if (l.isEmpty) { 
     None.getOrElse { 
     throw new scala.runtime.NonLocalReturnControl(key, 0) 
     } 
    } 

    listSize2(l.tail, s + 1) 
    } catch { 
    case e: scala.runtime.NonLocalReturnControl[Int @unchecked] => 
     if (e.key == key) 
     e.value 
     else 
     throw e 
    } 
} 

的最后一点是递归调用在try/catch块中封装时不是尾调用。基本上，这contrieved例如：

def self(a: Int): Int = { 
    try { 
    self(a) 
    } catch { 
    case e: Exception => 0 
    } 
} 

类似于此，这显然是不尾递归：

def self(a: Int): Int = { 
    if (self(a)) { 
    // ... 
    } else { 
    // ... 
    } 
} 

有某些特定情况下，可以优化本（到两个堆栈帧，如果不是一个），但似乎没有适用于这种情况的普遍规则。

而且，在该片段中return表达，是不是非本地return，这就是为什么该函数可被优化：

@annotation.tailrec 
def listSize(l : Seq[Any], s: Int = 0): Int = { 
    if (l.isEmpty) { 
    // `return` happens _before_ map `is` called. 
    Some(()).map(return s) 
    } 
    listSize(l.tail, s + 1) 
} 

上述工作，因为在Scala中，return e是一个表达式，不是一个声明。它的类型是Nothing，不过，它是一切的子类型，其中包括Unit => X，这是map的参数所需的类型。虽然评估很简单，但在执行map之前，函数返回e（显然，在方法调用之前评估参数）。这可能会令人困惑，因为你认为map(return e)被解析/解释为map(_ => return e)，但事实并非如此。

Answer 2

return总是打断递归调用。你应该改变你的代码到这样的东西：

@tailrec 
def listSize(l : Seq[Any], s: Int = 0): Int = { 
    l match { 
    case Nil => s 
    case head :: tail => listSize(tail, s + 1) 
    } 
} 

Answer 3

我不能现在就试试看，但这会解决这个问题吗？

@annotation.tailrec 
def listSize(l : Seq[Any], s: Int = 0): Int = { 
    if (l.isEmpty) { 
    None.getOrElse(return s) 
    } else { 
    listSize(l.tail, s + 1) 
    } 
} 

使用if-else，而不是仅仅if将确保if语句总是返回值。

Answer 4

这几乎肯定是编译器或部分实现的功能的错误。

它很可能与在斯卡拉表达式中执行return有关。使用异常实现非本地return语句，以便在调用return时引发NonLocalReturnException，并将整个表达式包装在try-catch中。我敢打赌，x => return x被转换为嵌套表达式，当它被封装在try-catch中时，在确定它是否可以使用@tailrec时会混淆编译器。我甚至会说，应该避免使用@tailrec与非本地return一起使用。

阅读更多关于return在斯卡拉的履行this博客文章或在this问题。