Re: Filtering lazy sequence on itself - Eratosthenes Sieve

[Sam Raker]

Clojure doesn't do TCO with recursive functions--you have to use 
`loop`/`recur`[1]. This is one of the (thankfully few) "gotchas" in 
Clojure, at least/especially for people coming from other functional 
languages (or so I assume--coming from Python, I hadn't heard that much 
about TCO in the first place). There's a pretty good chance whichever intro 
book you're working through will talk about this in a chapter or so :)


[1] http://clojure.org/functional_programming#Functional 
Programming--Recursive Looping


On Thursday, November 5, 2015 at 10:01:44 AM UTC-5, Matthew Ulrich wrote:
>
> Thanks, Sergio - this is a good way to construct the sieve.
>
> It took me a little while to convince myself that it's the same, but it's 
> definitely a good solution.
>
> In general, I guess it's not possible to generate an infinite sequence 
> that utilizes the tail-call optimization it makes sense as there is no 
> "tail".
>
> Have a good day,
>
> Matty
>
> On Wednesday, November 4, 2015 at 10:07:46 AM UTC-5, Sergio Rupena wrote:
>>
>> Hi
>>
>> You can try the following
>>
>> (defn dividers   [primes n]
>>   (take-while #(<= (* % %) n) primes))
>>
>> (defn prime? [primes n]
>>   (every? #(pos? (rem n %))
>>   (dividers primes n)))
>>
>> (defn range-peek [coll]
>>   (iterate inc (-> coll peek inc)))
>>
>> (defn sieve
>>   ([] (cons 2 (lazy-seq (sieve [2]
>>   ([primes]
>>(let [p (->> primes
>> range-peek
>> (filter (partial prime? primes))
>> first)]
>>  (cons p (lazy-seq (sieve (conj primes p)))
>>
>> (last (take 1 (sieve)))
>>
>> This version keeps the visited primes in a vector so it will grow in 
>> memory but won’t overflow otherwise.
>>
>> Sergio
>>
>> On 04 Nov 2015, at 15:44, Matthew Ulrich  wrote:
>>
>> All - 
>>
>> I'm trying to generate a lazy sequence of primes using Erastosthenes 
>> Sieve (from Abelson & Sussman) and am encountering some issues with lazy 
>> sequence.
>>
>> Here's what I have:
>> ---
>>
>> (defn divisible?
>>   [input numerator]
>>   (= 0 (mod input numerator)))
>>
>> (defn sieve
>>   [stream]
>>   (lazy-seq
>> (cons
>>   (first stream)
>>   (sieve (filter #(not (divisible? % (first stream))) (rest 
>> stream))
>>
>> (def primes (sieve (iterate inc 2)))
>>
>> ---
>>
>> This is fine now when I:
>>
>> => (take 5 (drop 1000 primes))
>> (7927 7933 7937 7949 7951)
>>
>>
>> But when I:
>>
>> => (take 5 (drop 4000 primes))
>> StackOverflowErrorclojure.lang.LazySeq.sval  (LazySeq.java:40)
>>
>>
>> --
>>
>> I understand how the StackOverflow occurs with the filter on the 
>> recursively generated sequence... however I can't think of a way to make 
>> this work..
>>
>> I'm pretty new to clojure so I'm not very familiar with all of the 
>> language features; is there some tool to help me realize this or should I 
>> just go about the implementation in a different way?
>>
>> Thanks - have a great morning!
>>
>> Matty
>>
>> -- 
>> You received this message because you are subscribed to the Google
>> Groups "Clojure" group.
>> To post to this group, send email to clo...@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+u...@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+u...@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.

Re: Filtering lazy sequence on itself - Eratosthenes Sieve

[Matthew Ulrich]

Thanks, Sergio - this is a good way to construct the sieve.

It took me a little while to convince myself that it's the same, but it's 
definitely a good solution.

In general, I guess it's not possible to generate an infinite sequence that 
utilizes the tail-call optimization it makes sense as there is no 
"tail".

Have a good day,

Matty

On Wednesday, November 4, 2015 at 10:07:46 AM UTC-5, Sergio Rupena wrote:
>
> Hi
>
> You can try the following
>
> (defn dividers   [primes n]
>   (take-while #(<= (* % %) n) primes))
>
> (defn prime? [primes n]
>   (every? #(pos? (rem n %))
>   (dividers primes n)))
>
> (defn range-peek [coll]
>   (iterate inc (-> coll peek inc)))
>
> (defn sieve
>   ([] (cons 2 (lazy-seq (sieve [2]
>   ([primes]
>(let [p (->> primes
> range-peek
> (filter (partial prime? primes))
> first)]
>  (cons p (lazy-seq (sieve (conj primes p)))
>
> (last (take 1 (sieve)))
>
> This version keeps the visited primes in a vector so it will grow in 
> memory but won’t overflow otherwise.
>
> Sergio
>
> On 04 Nov 2015, at 15:44, Matthew Ulrich  
> wrote:
>
> All - 
>
> I'm trying to generate a lazy sequence of primes using Erastosthenes Sieve 
> (from Abelson & Sussman) and am encountering some issues with lazy sequence.
>
> Here's what I have:
> ---
>
> (defn divisible?
>   [input numerator]
>   (= 0 (mod input numerator)))
>
> (defn sieve
>   [stream]
>   (lazy-seq
> (cons
>   (first stream)
>   (sieve (filter #(not (divisible? % (first stream))) (rest 
> stream))
>
> (def primes (sieve (iterate inc 2)))
>
> ---
>
> This is fine now when I:
>
> => (take 5 (drop 1000 primes))
> (7927 7933 7937 7949 7951)
>
>
> But when I:
>
> => (take 5 (drop 4000 primes))
> StackOverflowErrorclojure.lang.LazySeq.sval  (LazySeq.java:40)
>
>
> --
>
> I understand how the StackOverflow occurs with the filter on the 
> recursively generated sequence... however I can't think of a way to make 
> this work..
>
> I'm pretty new to clojure so I'm not very familiar with all of the 
> language features; is there some tool to help me realize this or should I 
> just go about the implementation in a different way?
>
> Thanks - have a great morning!
>
> Matty
>
> -- 
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@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+u...@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+u...@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.

Filtering lazy sequence on itself - Eratosthenes Sieve

[Matthew Ulrich]

All - 

I'm trying to generate a lazy sequence of primes using Erastosthenes Sieve 
(from Abelson & Sussman) and am encountering some issues with lazy sequence.

Here's what I have:
---

(defn divisible?
  [input numerator]
  (= 0 (mod input numerator)))

(defn sieve
  [stream]
  (lazy-seq
(cons
  (first stream)
  (sieve (filter #(not (divisible? % (first stream))) (rest stream))

(def primes (sieve (iterate inc 2)))

---

This is fine now when I:

=> (take 5 (drop 1000 primes))
(7927 7933 7937 7949 7951)


But when I:

=> (take 5 (drop 4000 primes))
StackOverflowErrorclojure.lang.LazySeq.sval  (LazySeq.java:40)


--

I understand how the StackOverflow occurs with the filter on the 
recursively generated sequence... however I can't think of a way to make 
this work..

I'm pretty new to clojure so I'm not very familiar with all of the language 
features; is there some tool to help me realize this or should I just go 
about the implementation in a different way?

Thanks - have a great morning!

Matty

-- 
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: Filtering lazy sequence on itself - Eratosthenes Sieve

[Sergio Rupena]

Hi

You can try the following

(defn dividers   [primes n]
  (take-while #(<= (* % %) n) primes))

(defn prime? [primes n]
  (every? #(pos? (rem n %))
  (dividers primes n)))

(defn range-peek [coll]
  (iterate inc (-> coll peek inc)))

(defn sieve
  ([] (cons 2 (lazy-seq (sieve [2]
  ([primes]
   (let [p (->> primes
range-peek
(filter (partial prime? primes))
first)]
 (cons p (lazy-seq (sieve (conj primes p)))

(last (take 1 (sieve)))

This version keeps the visited primes in a vector so it will grow in memory but 
won’t overflow otherwise.

Sergio

On 04 Nov 2015, at 15:44, Matthew Ulrich  wrote:

> All - 
> 
> I'm trying to generate a lazy sequence of primes using Erastosthenes Sieve 
> (from Abelson & Sussman) and am encountering some issues with lazy sequence.
> 
> Here's what I have:
> ---
> 
> (defn divisible?
>   [input numerator]
>   (= 0 (mod input numerator)))
> 
> (defn sieve
>   [stream]
>   (lazy-seq
> (cons
>   (first stream)
>   (sieve (filter #(not (divisible? % (first stream))) (rest stream))
> 
> (def primes (sieve (iterate inc 2)))
> 
> ---
> 
> This is fine now when I:
> 
> => (take 5 (drop 1000 primes))
> (7927 7933 7937 7949 7951)
> 
> 
> But when I:
> 
> => (take 5 (drop 4000 primes))
> StackOverflowErrorclojure.lang.LazySeq.sval  (LazySeq.java:40)
> 
> 
> --
> 
> I understand how the StackOverflow occurs with the filter on the recursively 
> generated sequence... however I can't think of a way to make this work..
> 
> I'm pretty new to clojure so I'm not very familiar with all of the language 
> features; is there some tool to help me realize this or should I just go 
> about the implementation in a different way?
> 
> Thanks - have a great morning!
> 
> Matty
> 
> -- 
> 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.