programming haskell code: List of primes

Question

My task is to create a list of primes but only with the following information:

-The list has to be infinite
-I have to check up primes for n > 1
-If there is a variable 2 <= k < n-2, which divides n,then it is no prime, if it does not divide n, it is
-No function!

So I started writing a code like this:

primes = [n| n<-[2,3..],k<-[2,3..], if (k>=2) && (k<=(n-2))
            then if n `mod` k /= 0 then n else return ()
            else return ()  ]

But then appears the following error : "Couldn't match expected type ‘Bool’ with actual type"

It's because of the return (), but I don't know how to replace this return.

I hope for help.

Answer 1

Suppose you had a function:

isPrime :: Int -> Bool

which returned True for primes and False otherwise. Then you could define:

primes = [ n | n <- [2..], isPrime n ]

Using the function all, you could write isPrime like this:

isPrime n = all (\a -> mod n a /= 0) [2..n-1]

all f xs returns True if f applied to every member of xs is True. So n is prime if for all elements in [2..n-1], mod n a /= 0, i.e. a does not divide n.

Some more examples of the all function:

all even [2,4,10,12]       -- True
all (\x -> x > 0) [4,-5,6] -- False
all (\xs -> length xs > 0) [ [3], [4,5], [-4] ] -- True
all (\x -> x*x < 0) []     -- True

You can come up with the definition of all yourself by using the standard template for recursion on lists:

all f []     =  ...
all f (x:xs) =  ...

Answer 2

It should be 2 <= k <= n-2, otherwise 4 would be prime (with the <).

Without functions, it can be written as

[n | n<-[2..], []<-[[i | i<-[2..div n 2], rem n i==0]]]            -- or, even,
[n | n<-[2..], []<-[[j | i<-[2..n-2], j<-[i*i, i*i+i..n], j==n]]]  -- no `i` dividing `n`

The last code snippet is remarkable for being both a trial division and a sieve of Eratosthenes working through addition only (becoming the true sieve when the computational redundancies are discovered and eliminated through rearrangement and sharing of repeated calculations).

To your question specifically, return is out of place there. Test expressions in list comprehensions are simply expressions of type Bool. The False result means rejection of the currently generated value; True means acceptance — and therefore inclusion in the list of results.

Another thing is, repeated failed testing of repeatedly generated values means infinite looping, when for all values of k above n-2 (generated by k<-[2..] without end) your test (k>=2) && (k<=(n-2)) will always fail (and cause the next k being generated, and the next one, and the next...).

Instead of testing, we stop the generation after n-2 altogether, with [2..n-2], so the test condition always holds by construction — and were it would fail, those values of k are not generated at all, in the first place.