Re: Lazy Sequence Results in Stack Overflow

[Yoshinori Kohyama]

Hi, Charles and all.

Here is my definition of prime numbers:
https://gist.github.com/kohyama/8e599b2e765ad4256f32

HTH.

Yoshinori Kohyama

-- 
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
--- 
You received this message because you are subscribed to the Google Groups 
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: Lazy Sequence Results in Stack Overflow

[Gary Verhaegen]

Primes are hard, because you essentially need to track all previous primes.

Here's one way to think about what you're doing here. First, you
create a lazy sequence of infinite numbers from 3 and up. This is done
by building a cons cell with 3 as the head and (iterate inc 4) as the
tail.

Then you filter that. From now on, every time you want the next
element, you'll have to run two functons: inc and odd?, plus some
extra processing for iterate and filter which both build up an
intermediate lazy seq.

Then you call sieve, which yet again builds up a new lazy seq that
accumulates more functions on its tail: assoc-nth, drop-while and a
recursive call to sieve. And assoc-nth itself still wraps a bunch of
other functions on your tail.

Now, the crucial part here is that most of these functions never go
away: for each new element that you compute, you add additional
function calls to each subsequent element. So that getting the 5th
element requires more additional elements than getting the 4th.

In some way, you have chosen to encode your list of previous primes as
accumulated functions. By the 500th prime, you have some much
accumulated functions that your call stack itself blows the stack.

With your implementation, on my computer, I only get about 300:

