TCO优化了Clojure的河内塔

Question

我正在阅读Haskell入门课程，他们正在介绍著名的河内塔问题作为第一堂课的家庭作业。我很想写一个解决方案：

type Peg = String
type Move = (Peg, Peg)
hanoi :: Int -> Peg -> Peg -> Peg -> [Move]
hanoi n b a e
  | n == 1 = [(b, e)]
  | n > 1 = hanoi (n - 1) b e a ++ hanoi 1 b a e ++ hanoi (n - 1) a b e
  | otherwise = []

我玩了一下，发现它显然使用了尾部调用优化，因为它在常量内存中工作。

Clojure

是我大部分时间使用的语言，因此我面临着编写Clojure解决方案的挑战。朴素的被丢弃，因为我想写它来使用 TCO：

(defn hanoi-non-optimized
  [n b a e]
  (cond
    (= n 1) [[b e]]
    (> n 1) (concat (hanoi-non-optimized (dec n) b e a)
                    (hanoi-non-optimized 1 b a e)
                    (hanoi-non-optimized (dec n) a b e))
    :else   []))

好吧，Clojure是JVM托管的，因此默认情况下没有TCO，应该使用recur来获取它(我知道这个故事......另一方面，recur施加了一些语法约束，因为它必须是最后一个表达式 - 必须是尾巴。我感觉有点糟糕，因为我仍然无法编写一个像 Haskell 中的解决方案那样简短/富有表现力的解决方案，同时使用 TCO。

有没有我目前看不到的简单解决方案？

我非常尊重这两种语言，并且已经知道这是我的方法而不是Clojure本身的问题。

Answer 1

不，Haskell代码不是尾递归的。它是守卫递归的，递归由惰性数据构造函数:(++调用最终转换为该函数(，由于懒惰，只有递归调用树的一部分(a ++ b ++ c(被依次探索，因此堆栈的深度永远不会超过n，即磁盘数。这非常小，比如 7 或 8。

所以Haskell代码探索了a，把c部分放在一边。另一方面，你的 Clojure 代码在连接它们之前计算两个部分(a 和 c b不算在内(，所以是双递归的，即计算量大。

你正在寻找的不是TCO，而是TRMCO - 尾递归模缺点优化，即从具有模拟堆栈的循环内部以自上而下的方式构建列表。Clojure特别适合于此，它的尾部附加conj(对吗？(而不是Lisp和Haskell的头部前缀cons。

或者只是打印动作，而不是构建所有动作的列表。

编辑：实际上，TRMCO意味着如果我们自己维护"延续堆栈"，我们就允许重用调用帧，因此堆栈深度正好变为1。在这种情况下，Haskell很可能构建了一个嵌套++ thunk节点的左加深树，正如这里所解释的，但是在Clojure中，当我们维护自己的待办事项下一个调用描述堆栈(用于a ++ b ++ c表达式的b和c部分(时，我们可以自己将其重新排列到右嵌套列表中。