Prime numbers -- specific list comprehension explained

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Prime numbers -- specific list comprehension explained

Alexander Chen
Hi,

This could gives you for any given integer the list of prime numbers. source is from a stack overflow snippet.

helper function:
isqrt :: Integral a => a -> a
isqrt = floor . sqrt . fromIntegral

main function:
primes 1 = []
primes n = 2:[i | i <- [3,5..n], and [mod i k /= 0 | k <- primes (isqrt i)]]



my main unclarity is how I should interpret i and k in de mod part. At every step of the recursion.

example: primes 10.

it should generate [2,3,5,7,9] if you ignore the second part.

however, when I look at the second part

then first I need to do this primes (isqrt 10), which give primes 3. which gives met [2,3]
first question) I haven't reached base case in this situations so can i or can i not meaningfully evaluate mod i k /= 0?
Independent of that I now go deeper to reach base case.
So I go to primes (isqrt 3) which gives me primes 1 which is []. Now I hit the base case and need to definitely evaluate mod i k /= 0.
second question) but in this case what is i and what is k?

If I have it completely wrong, then please be patience. I appreciate the input!

best,




_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Prime numbers -- specific list comprehension explained

Ut Primum
Hi,

First I'll answer your second question:

but in this case what is i and what is k? 
(So the question is about  primes 3)

Think about the meaning of the expression primes 3, which is:
primes 3 = 2:[i | i <- [3,5..3], and [mod i k /= 0 | k <- primes (isqrt i)]]
               = 2:[i | i <- [3], and [mod i k /= 0 | k <- primes (isqrt i)]
So, in the list  [i | i <- [3], and [mod i k /= 0 | k <- primes (isqrt i)]]  i takes all values in the list [3] (i.e. it is only 3) and for each of them the condition 
[mod i k /= 0 | k <- primes (isqrt i)] 
must be checked. When i=3, it is  [mod 3 k /= 0 | k <- primes 1] [mod 3 k /= 0 | k <- []], so the condition is empty (it means you must check that mod 3 k is nonzero for every k in the empty list, so you don't need to check anything!).
So this is clearly primes 3 = 2:[3] = [2,3].
To understand better, if you had:
  [i | i <- [3,4,5,6], and [mod i k /= 0 | k <- []]] 
(this never occurs in the program, but just to understand what i and k are)
i would be respectively 3,4,5 and 6 and for each i, k would be nothing. So the list above is equal to [3,4,5,6].


Now maybe the meaning of this kind of expressions is mor clear, and you can see that what you imagined the function did is not completely correct:
primes 10 = 2:[i | i <- [3,5,7,9], and [mod i k /= 0 | k <- primes (isqrt i)]]  

So, i is not 10 (so you don't always take k in primes 3), since it varies among the values 3,5,7 and 9.
When i is 3, as I said before, k is in primes 1 = [], so there is no further condition to check, so 3 is in the list.
When i is 5, k is in primes (isqrt 5) = primes 2 = [2], so you have to check if mod 5 2 is nonzero, and it is, so 5 is in the list.
When i is 7, k is in primes  (isqrt 7) = primes 2 = [2], so you have to check if mod 7 2 is nonzero, and it is, so 7 is in the list.
When i is 9k is in primes  (isqrt 9) = primes 3 = [2,3], so you have to check if mod 9 2 is nonzero and mod 9 3 is nonzero, but this is false, so 9 is NOT in the list.

As for your first question (which is now about something that happens for i=9, not for i=10 which never happens, n=10, not i, so you never look at primes (isqrt 10), but the answer would be the same, there is no difference)
 I haven't reached base case in this situations so can i or can i not meaningfully evaluate mod i k /= 0? 

The answer is that of course you have to evaluate primes 3 before. So when the expression is reduced, first primes 3 is calculated (and as you said it gives [2,3]), and then mod i k /=0 can be evaluated because you know where both i and k vary.
 
I hope it is clear,
cheers,
Ut

Il giorno mer 15 gen 2020 alle ore 15:49 Alexander Chen <[hidden email]> ha scritto:
Hi,

This could gives you for any given integer the list of prime numbers. source is from a stack overflow snippet.

helper function:
isqrt :: Integral a => a -> a
isqrt = floor . sqrt . fromIntegral

main function:
primes 1 = []
primes n = 2:[i | i <- [3,5..n], and [mod i k /= 0 | k <- primes (isqrt i)]]



my main unclarity is how I should interpret i and k in de mod part. At every step of the recursion.

example: primes 10.

it should generate [2,3,5,7,9] if you ignore the second part.

however, when I look at the second part

then first I need to do this primes (isqrt 10), which give primes 3. which gives met [2,3]
first question) I haven't reached base case in this situations so can i or can i not meaningfully evaluate mod i k /= 0?
Independent of that I now go deeper to reach base case.
So I go to primes (isqrt 3) which gives me primes 1 which is []. Now I hit the base case and need to definitely evaluate mod i k /= 0.
second question) but in this case what is i and what is k?

If I have it completely wrong, then please be patience. I appreciate the input!

best,



_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners