<div dir="ltr">Silent Leaf, Akash,<div><br></div><div>Thanks for your inputs. I think my issue got sorted out. As Akash pointed out, the issue lies with the truncation condition never being met for some cases. I got this finally working using 'takeWhile'. The recursion is as elegant now:</div><div><br></div><div><div>primesBelowN :: Integer -> [Integer]</div><div>primesBelowN n = 2:3:filter f [6*k+i | k <- [1..(n-1)`div`6], i <- [-1, 1]]</div><div> where f x = foldr g True xs</div><div> where g t ac = (x `rem` t /= 0) && ac</div><div> xs = takeWhile (<= squareRoot x) $ primesBelowN n</div></div><div><br></div><div>Since squareRoot x will never be more than x, the recursion has no opportunity to overflow to infinity.</div><div><br></div><div>Thanks for your inputs!</div><div><br></div><div>Having said all of this, I now realize that this is not really the Sieve of Eratosthenes, but an optimized trial division method. Thanks to this, now I know something more about list comprehension and its pitfalls. And some things about optimization in haskell.</div><div><br></div><div>Thanks again for your time and effort.</div><div><br></div><div>Dushyant</div></div><br><div class="gmail_quote"><div dir="ltr">On Thu, May 5, 2016 at 11:41 PM Silent Leaf <<a href="mailto:silent.leaf0@gmail.com">silent.leaf0@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div>Implicitly, primesBelow shouldn't ever in fact call itself, not as it is articulated here **at the very least**, not without wasting a lot of calculus.<br></div><br>As it is, and maybe no matter what (i'm not sure, don't have the knowledge to certify that), when primesBelow checks if a value "v" is prime or not, well no matter what it'll already have calculated and stored all primes below this value n (this, according to how primesBelow is articulated, aka filtering of Naturals bottom-top).<br><br>Thus, if for each potential element "v" of the result (in my version, "list") of primesBelow, you call once again primesBelow, asking it to generate again all primes below sqrt(v), you'll do nothing more than doing again what you already did, because all those previous primes have already been generated, stored away, and especially very accessible, in the list-result in-construction of the **current** call to primesBelow, so if you don't use it but call again primesBelow to get a copy of what you already have, you'll multiply immensely the work without any gain.<br></div><div>That's why I named the very result of primesBelow, to get a way to use "list" (the previously generated items of the future result-list) in "checker".<br></div></div><div class="gmail_extra"><br><div class="gmail_quote">2016-05-05 15:44 GMT+02:00 Dushyant Juneja <span dir="ltr"><<a href="mailto:juneja.dushyant@gmail.com" target="_blank">juneja.dushyant@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi Akash,<div><br></div><div>Thanks for the response. A very simple and lucid explanation. Looks interesting.</div><div><br></div><div>So, here's the big picture now, for which I need this. I intend to implement a lookalike Sieve of Eratosthenes algorithm in haskell. For this, I intend to use the earlier function recursively, as follows:</div><div><br></div><div><div><div>primesBelowN :: Integer -> [Integer]</div><div>primesBelowN n = 2:3:filter f [6*k+i | k <- [1..(n-1)`div`6], i <- [-1, 1]]</div><div> where f x = foldr g True xs</div><div> where g t ac = (x `rem` t /= 0) && ac</div><div> xs = [ m | m <- primesBelowN n, m <= <span style="line-height:1.5">(truncate (sqrt (fromInteger x)))</span><span style="line-height:1.5">]</span></div></div></div><div><br></div><div>Of course, I could do something like this:</div><div><br></div><div><div><div>primesBelowN :: Integer -> [Integer]</div><div>primesBelowN n = 2:3:filter f [6*k+i | k <- [1..(n-1)`div`6], i <- [-1, 1]]</div><div> where f x = foldr g True xs</div><div> where g t ac = (x `rem` t /= 0) && ac</div><div> xs = [ m | m <- primesBelowN <span style="line-height:1.5">(truncate (sqrt (fromInteger x)))</span><span style="line-height:1.5">]</span></div></div></div><div><span style="line-height:1.5"><br></span></div><div><span style="line-height:1.5">However, this calls primesBelowN function with a new argument everytime. I suppose that is not optimal (correct me if I am wrong).</span></div><div><span style="line-height:1.5"><br></span></div><div><span style="line-height:1.5">Point number 2: both fail. Grrh.</span></div><div><span style="line-height:1.5"><br></span></div><div><span style="line-height:1.5">Any ideas how I could go recursive with this function?</span></div><div><span style="line-height:1.5"><br></span></div><div><span style="line-height:1.5">Dushyant</span></div><div><span style="line-height:1.5"><br></span></div></div><br><div class="gmail_quote"><div dir="ltr">On Thu, May 5, 2016 at 6:31 PM akash g <<a href="mailto:akaberto@gmail.com" target="_blank">akaberto@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div><div><div>Hi Dushyant,<br><br></div>The problem most likely is <br></div>[m | m <- [5,7..], m <= (truncate (sqrt (fromInteger x)))]<br><br></div> This is because, the filter condition (the last part) does a very simple thing: It filters out any element that does not fulfil the criteria. You are operating on a list that is monotonically increasing. However, the filter isn't aware of this property. Hence, this list comprehension never ends because it doesn't know that once the condition fails, it will always fail.<br><br></div><div>Thus, the solution would be to generate a finite set (or take a part of the infinite set using takeWhile or something like that), instead of using an infinite one.<br></div><div><br></div>Regards,<br></div>G Akash.<br></div><div class="gmail_extra"><br><div class="gmail_quote"></div></div><div class="gmail_extra"><div class="gmail_quote">On Thu, May 5, 2016 at 6:13 PM, Dushyant Juneja <span dir="ltr"><<a href="mailto:juneja.dushyant@gmail.com" target="_blank">juneja.dushyant@gmail.com</a>></span> wrote:<br></div></div><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi,<div><br></div><div>I seem to be landing into infinite recursion when using higher order functions with list comprehension. Take this for an example. The following works well, and gives answers for numbers like 2000000 as well:</div><div><br></div><div><div>primesBelowN :: Integer -> [Integer]</div><div>primesBelowN n = 2:3:filter f [6*k+i | k <- [1..(n-1)`div`6], i <- [-1, 1]]</div><div> where f x = foldr g True xs</div><div> where g t ac = (x `rem` t /= 0) && ac</div><div> xs = [5, 7..(truncate (sqrt (fromInteger x)))]</div></div><div><br></div><div><br></div><div>However, the following never returns anything for the same number, probably due to some kind of loop malfunction:</div><div><br></div><div><div>primesBelowN :: Integer -> [Integer]</div><div>primesBelowN n = 2:3:filter f [6*k+i | k <- [1..(n-1)`div`6], i <- [-1, 1]]</div><div> where f x = foldr g True xs</div><div> where g t ac = (x `rem` t /= 0) && ac</div><div> xs = [ m | m <- [5, 7, ..], m <= <span style="line-height:1.5">(truncate (sqrt (fromInteger x)))</span><span style="line-height:1.5">]</span></div></div><div><br></div><div>Any ideas what might be going wrong?</div><div><br></div><div>Thanks in advance!</div><span><font color="#888888"><div><br></div><div>DJ</div></font></span></div>
<br></blockquote></div></div><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
<br></blockquote></div><br></div>
_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
</blockquote></div>
<br>_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
<br></blockquote></div><br></div>
_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
</blockquote></div>