Clojure: Avoiding stack overflow in Sieve of Erathosthene?
Posted
by nixx
on Stack Overflow
See other posts from Stack Overflow
or by nixx
Published on 2010-06-07T18:34:07Z
Indexed on
2010/06/07
19:22 UTC
Read the original article
Hit count: 297
Here's my implementation of Sieve of Erathosthene in Clojure (based on SICP lesson on streams):
(defn nats-from [n]
(iterate inc n))
(defn divide? [p q]
(zero? (rem q p)))
(defn sieve [stream]
(lazy-seq (cons (first stream)
(sieve (remove #(divide? (first stream) %)
(rest stream))))))
(def primes (sieve (nats-from 2)))
Now, it's all OK when i take first 100 primes:
(take 100 primes)
But, if i try to take first 1000 primes, program breaks because of stack overflow. I'm wondering if is it possible to change somehow function sieve to become tail-recursive and, still, to preserve "streamnes" of algorithm?
Any help???
© Stack Overflow or respective owner