このClojure関数をスタックを吹き飛ばさないように書くにはどうすればいいですか？

Question

私はClojureには新しく、これまでのコードの作成方法は "Clojureの方法"と一致していないと思います。少なくとも、大きな値のStackOverflowエラーにつながる関数を書いています。私はrecurの使用について学びましたが、これは良い一歩です。しかし、以下のような関数を2500000のような値にするにはどうすればいいですか？

(defn fib [i] 
    (if (>= 2 i) 
    1 
    (+ (fib (dec i)) 
     (fib (- i 2))))) 

この関数は、私の目には、フィボナッチジェネレータの「単純な」実装です。私ははるかに最適化された他の実装を見てきましたが、彼らが何をするのかは明らかではありません。私。関数の定義を読むと、 "oh、fibonacci"にはなりません。

どのポインタも大変ありがとうございます。

Answer 1

機能の仕組みの精神モデルが必要です。呼び出しごとに紙のスクラップを使用して、自分で関数を実行するとします。最初のスクラップは(fib 250000)と書いてありますが、「ああ、(fib 249999)と(fib 249998)を計算して最後に追加する必要があります」というメッセージが表示されるので、2つの新しいスクラップを開始してください。最初のものを捨てることはできません。なぜなら、他の計算を終えた時点であなたのために行うことがまだ残っているからです。この計算には多くのスクラップが必要であると想像することができます。

もう1つの方法は、上からではなく、下から開始することです。手でこれをどうやってやりますか？あなたは最初の数字、1,1,3,2,3,5,8＆hellip;で始まり、最後に2つを加えます。それまでにi回行っています。各ステップで最後の2つを除くすべての数値を捨てることもできるので、ほとんどのスクラップを再利用することができます。

(defn fib [i] 
    (loop [a 0 
     b 1 
     n 1] 
    (if (>= n i) 
     b 
     (recur b 
       (+ a b) 
       (inc n))))) 

また、これはかなり明白な実装ではなく、どのようなの、どのようの。定義を書き留めるだけで、効率的な計算に自動的に変換されるときは、常にエレガントに見えますが、プログラミングはその変換です。何かが自動的に変換されると、この特定の問題はすでに解決されています（より一般的な方法で）。

「この手順を紙でどのように行うか」と考えると、しばしば良い実装につながります。

Answer 2

シーケンスの定義のように、「普通の」方法で実装されたフィボナッチ生成器は、常にスタックを吹き飛ばします。 fibへの2回の再帰呼び出しのどちらもテール再帰的ではなく、そのような定義を最適化することはできません。

残念ながら、大規模な数値を扱う効率的​​な実装を作成する場合は、数式表記がわれわれが望んでいるようにきれいにコードに変換されないという事実を受け入れる必要があります。

たとえば、非再帰的実装はclojure.contrib.lazy-seqsにあります。この問題に対する様々なアプローチの全範囲はHaskell wikiにあります。関数型プログラミングの基礎知識を理解するのは難しいことではありません。

Answer 3

;;from "The Pragmatic Programmers Programming Clojure" 
(defn fib [] (map first (iterate (fn [[a b]][b (+ a b)])[0N 1N]))) 
(nth (fib) 2500000)