爲什麼嵌套的FlatMaps可能會炸燬Scala中的堆棧？

我正在通過閱讀RúnarBjarnason的Stackless Scala with Free Monad這篇文章來學習斯卡拉的蹦牀技巧。但是我陷入了第4.3節「容易出錯」。爲什麼嵌套的FlatMaps可能會炸燬Scala中的堆棧？

有一件事讓我很困惑，f(x)可以直接觸發另一個內部呼叫給定FlatMap(x, f)。 resume已經是尾部遞歸，所以它必須發生在一個resume調用中。但是resume中的所有封裝函數都應該導致一個蹦牀實例。所以我找不到這樣的情況，堆棧仍然可能被炸燬。

任何人都可以舉一個例子來解釋「角落案例」嗎？謝謝。

=============

這是案件的背景，你還沒有看到真棒紙：

Scala編譯器只能在本地應用TCO /最終尾部位置自我通話功能。因此Trampoline是爲了將堆棧轉換爲堆棧而引入的。因此，在本文中，針對不同用途聲明瞭三個Trampoline實例。 Done用於包裝最終結果。 More代表下一步計算。並且FlatMap表示在下一步計算之後還有一件事要做。因此在定義bind操作後，Trampoline成爲Monad。請參閱下面的代碼（從紙）：

```

sealed trait Trampoline[+A] { 
    final def resume: A = this match { 
     case Done(v) => v 
     case More(k) => k().resume 
     case FlatMap(a, f) => a match { 
     case Done(v) => f(v).resume 
     case More(k) => (FlatMap(k(), f): Trampoline[A]).resume 
     case FlatMap(b, g) => (FlatMap(b, (x: Any) => FlatMap(g(x), f)): Trampoline[A]).resume 
     } 
    } 
    } 

    case class More[+A](k:() => Trampoline[A]) 
    extends Trampoline[A] 

    case class Done[+A](v: A) 
    extends Trampoline[A] 

    case class FlatMap[A, +B](sub: Trampoline[A], k: A => Trampoline[B]) extends Trampoline[B]

```

一切對我來說很有意義，直到它說，嵌套FlatMap仍然可以炸燬堆棧。這就是我在這裏問的原因。

來源

2017-07-13 SanCoder

這是一個有趣的問題的構造並且我認爲文章中闡述的問題的一個[MCVE]可能有助於提供一個答案（如果他們還沒有閱讀，我不認爲人們會閱讀一個8頁的PDF來回答這個問題）。 –

@YuvalItzchakov你是對的。我正在使用我的手機發布問題。一旦我回到我的鍵盤，將更新細節。謝謝。 – SanCoder

它使紙上的答案：

還有一個角落的情況下考慮這裏。如果FlatMaps的左傾塔比調用堆棧高，則現在可以使繼續溢出堆棧。然後調用F（V）將撥打電話 G（X），這將使另一個內心的召喚，等等

注意FlatMap (b , x => FlatMap (g(x), f))立即調用該函數

來源

2017-07-13 15:25:28 raam86

感謝您的回覆。根據我的理解，'x => FlatMap（g（x），f）'不會被立即評估。如果調用'g'會導致堆棧溢出，那麼如何禁止FlatMap構造函數解決問題呢？ – SanCoder

謝謝你的發人深省的問題。 'k：A =>蹦牀[B]'被推遲到被稱爲時，但是'sub：蹦牀[A]'是左傾斜 – raam86

爲什麼嵌套的FlatMaps可能會炸燬Scala中的堆棧？

回答

相關問題