I have this implementation of the sieve of Eratosthenes in Clojure:
(defn sieve [n]
(loop [last-tried 2 sift (range 2 (inc n))]
(if
(or (nil? last-tried) (> last-tried n))
sift
(let [filtered (filter #(or (= % last-tried) (< 0 (rem % last-tried))) sift)]
(let [next-to-try (first (filter #(> % last-tried) filtered))]
(recur next-to-try filtered))))))
For larger n
(like 20000) it ends with stack overflow. Why doesn't tail call elimination work here? How to fix it?
Problem: filter
does lazy evaluation, so each new level of filtering hangs around on the call stack.
Fix: Change (filter ...)
to (doall (filter ...))
.
See the explanation here.
If you look at the backtrace
(try
(sieve 200000)
(catch java.lang.StackOverflowError e
(.printStackTrace e)))
it looks like this:
...
at clojure.lang.LazySeq.sval(LazySeq.java:42)
at clojure.lang.LazySeq.seq(LazySeq.java:56)
at clojure.lang.RT.seq(RT.java:440)
at clojure.core$seq__4176.invoke(core.clj:103)
at clojure.core$filter__5033$fn__5035.invoke(core.clj:1751)
at clojure.lang.LazySeq.sval(LazySeq.java:42)
at clojure.lang.LazySeq.seq(LazySeq.java:56)
...
It's too many filters that's causing the overflow, not the loop.
Unfortunately, I don't see an obvious solution for this.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With