Re: [Haskell-beginners] Infinite recursion in list comprehension

5 May 2016

      Hi Akash,

Thanks for the response. A very simple and lucid explanation. Looks
interesting.

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:

primesBelowN :: Integer -> [Integer]
primesBelowN n = 2:3:filter f [6*k+i | k <- [1..(n-1)`div`6], i <- [-1, 1]]
                     where f x = foldr g True xs
                                 where g t ac = (x `rem` t /= 0) && ac
                                       xs = [ m | m <- primesBelowN n,
m <= (truncate
(sqrt (fromInteger x)))]

Of course, I could do something like this:

primesBelowN :: Integer -> [Integer]
primesBelowN n = 2:3:filter f [6*k+i | k <- [1..(n-1)`div`6], i <- [-1, 1]]
                     where f x = foldr g True xs
                                 where g t ac = (x `rem` t /= 0) && ac
                                       xs = [ m | m <- primesBelowN (truncate
(sqrt (fromInteger x)))]

However, this calls primesBelowN function with a new argument everytime. I
suppose that is not optimal (correct me if I am wrong).

Point number 2: both fail. Grrh.

Any ideas how I could go recursive with this function?

Dushyant

On Thu, May 5, 2016 at 6:31 PM akash g  wrote:
...
Hi Dushyant,
The problem most likely is
[m | m <- [5,7..], m <= (truncate (sqrt (fromInteger x)))]
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.
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.
Regards,
G Akash.
On Thu, May 5, 2016 at 6:13 PM, Dushyant Juneja 
...
wrote:
...
Hi,
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:
primesBelowN :: Integer -> [Integer]
primesBelowN n = 2:3:filter f [6*k+i | k <- [1..(n-1)`div`6], i <- [-1,
1]]
                     where f x = foldr g True xs
                                 where g t ac = (x `rem` t /= 0) && ac
                                       xs = [5, 7..(truncate (sqrt
(fromInteger x)))]
However, the following never returns anything for the same number,
probably due to some kind of loop malfunction:
primesBelowN :: Integer -> [Integer]
primesBelowN n = 2:3:filter f [6*k+i | k <- [1..(n-1)`div`6], i <- [-1,
1]]
                     where f x = foldr g True xs
                                 where g t ac = (x `rem` t /= 0) && ac
                                       xs = [ m | m <- [5, 7, ..], m <= (truncate
(sqrt (fromInteger x)))]
Any ideas what might be going wrong?
Thanks in advance!
DJ
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners