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 |
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 9,
k 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:
_______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners |
Free forum by Nabble | Edit this page |