(defn num-primes
  [prime-seq]
  (try (doall prime-seq)
   (catch StackOverflowError e
 (count prime-seq

=> (time (num-primes primes))
"Elapsed time: 62385.706564 msecs"
325

A slightly more direct approach to the sieve (though arguably not a
true sieve), which has the same problem, in a more obvious way, would
be:

(defn filter-primes
  []
  (let [helper (fn helper [n]
 (lazy-seq (cons n (remove #(zero? (mod % n))
   (helper (inc n))]
(helper 2)))

=> (time (max-prime (filter-primes)))
"Elapsed time: 472.078328 msecs"
251

Two things to note:

* I've turned the sequence into a defn instead of a def. This makes it
possible to not hold onto the head. Since we get a stack overflow
around 300 integers here, this is no biggie, but it's a good practice
when defining potentially very long lazy seqs.
* It should be much more clear here that each prime is adding a call
to remove: whereas the 2 gets returned directly, the 3 has to go
through a mod 2 operation, then a remove function has to check that it
returned false. Similarly, the 5 will, in this very naive
implementation, need to check that it is not divisible by either 2, 3,
or 4, so we now have a "stack" of three remove functions to go
through.

A closer implementation to yours would be:

(defn filter-primes2
  []
  (let [sieve (fn [ls]
(let [p (first ls)]
  (lazy-seq
(cons p (remove #(zero? (mod % p)) ls)]
(sieve (iterate inc 2

=> (time (num-primes (filter-primes2)))
"Elapsed time: 59021.93554 msecs"
325

However, storing "primes found so far" into a stack of functions is
not very efficient (in either memory or computation), and the sieve
only really shines when it's used on vectors of known length (because
then there's no division), not on lazy seqs of potentially infinite
length. Here's an attempt to combine the advantages of the sieve with
lazy seqs:

(defn array-sieve
  []
  (let [sieve (fn [n]
(let [a (long-array n)]
  (loop [idx 0]
(when (< idx n)
  (aset-long a idx (+ 2 idx))
  (recur (inc idx
  (loop [idx 0]
(when (and (< idx n)
   (not= 0 (aget a idx)))
  (let [v (aget a idx)]
(loop [idx2 (+ idx v)]
  (when (< idx2 n)
(aset-long a idx2 0)
(recur (+ v idx2))
(when (< idx n)
  (recur (inc idx
  (vec (remove zero? a
generator (fn [[prev-idx known-primes prev-prime]]
(let [next-idx (inc prev-idx)
  known-primes (if (< next-idx (count known-primes))
 known-primes
 (loop [n (* 2 next-idx)]
   (let [k (sieve n)]
 (if (> (count k) next-idx)
   k

(recur (* 2 n))
  next-prime (get known-primes next-idx)]
  [next-idx known-primes next-prime]))]
(->> [0 [2] 2]
 (iterate generator)
 (map last

=> (time (nth (array-sieve) (dec 10)))
"Elapsed time: 13454.668724 msecs"
1299709

(You can check e.g. here that this is correct:
https://primes.utm.edu/nthprime/index.php#nth; the dec is there
because this website counts from 1, and nth from 0)

This is of course much more complex, but it's also much 

Re: Lazy Sequence Results in Stack Overflow

[William la Forge]

Why not turn this problem on its head? Have a vector of lists of prime 
factors for each i. March through this vector and for each prime factor in 
the current list, add that prime factor p to list i + p. And if i has no 
prime factors, then it is a prime itself and add it to the list at 2 * i.

So the only test for prime is if i has no prime factors as determined by 
propagating the prime factors forward, not through a mod function.

On Wednesday, September 23, 2015 at 8:14:39 PM UTC-4, Charles Reese wrote:
>
> I want to compute a lazy sequence of primes.
>
> Here is the interface:
>
> user=> (take 10 primes)
> (2 3 5 7 11 13 17 19 23 29)
>
> So far, so good.
>
> However, when I take 500 primes, this results in a stack overflow.
>
>   core.clj:  133  clojure.core/seq
>   core.clj: 2595  clojure.core/filter/fn
>   LazySeq.java:   40  clojure.lang.LazySeq/sval
>   LazySeq.java:   49  clojure.lang.LazySeq/seq
>RT.java:  484  clojure.lang.RT/seq
>   core.clj:  133  clojure.core/seq
>   core.clj: 2626  clojure.core/take/fn
>   LazySeq.java:   40  clojure.lang.LazySeq/sval
>   LazySeq.java:   49  clojure.lang.LazySeq/seq
>  Cons.java:   39  clojure.lang.Cons/next
>   LazySeq.java:   81  clojure.lang.LazySeq/next
>RT.java:  598  clojure.lang.RT/next
>   core.clj:   64  clojure.core/next
>   core.clj: 2856  clojure.core/dorun
>   core.clj: 2871  clojure.core/doall
>   core.clj: 2910  clojure.core/partition/fn
>   LazySeq.java:   40  clojure.lang.LazySeq/sval
>   LazySeq.java:   49  clojure.lang.LazySeq/seq
>RT.java:  484  clojure.lang.RT/seq
>   core.clj:  133  clojure.core/seq
>   core.clj: 2551  clojure.core/map/fn
>   LazySeq.java:   40  clojure.lang.LazySeq/sval
>   LazySeq.java:   49  clojure.lang.LazySeq/seq
>RT.java:  484  clojure.lang.RT/seq
>   core.clj:  133  clojure.core/seq
>   core.clj: 3973  clojure.core/interleave/fn
>   LazySeq.java:   40  clojure.lang.LazySeq/sval
>   
> I'm wondering what is the problem here and, more generally, when working 
> with lazy sequences, how should I approach this class of error?
>
> Here is the code.
>
> (defn assoc-nth
>   "Returns a lazy seq of coll, replacing every nth element by val
>
>   Ex:
>   user=> (assoc-nth [3 4 5 6 7 8 9 10] 2 nil)
>   (3 nil 5 nil 7 nil 9 nil)
>   "
>   [coll n val]
>   (apply concat
>  (interleave
>   (map #(take (dec n) %) (partition n coll)) (repeat [val]
>
> (defn sieve
>   "Returns a lazy seq of primes by Eratosthenes' method
>
>   Ex:
>   user=> (take 4 (sieve (iterate inc 2)))
>   (2 3 5 7)
>
>   user=> (take 10 (sieve (iterate inc 2)))
>   (2 3 5 7 11 13 17 19 23 29)
>   "
>   [s]
>   (lazy-seq
>(if (seq s)
>  (cons (first s) (sieve
>   (drop-while nil? (assoc-nth (rest s) (first s) 
> nil
>  [])))
>
> (def primes
>   "Returns a lazy seq of primes
>
>   Ex:
>   user=> (take 10 primes)
>   (2 3 5 7 11 13 17 19 23 29)
>   "
>   (concat [2] (sieve (filter odd? (iterate inc 3)
>

-- 
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
--- 
You received this message because you are subscribed to the Google Groups 
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: Lazy Sequence Results in Stack Overflow

[Colin Yates]

This might help:
http://stuartsierra.com/2015/08/25/clojure-donts-lazy-effects
On 24 Sep 2015 01:14, "Charles Reese"  wrote:

> I want to compute a lazy sequence of primes.
>
> Here is the interface:
>
> user=> (take 10 primes)
> (2 3 5 7 11 13 17 19 23 29)
>
> So far, so good.
>
> However, when I take 500 primes, this results in a stack overflow.
>
>   core.clj:  133  clojure.core/seq
>   core.clj: 2595  clojure.core/filter/fn
>   LazySeq.java:   40  clojure.lang.LazySeq/sval
>   LazySeq.java:   49  clojure.lang.LazySeq/seq
>RT.java:  484  clojure.lang.RT/seq
>   core.clj:  133  clojure.core/seq
>   core.clj: 2626  clojure.core/take/fn
>   LazySeq.java:   40  clojure.lang.LazySeq/sval
>   LazySeq.java:   49  clojure.lang.LazySeq/seq
>  Cons.java:   39  clojure.lang.Cons/next
>   LazySeq.java:   81  clojure.lang.LazySeq/next
>RT.java:  598  clojure.lang.RT/next
>   core.clj:   64  clojure.core/next
>   core.clj: 2856  clojure.core/dorun
>   core.clj: 2871  clojure.core/doall
>   core.clj: 2910  clojure.core/partition/fn
>   LazySeq.java:   40  clojure.lang.LazySeq/sval
>   LazySeq.java:   49  clojure.lang.LazySeq/seq
>RT.java:  484  clojure.lang.RT/seq
>   core.clj:  133  clojure.core/seq
>   core.clj: 2551  clojure.core/map/fn
>   LazySeq.java:   40  clojure.lang.LazySeq/sval
>   LazySeq.java:   49  clojure.lang.LazySeq/seq
>RT.java:  484  clojure.lang.RT/seq
>   core.clj:  133  clojure.core/seq
>   core.clj: 3973  clojure.core/interleave/fn
>   LazySeq.java:   40  clojure.lang.LazySeq/sval
>
> I'm wondering what is the problem here and, more generally, when working
> with lazy sequences, how should I approach this class of error?
>
> Here is the code.
>
> (defn assoc-nth
>   "Returns a lazy seq of coll, replacing every nth element by val
>
>   Ex:
>   user=> (assoc-nth [3 4 5 6 7 8 9 10] 2 nil)
>   (3 nil 5 nil 7 nil 9 nil)
>   "
>   [coll n val]
>   (apply concat
>  (interleave
>   (map #(take (dec n) %) (partition n coll)) (repeat [val]
>
> (defn sieve
>   "Returns a lazy seq of primes by Eratosthenes' method
>
>   Ex:
>   user=> (take 4 (sieve (iterate inc 2)))
>   (2 3 5 7)
>
>   user=> (take 10 (sieve (iterate inc 2)))
>   (2 3 5 7 11 13 17 19 23 29)
>   "
>   [s]
>   (lazy-seq
>(if (seq s)
>  (cons (first s) (sieve
>   (drop-while nil? (assoc-nth (rest s) (first s)
> nil
>  [])))
>
> (def primes
>   "Returns a lazy seq of primes
>
>   Ex:
>   user=> (take 10 primes)
>   (2 3 5 7 11 13 17 19 23 29)
>   "
>   (concat [2] (sieve (filter odd? (iterate inc 3)
>
> --
> 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
> ---
> You received this message because you are subscribed to the Google Groups
> "Clojure" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to clojure+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>

-- 
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
--- 
You received this message because you are subscribed to the Google Groups 
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.