[Haskell-beginners] Infinite recursion in list comprehension
Silent Leaf
silent.leaf0 at gmail.com
Fri May 6 15:35:45 UTC 2016
I don't think you have understood me. your recursive call will do a huge
amount of work several times uselessly.
for each x, *after* having checked [4..x-1] of your list comprehension for
primeness, every value of [4.. square(x)] would again be calculated by your
recursive call, instead of using the same result of the current call (what
i called "list" in my version of it), then for every of those values, the
recursive call would calculate *again* the exact same values, say, for
square(x), [4.. square(square(x))], etc until it reaches the beginning of
the list.
in other terms, everytime you call primeBelow inside itself, it'll create a
new scope, with a new identical result list (2:3: ...), and will try to
calculate **again** the first items until it reaches the square root of x,
a work which at the time this recursive call is made, is necessarily
**already** done!
think about it: this x is the one in the list comprehension that is
currently being processed to know if it is prime or not. it means every n <
x has already been processed inside the result-in-construction ("list" in
my example) of your **current** call to (primeBelow n).
this expression:
primeBelow n = list where list = ...
implies that (primeBelow n) precisely is identical to "list" (lazily
speaking), so if you use the value "list" instead of a new call, you'll get
necessarily the same values under square(x), except they won't have to be
calculated again
the only other scenario of course is endless recursive call, but you
mentioned it yourself, which makes me think implicitly you know what i'm
trying to explain, since you said yourself:
"Since squareRoot x will never be more than x, the recursion has no
opportunity to overflow to infinity."
you knkow that in the recursive call to, basically, (primeBelow square(x)),
x itself would never be reached **because** (square x) is being checked
**before** x is ever reached, which implies that, in the **current** main
call to primeBelow, since we do are checking (x) (and are in need of the
first primes under square x), then all primes under square(x) will
**already** have been calculated *before**, are already known, in this very
call, in a value you have to name, and which i named "list".
2016-05-06 9:48 GMT+02:00 Dushyant Juneja <juneja.dushyant at gmail.com>:
> Silent Leaf, Akash,
>
> 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:
>
> 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 = takeWhile (<= squareRoot x) $
> primesBelowN n
>
> Since squareRoot x will never be more than x, the recursion has no
> opportunity to overflow to infinity.
>
> Thanks for your inputs!
>
> 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.
>
> Thanks again for your time and effort.
>
> Dushyant
>
> On Thu, May 5, 2016 at 11:41 PM Silent Leaf <silent.leaf0 at gmail.com>
> wrote:
>
>> 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.
>>
>> 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).
>>
>> 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.
>> 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".
>>
>> 2016-05-05 15:44 GMT+02:00 Dushyant Juneja <juneja.dushyant at gmail.com>:
>>
>>> 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
>>>>
>>>
>>> _______________________________________________
>>> 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
>>
>
> _______________________________________________
> 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/20160506/b2a0d31d/attachment.html>
More information about the Beginners
mailing list