[Haskell-beginners] Infinite recursion in list comprehension
Dushyant Juneja
juneja.dushyant at gmail.com
Thu May 5 13:44:26 UTC 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 <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>
More information about the Beginners
mailing list