recursion - Clojure 関数でスタック オーバーフローを取得します。

Question

次の Clojure 関数でスタック オーバーフローが発生するのはなぜですか。

(defn length
  [xs]
  (if ,(not= xs nil)
    (println (+ 1 (length (rest xs))))
    (println 0)))

Answer 1

これを行う慣用的な方法はseq、コレクションを呼び出すことだと思います。 コレクションが空の場合はseq、コレクションを返します。nil

(defn length [xs]
  (if (seq xs)
      (inc (length (rest xs)))
      0))

これは末尾再帰ではない (使用してrecurおらず、ここでは使用できない) ため、非常に大きなコレクションではスタックがオーバーフローします。

user> (println (length (range 1000000)))
;; stack overflow

1 つの末尾再帰バージョンは次のようになります。

(defn length [xs]
  (loop [xs xs
         acc 0]
    (if (seq xs)
        (recur (rest xs) (inc acc))
        acc)))

user> (println (length (range 1000000)))
1000000

これは巨大なコレクションでもスタックをオーバーフローさせませんが、それでも遅いです。多くの Clojure コレクションはこのCountedインターフェースを実装しており、組み込みcount関数はこれらのコレクションの長さを定数時間で返します。

Answer 2

すべてのレイジー seq に切り替えた後、rest は決して nil を返さず、空のリストだけを返します - これを試してください:

(defn length 
   [xs]
   (if (not (empty? xs))
      (println (+ 1 (length (rest xs))))
      (println 0)))

またはこれ

(defn length
   [xs]
   (if ,(not= xs nil)
      (println (+ 1 (length (next xs))))
      (println 0)))