爲什麼在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問題。