在Clojure中对河内塔进行TCO优化

Question

我正在读一门Introdution to 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托管的，因此默认情况下没有总拥有成本，人们应该使用recur来获得它(我知道这个故事……)。另一方面，recur施加了一些语法约束，因为它必须是最后一个表达式-必须是尾部。我感觉有点糟糕，因为我仍然不能编写一个像Haskell那样简短/富有表现力的解决方案，同时使用TCO。

有没有一个简单的解决方案，我现在还看不到？

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

Answer 1

不，Haskell代码不是尾递归的。它是有保护的递归的，递归由一个惰性数据构造函数: ( ++调用最终被转换到这个构造函数)来保护，由于惰性，只有一部分递归调用树(a ++ b ++ c)被轮流探索，所以堆栈的深度永远不会超过n，即磁盘的数量。它非常小，像7或8。

因此，Haskell代码将c部分放在一边，探索a。另一方面，您的Clojure代码在连接这两个部分(a和c，因为b不计算它们)之前先计算它们，所以是双重递归的，即计算量很大。

您正在寻找的不是总体拥有成本，而是TRMCO -- tail recursion 优化--即以自上而下的方式从具有模拟堆栈的循环内部构建列表。Clojure特别适合这一点，它的尾部附加conj (对吗？)而不是Lisp和Haskell的头部前缀cons。

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

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