将“几乎尾部位置”中的递归调用移动到真正尾部位置

Question

在阅读Guido关于不在Python中添加尾部递归消除的推理时，我在Haskell中编造了这个几乎尾部递归的示例：

triangle :: Int -> Int
triangle 0 = 0
triangle x = x + triangle (x - 1)

这当然不是尾部调用，因为尽管递归调用本身在“return”中，但是x阻止了当前堆栈被重用为递归调用。

但是，可以将其转换为尾递归代码（尽管相当丑陋和冗长）：

triangle' :: Int -> Int
triangle' = innerTriangle 0
    where innerTriangle acc 0 = acc
          innerTriangle acc x = innerTriangle (acc + x) (x - 1)

这里innerTriangle是尾递归的，由triangle启动。虽然微不足道，但这样的转换似乎也适用于其他任务，例如构建列表（这里acc可能只是正在构建的列表）。

当然，如果递归调用不在函数return中，这似乎是不可能的：

someRecusiveAction :: Int -> Bool
someRecursiveAction x = case (someRecursiveAction (x * 2)) of
    True -> someAction x
    False -> someOtherAction x

但我只是指几乎尾部调用，其中递归调用是返回值的一部分，但由于另一个函数应用程序包装它而不在尾部位置（例如上面三角形示例中的x）。

这在功能上下文中可以概括吗？那么命令式的呢？所有返回中包含递归调用的函数能否转换为返回位于尾部位置的函数（即可以进行尾部调用优化的函数）？

没关系，这些都不是在Haskell中计算三角形数的“最佳”方法，AFAIK是三角形x=sum[0... n]。该代码纯粹是这个问题的一个人为示例。

注意：我已经阅读了是否有不能使用尾递归编写的问题？，所以我相当有信心我的问题的答案是肯定的。然而，答案提到了延续传递风格。除非我误解了CPS，否则我的转换后的三角形'似乎仍然是直接风格。在这种情况下，我很好奇如何使这种转换在直接风格中推广。

Answer 1

有一个有趣的尾部递归模算子优化空间，可以转换一些函数，使其在恒定空间中运行。最著名的可能是尾递归模cons，其中不完全的尾调用是构造函数应用程序的参数。（这是一个古老的优化，可以追溯到Prolog编译器的早期——我认为Warren Abstract Machine fame的David Warren是第一个发现它的人）。

但是，请注意，这种优化不太适合懒惰的语言。像Haskell这样的语言有非常不同的评估模型，其中尾部调用并不那么重要。在Haskell中，可能需要一个包含递归调用的构造函数应用程序，因为它将阻止对递归调用的立即求值，并允许惰性地使用计算。请参阅Haskell Wiki页面上的讨论。

下面是一个用严格语言进行模约束优化的示例：

let rec map f = function
  | [] -> []
  | x::xs -> f x::map f xs

在这个OCaml函数中，对映射的递归调用是位于尾部的构造函数应用程序的参数，因此可以应用模约束优化。（OCaml尚未进行此优化，尽管有一些实验补丁正在四处浮动。）

转换后的函数可能类似于以下psuedo-OCaml。注意，内部循环是尾部递归的，通过改变之前的cons来工作：

let rec map f = function
  | [] ->
  | x::xs ->
    let rec loop cons = function
      | [] -> cons.[1] <- []
      | y::ys ->
        let new_cons = f y::NULL in
        cons.[1] <- new_cons;
        loop new_cons ys in
    loop (f x::NULL) xs

（其中NULL是GC不会阻塞的某个内部值。）

尾考虑在Lisp中也很常见，通过一种不同的机制：在那里，突变倾向于显式编程，混乱的细节隐藏在宏中，例如循环。

如何推广这些方法是一个有趣的问题。