[Haskell-beginners] Infinite recursion in list comprehension

[Dushyant Juneja]

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 <akaberto at gmail.com> 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 <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
>>
>>
> _______________________________________________
> 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/84f2c2b8/attachment.html>