用于无限序列的 lazy-seq 和堆栈溢出

Question

我试图向非FP程序员展示惰性序列或惰性求值的重要性。我写了这个黄金一代的实现来展示这个概念：

(defn primes-gen [sieve]
  (if-not (empty? sieve)
    (let [prime (first sieve)]
      (cons prime
            (lazy-seq (primes-gen
                       (filter (fn [x]
                                 (not= 0 (mod x prime)))
                               (rest sieve))))))))
;;;;; --------- TO SHOW ABOUT THE LAZY-THINGS 
;; (take 400 (primes-gen (iterate inc 2)))
;; (take 400 (primes-gen (range 2 1000000000000N)))

但是，如果我给take任何更大的值，我就会得到堆栈溢出异常。

堆栈是：

user> (pst)
StackOverflowError 
    clojure.core/range/fn--4269 (core.clj:2664)
    clojure.lang.LazySeq.sval (LazySeq.java:42)
    clojure.lang.LazySeq.seq (LazySeq.java:60)
    clojure.lang.RT.seq (RT.java:484)
    clojure.core/seq (core.clj:133)
    clojure.core/filter/fn--4226 (core.clj:2523)
    clojure.lang.LazySeq.sval (LazySeq.java:42)
    clojure.lang.LazySeq.seq (LazySeq.java:60)
    clojure.lang.RT.seq (RT.java:484)
    clojure.core/seq (core.clj:133)

似乎filter的暴徒正在积累。但是如果(doall (filter ...这样做，那么我将无法处理无限序列，即 (take 1000 (primes-gen (iterate inc 2)))不再起作用了。

正确的方法是什么？

Answer 1

你的分析是正确的：你嵌套过滤器太多了。您应该修改 prime-gen 以采用两个参数：已知素数和候选素数的集合。请参阅我的博客，了解有关实施Erathostenes筛子的其他一些想法。

更新：因此，您将过滤器堆叠在过滤器上，并且在某些时候，当您想要获取新的候选对象时，堆栈太大。

您必须将所有过滤器合并到单个（或合理数量的）通道中。这里很容易，因为过滤器非常均匀。因此，我将过滤器堆栈替换为保存已知素数的集合。

(defn primes-gen
 ([candidates] (primes-gen candidates []))
 ([candidates known-primes]
  (lazy-seq ; I prefer having the lazy-seq up here
    (when-first [prime candidates] ; little known macro
      (let [known-primes (conj known-primes prime)]
        (cons prime
          (primes-gen
            (drop-while (fn [n] (some #(zero? (mod n %)) known-primes)) candidates)
             known-primes)))))))

Answer 2

可能的解决方案之一是在惰性 seq 中移动生成器函数。例如（取自此处）：

(def primes
  (concat
   [2 3 5 7]
   (lazy-seq
    (let [primes-from
          (fn primes-from [n [f & r]]
            (if (some #(zero? (rem n %))
                      (take-while #(<= (* % %) n) primes))
              (recur (+ n f) r)
              (lazy-seq (cons n (primes-from (+ n f) r)))))
          wheel (cycle [2 4 2 4 6 2 6 4 2 4 6 6 2 6  4  2
                        6 4 6 8 4 2 4 2 4 8 6 4 6 2  4  6
                        2 6 6 4 2 4 6 2 6 4 2 4 2 10 2 10])]
      (primes-from 11 wheel)))))