Почему вложенные FlatMaps могут взорвать стек в Scala?

Question

Я изучаю трюк с батутом в Скале, читая эту статью Рунара Бьярнасона " Безжизненная скала со свободной монадой". Но я застрял в разделе 4.3 "Легко ошибиться".

Меня смущает то, как f(x) может напрямую вызвать другой внутренний вызов, учитывая FlatMap(x, f), resume это уже хвостовая рекурсия, так что это должно произойти в одном resume вызов. Но все обернутые функции в resume должен привести экземпляр батута. Поэтому я не могу найти случай, когда стек все еще может быть взорван.

Кто-нибудь может привести пример, чтобы объяснить "угловой случай"? Благодарю.

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

Это фон на случай, если вы еще не видели удивительную статью:

Компилятор Scala может применять TCO только к функции локального / конечного положения конечного положения. Так Trampoline переносится для преобразования стека в кучу. Таким образом, в документе, три случая Trampoline объявлены для разных видов использования. Done для упаковки окончательного результата. More представляет собой следующий шаг для расчета. А также FlatMap указывает на то, что есть еще одна вещь, которую нужно сделать после вычисления следующего шага. Итак, после определения bind операция к нему, Trampoline становится монадой. Смотрите код ниже (из бумаги):

`` `

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 все еще может взорвать стек И вот почему я спрашиваю это здесь.

Answer 1

Это дает ответ на бумаге:

Здесь стоит рассмотреть еще один угловой случай. Теперь возобновление может переполнить стек, если левая башня FlatMaps выше стека вызовов. Затем вызов f(v) сделает вызов g(x), который сделает еще один внутренний вызов и т. Д.

Обратите внимание на конструктор FlatMap (b , x => FlatMap (g( x), f )) вызывает функцию немедленно