lazy-seq and stack overflow for infinite sequences

Question

I am trying to show the importance of lazy-sequences or lazy-evaluation to the non-FP programmers. I have written this implementation of prime-generation to show the concept:

(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)))

However, i get stack-overflow-exception if i give any bigger value to take.

The stack is :

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)

It seems that filter thunks are getting accumulated. But if do (doall (filter ... then i would not be able to process the infinite sequences i.e. (take 1000 (primes-gen (iterate inc 2))) would not work anymore.

What is the right way to do it ?

Small point: prefer `(if (seq sieve) ... )` to `(if-not (empty? sieve) ... )`. — Thumbnail, Mar 16 '15 at 17:58
@amalloy the marked question is not at all duplicate of this one: it deals with finite sequences while this one specifically asks about the *infinite* ones. Voting to reopen, hope you do too. — Will Ness, Jan 12 '17 at 19:40
@WillNess Agreed. It's the same basic problem, but the answers to the question I closed this as a duplicate of don't work when you need to work for an infinite output. Reference for future viewers: [Recursive function causing a stack overflow](http://stackoverflow.com/q/2946764/625403) is not a duplicate like I thought it was. — amalloy, Jan 12 '17 at 20:14

cgrand · Accepted Answer · 2015-03-23T10:21:28.103

3

Your analysis is spot on: you are nesting filters too much. You should modify prime-gen to take two args: the set of known primes and candidates. See my blog for some other ideas on implementing the Erathostenes' sieve.

Update: So you stack filters over filters and at some point the stack is too big when you want to fetch the new candidate.

You have to merge all the filters into a single (or a reasonable number of) pass. Here it's easy because filters are very homogeneous. So I replace the filters stack by a collection holding the known primes.

(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)))))))

edited Mar 23 '15 at 10:21

answered Mar 16 '15 at 09:32

cgrand

7,939
28
32

i am sorry i could not understand your algorithm. I am actually more interested in how to solve this thunk problem.. and not much on prime-number algorithm. Can you explain in essence how you solved this thunk problem in your code ? – Ashish Negi Mar 23 '15 at 07:22
In this specific case the algorithm change (to a true sieve impl) is the strategy to "de-thunk". See my update for a less drastic departure from your original code. – cgrand Mar 23 '15 at 10:22
Oh!!! so to look at it.. i find that if i do not use lazy-functions inside of `lazy-seq` then i would not have thunks problem. this is what happens when we use `(doall` unlazy the lazy.. but you showed that we can really get the best of both working on infinite seq and no-thunks with better understanding of problem and language.. thanks.. – Ashish Negi Mar 23 '15 at 13:33

score 0 · Answer 2 · answered Mar 16 '15 at 09:33

One of the possible solutions would be moving generator function inside lazy seq. For example (taken from here):

(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)))))

lazy-seq and stack overflow for infinite sequences

2 Answers2

Linked