[Haskell-beginners] 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 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 <
alexander at chenjia.nl> 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
> 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/20200115/16f0573e/attachment.html>