Beginner’s questions about heap and garbage in clojure

I have a question about clojure:

(defn getAllPrimes [lim] 
  (defn getPrimes [primes numlist]
    (if (not-empty numlist) ;base case;
    (recur (cons (first numlist) primes) ;put the prime on to the prime list 
           (filter
        (fn [x] (not (div? x (first numlist)))) ;remove the prime and all its multiples from the numlist
        (rest numlist)))
      primes)); return the primes
  (getPrimes () (range 2 lim))) ;call the recursive function with and empty prime list to be filled up and a full numlist to be emptied

When I call, my heap space keeps running out

(apply + (getAllPrimes 2000000))

, but I didn't run out of space

(apply + (filter even? (range 2000000)))

So I don't think I can understand how to collect garbage when calling recur and actually using the O (n * n) heap or something

Solution

I believe the problem is that each time you repeat, you will create a new delay sequence, pointing to the last one, so after several iterations, you hold a SEQ, which contains a SEQ header, which contains a SEQ header Master the head of a SEQ All the intermediate sequences fill your heap

Although it's worth writing a main sieve, if you want the answer, clojure does include a prime sequence in its standard library: clojure contrib. lazy-seqs / primes. The standard solution to this particular Euler problem is a single thread

As a style point, internal definition is not a good idea The actual effect is the same as when defn is at the top level, but if I am not mistaken, VAR will be reassigned every time getallprimes is called, and it is strongly recommended not to redefine variables at run time Since the code only defines a VaR, getprimes is still visible as getallprimes In this case, getprimes can be easily rewritten as a loop / repetition without internal functions, anonymity or naming This doesn't help with your lazy SEQS problem, but it does make the code more standard:

(defn getAllPrimes [lim]
  (loop [primes ()
         numlist (range 2 lim)]
    (if (not-empty numlist)
      (recur (cons (first numlist) primes)
             (filter (fn [x] (not (div? x (first numlist))))
                     (rest numlist)))
      primes)))

I will also avoid using camelCase The clojure standard name for this function will be get all primes

However, back to the actual problem, the least you can do is force each SEQ at each iteration, that is, wrap your filter call in doall I've tried this. Although it still runs slowly, it will at least finish running without exhausting the heap:

(defn get-all-primes [lim]
  (loop [primes ()
         numlist (range 2 lim)]
    (if (not-empty numlist)
      (recur (cons (first numlist) primes)
             (doall (filter #(not (div? % (first numlist)))
                            (rest numlist))))
      primes)))