2

我不明白为什么这个惰性素数序列的定义会导致不终止。我得到的堆栈跟踪不是很有帮助（我对 clojure 的一个抱怨是钝的堆栈跟踪）。

(declare naturals is-prime? primes)

(defn naturals
  ([] (naturals 1))
  ([n] (lazy-seq (cons n (naturals (inc n))))))

(defn is-prime? [n]
  (not-any? #(zero? (rem n %))
                (take-while #(> n (* % %)) (primes))))

(defn primes
  ([] (lazy-seq (cons 2 (primes 3))))
  ([n] (let [m (first (filter is-prime? (naturals n)))]
         (lazy-seq (cons m (primes (+ 2 m)))))))

(take 10 (primes)) ; this results in a stack overflow error
4

3 回答 3

0

问题是要知道计算“素数”函数您正在使用“是素数吗？” 函数，然后计算“是素数？” 您正在使用“（素数）”的函数，因此堆栈溢出。

所以要计算“(primes 3)”，你需要计算“(first (filter is-prime?(naturals 3)))”，它会调用“(is-prime?1)”，即调用“（素数）”，而后者又调用“（素数 3）”。换句话说，你正在做：

user=> (declare a b)
#'user/b
user=> (defn a [] (b))
#'user/a
user=> (defn b [] (a))
#'user/b
user=> (a)
StackOverflowError   user/b (NO_SOURCE_FILE:1)

要了解如何生成素数：Clojure 中的快速素数生成

于 2012-07-11T12:03:57.103 回答
0

让我们开始执行primes，我们会神奇地实现一个seq，只是为了清楚。我会忽略naturals，因为它是正确的懒惰：

 > (magically-realise-seq (primes))
=> (magically-realise-seq (lazy-seq (cons 2 (primes 3))))
=> (cons 2 (primes 3))
=> (cons 2 (let [m (first (filter is-prime? (naturals 3)))]
             (lazy-seq (cons m (primes (+ 2 3))))))
=> (cons 2 (let [m (first (filter
                            (fn [n]
                              (not-any? #(zero? (rem n %))
                                            (take-while #(> n (* % %)) (primes))))) 
                            (naturals 3)))]
             (lazy-seq (cons m (primes (+ 2 3))))))

我在最后替换is-prime?为 a fn——你可以看到它primes会再次被调用，并且至少实现一次作为take-while拉出元素。这将导致循环。

于 2012-07-11T12:04:07.550 回答
0

我认为问题在于，您在 (primes) 已经构建之前尝试使用它。

像这样改变is-prime?可以解决问题：

(defn is-prime? [n]
     (not-any? #(zero? (rem n %))
               (take-while #(>= n (* % %)) (next (naturals)))))

（请注意，我已更改>为>=，否则它给出了 4 是素数。它仍然说 1 是素数，这是不正确的，如果您is-prime?在其他地方使用可能会导致问题。

于 2012-07-11T12:15:32.823 回答