Hi,
On Jan 26, 3:17 pm, Nebojsa Stricevic <nebojsa.strice...@gmail.com>
wrote:
> I'm new to Clojure and working my way through Project Euler problems
> for learning. I wrote function for calculating prime number below some
> integer value max. But it doesn't work for large numbers, causing
> StackOverflowError.
>
> (defn primes-below
> "calculates all primes bellow max"
> [max]
> (loop [numbers (range 2 max) primes []]
> (if (empty? numbers)
> primes
> (let [p (first numbers)
> numbers (filter #(pos? (rem % p)) numbers)
> primes (cons p primes)]
> (recur numbers primes)))))
>
> (primes-below 2000000)
>
> I guess problem is not with loop-recur, or am I wrong?
The problem is lazyness of the filter call. You don't really get a
filtered list of numbers but some promise that you will get it, when
you require it. So you are basically piling a filter on a filter on a
filter .... When you know call first, the computations to hold the
promise are started causing an overflow due to the deep nesting.
One way to solve this problem is to use doall around the filter call.
This will remove the laziness issue, but it will also traverse the
numbers list several times.
Here is a different approach to this problem, which does not have this
problem. (Also note: this style of loop is a good candidate for
reduce)
(defn primes-below
[max]
(reduce (fn [primes x]
(if (some #(zero? (rem x %)) primes)
primes
(conj primes x)))
[] (range 2 max)))
Hope this helps.
Sincerely
Meikel
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
