如何让这个sieve函数变得懒惰？

Question

代码如下：

;; Helper function for marking mutiples of a number as 0
(defn mark 
  ([xs k m] (mark xs k m []))
  ([xs k m mark-vec] 
   (loop [[x & rest-xs] xs
          k k
          mark-vec mark-vec
          ]
     (cond 
       (and (nil? x) (nil? rest-xs)) mark-vec
       (= k m) (recur rest-xs 1       (conj mark-vec 0))
       :else   (recur rest-xs (inc k) (conj mark-vec x))
       ))))

;; Sieve of Eratosthenes
(defn sieve
  ([xs] (sieve xs []))
  ([xs sieve-res]
   (loop [[x & rest-xs] xs
          sieve-res sieve-res]
     (cond 
       (and (nil? x) (nil? rest-xs)) sieve-res
       (= x 0) (recur rest-xs sieve-res)
       :else   (recur (mark rest-xs 1 x) (conj sieve-res x))))))

(take 10 (sieve (range 2 100)))

我想让它接收像(iterate inc 2)这样的东西，并生成一个无限的素数序列。

Answer 1

最好的方法是构建一个适当的功能增量筛子，比如Melissa E.O‘’Neill的The Genuine Sieve of Eratosthenes中描述的那些筛子。

Christophe Grand发布了一些非常漂亮的增量式sieve实现here。