[Haskell-beginners] Infinite recursion in list comprehension

[akash g]

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 <juneja.dushyant at gmail.com>
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 at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20160505/01a7fb1a/attachment.html>