StackOverflow when using Iterate in Clojure

Question

I'm trying to write a function in Clojure that finds the first x prime numbers. I wrote these functions:

(defn isprime? [n]
  (if (empty? (filter #(= 0 (mod n  %)) (range 2 n)))
    n
    0)
  )

(defn listprimes [nums]
    (if (first nums)
      (cons (isprime? (first nums)) (listprimes (rest nums)))
      [])
  )

The first one checks if a given number is prime or not, retruns it if it is or 0 id it isn't. The second gets a vector of numbers and activates the first function on each element. So, if my input to listprimes is [1 2 3 4 5 6] the output will be [1 2 3 0 5 0].

I was planning to use filter in the following way (for any x):

(take x (filter #(== 0 %) (listprimes(iterate inc 0)))

But I get a StackOverflow.. Any ideas what am I doing wrong?

Thanks!

Possible duplicate of [Recursive function causing a stack overflow](http://stackoverflow.com/questions/2946764/recursive-function-causing-a-stack-overflow) — bereal, Jan 31 '16 at 12:02
@bereal Not the same. This one fails for lack of laziness. The question you refer to fails for too much! — Thumbnail, Jan 31 '16 at 12:57

Thumbnail · Accepted Answer · 2016-01-31T17:06:28.693

3

listprimes is recursive and not lazy. Supplying it with the endless (iterate inc 0) is bound to overflow the stack, as each number nests another function call.

A lazy version of listprimes is ...

(defn listprimes [nums]
  (map isprime? nums))

Then, for example,

(take 20 (filter #(== 0 %) (listprimes (iterate inc 0))))

yields ...

;(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)

... not informative, but at least it terminates.

By the way,

isprime? does too much for its name. Peel it of the if form, leaving ...

(defn isprime? [n]
  (empty? (filter #(= 0 (mod n  %)) (range 2 n))))

For example,

(filter isprime? (range 2 20))
;(2 3 5 7 11 13 17 19)

Then the sort of result you want is better expressed thus:

(take 20 (remove isprime? (iterate inc 0)))
;(4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 26 27 28 30 32)

edited Jan 31 '16 at 17:06

answered Jan 31 '16 at 12:13

Thumbnail

13,293
2
29
37

Nope.. changes nothing. – shakedzy Jan 31 '16 at 12:15
@shakedzy Are you still trying to use your `listprimes` function? I believe Thumbnail is arguing that you shouldn't. Just use `filter` to get the list of primes. Doing so does change the behavior for me. You're version SOs on `(range 2 10000)`, while I have no issues with this version. And it does get rid of the recursion introduced is `listprimes`. If you're keen on having similar output of `listprimes`, you could redefine it to be: `(defn listprimes [nums] (map #(if (isprime? %) % 0) nums))` with this version of `isprime?`. – John Szakmeister Jan 31 '16 at 12:46

StackOverflow when using Iterate in Clojure

1 Answers1