Maa*_*mon 20 recursion haskell scala tail-recursion trampolines
由于 Scala 开发人员正在学习 IO Monad，因此一般来说，在无法进行尾调用优化的情况下，对于递归来说是必需的 Trampoliing 技术细节，我想知道 Haskell 是如何在本机上避免它的。
我知道 Haskell 是一种懒惰的语言，但是我想知道是否有人可以进一步详细说明。
例如，为什么 ForeverM stackoverflow 在 Scala 中没有？嗯，我可以回答蹦床，我可以在库和博客中找到执行此操作的实际代码。我实际上自己实现了一个基本的蹦床来学习。
它是如何在 Haskell 中发生的？有没有办法稍微解开懒惰，给出一些指示，也许还有有助于更好地理解它的文档？
sealed trait IO[A] {
.....
def flatMap[B](f: A => IO[B]): IO[B] =
FlatMap[A,B](this, f) // we do not interpret the `flatMap` here, just return it as a value
def map[B](f: A => B): IO[B] =
flatMap[B](f andThen (Return(_)))
}
case class Return[A](a: A) extends IO[A]
case class Suspend[A](resume: () => A) extends IO[A]
case class FlatMap[A,B](sub: IO[A], k: A => IO[B]) extends IO[B]
......
@annotation.tailrec
def run[A](io: IO[A]): A = io match {
case Return(a) => a
case Suspend(r) => r()
case FlatMap(x, f) => x match {
case Return(a) => run(f (a))
case Suspend(r) => run(f( r()))
case FlatMap(y, g) => run(y flatMap (a => g(a) flatMap f))
}
}
Lev*_*sey 23
函数式编程通常需要消除尾调用（否则函数调用的深层链会溢出堆栈）。例如，考虑一个偶数/奇数分类器的这个（非常低效）的实现：
def even(i: Int): Boolean =
if (i == 0) true
else if (i > 0) odd(i - 1)
else odd(i + 1)
def odd(i: Int): Boolean =
if (i == 0) false
else if (i > 0) even(i - 1)
else even(i + 1)
在evenand 中odd，每个分支要么是一个简单的表达式（true或false在这种情况下），它不进行函数调用或尾调用：被调用函数的值被返回而不被操作。
如果没有尾调用消除，则必须使用消耗内存的堆栈来实现（可能以无限长的循环递归）调用，因为调用者可能会对结果执行某些操作。尾调用消除依赖于观察调用者不对结果做任何事情，因此被调用的函数可以有效地替换堆栈上的调用者。
Haskell 和基本上所有其他 post-Scheme 函数式语言运行时都实现了广义的尾调用消除：尾调用变成了无条件跳转（想想 GOTO）。著名的系列斯蒂尔和萨斯曼论文（PDF文件遗憾的是没有得到存档，但你可以搜索，如AIM-443（mit或steele或sussman可能需要））被称为“拉姆达：终极”（这激发了编程语言的名称论坛）探讨了尾调用消除的含义，以及这如何意味着函数式编程对于解决现实世界的计算问题实际上是可行的。
然而，Scala 主要针对 Java 虚拟机，它的规范有效地（按设计）禁止了广义的尾调用消除，并且其指令集限制无条件跳转不跨越方法的边界。在某些有限的上下文中（基本上是一个方法的递归调用，其中编译器可以绝对确定正在调用什么实现），Scala 编译器在发出 Java 字节码之前执行尾调用消除（理论上可以想象 Scala Native 可以执行泛化尾调用消除，但这会导致 JVM 和 JS Scala 的一些语义中断（一些 JavaScript 运行时执行通用的尾调用消除，但据我所知不是 V8））。这@tailrec 您可能熟悉的注释强制要求编译器能够执行尾调用消除。
蹦床是一种在运行时模拟编译时尾调用消除的低级技术，尤其是在 C 或 Scala 等语言中。由于 Haskell 在编译时执行了尾调用消除，因此不需要 Trampoline 的复杂性（以及将高级代码编写为 continuation-passing 风格的要求）。
可以说，您可以将 Haskell 程序中的 CPU（或运行时本身，如果转换为例如 JS）视为实现蹦床。