TCOに最適化されたClojureのハノイ塔

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がホストされているので、デフォルトでTCOを持っていない、もう1つはそれを得るためにrecurを使用する必要があります。 ..）。一方、recurは最後の式でなければならないので構文上の制約を課します。つまり、テールでなければなりません。なぜなら、Haskellのように短く/表現力豊かなソリューションを書くことができず、同時にTCOを使うことができないからです。

私は現時点で見ることができない簡単な解決法はありますか？

私は両方の言語に大きな敬意を払っていますが、これはClojure自身よりも私のアプローチではむしろ問題であることをすでに知っています。

Answer 1

いいえ、ハスケルコードはテール再帰的ではありません。 guarded - 再帰呼び出しが怠惰なデータコンストラクタである:（最終的には++コールが変換されます）で保護されています。怠惰のため、再帰呼び出しツリーの一部（a ++ b ++ c）のみが探索されます、スタックの深さはn、ディスクの数を超えることはありません。これは7または8のように非常に小さいです。

ハスケルのコードはaを探索し、cを脇に置いています。一方、あなたのClojureコードは、の前にの2つの部分（bは含まれていないので、とc）を計算するため、再帰的に計算が重くなります。

あなたが探しているのはTCOではなく、TRMCO-tail recursion modulo cons最適化です。つまり、シミュレートされたスタックのループ内からトップダウン方式でリストを構築します。 Clojureは、LispとHaskellの頭の先頭にあるconsの代わりに、末尾に末尾にconj（右？）を追加して、これに特に適しています。

または、すべてのリストを作成せずに印刷するだけです。

編集：は実際に、TRMCOたちは「継続スタック」自分自身を維持する場合は、スタックの深さを正確にになるように、我々は、呼び出しフレームを再利用することが許可されていることを意味します。 Haskellは、hereのように、この場合ネストされた++サンクノードの左に深いツリーを構築しますが、Clojureでは右のネストされたリストに再配置できます。 do-do-next呼び出しの説明（a ++ b ++ c式のbとc部分）。