CODEWITHSUNDEEP
listhaskelllist-comprehension
iguider
iguider

Reputation: 721

how to use an incomplete list in its condition


I know.. The title isn't explaining well..
if you have a better title tell me in a comment..
I'm making a prime numbers generator for fun and learning purposes..
here's my code:

divisors x xs = [ y | y <- [1]++xs++[x], x `mod` y == 0]
isPrime x xs = divisors x xs == [1,x]
primeLst = [ x | x <- [2..], isPrime x primeLst]

As you can see.. I must use the already generated primes in a condition when generating a new one to reduce execution time..
and it's not working..
Is there a way of making it?

Upvotes: 0

Views: 127

Answers (3)

Sergey Bolgov
Sergey Bolgov

Reputation: 806

dividedBy a b = a `mod` b == 0
isPrime x = null $ filter (x `dividedBy`) $ takeWhile (\y -> y * y <= x) primeLst
primeLst = 2:(filter isPrime [3..])

or, more verbose:

primeLst = 2:(filter isPrime [3..])
  where
    isPrime x = null $ primeDivisors x
    primeDivisors x = filter (x `dividedBy`) $ potentialDivisors x
    potentialDivisors x = takeWhile (\y -> y * y <= x) primeLst
    a `dividedBy` b = a `mod` b == 0

Upvotes: 2

Boris
Boris

Reputation: 5176

Let us start by looking at the divisors function. It is sort of correct, with only two issues:

  1. What is the xs argument supposed to be? From the definition, it looks like it should be all the prime numbers below x - let's call these the candidate primes. So if x was 10, then the candidate primes should be [2,3,5,7]. However, this is not what the function gets as an argument. In your code, xs is the infinite list of primes.

  2. Technically, the divisors doesn't return all divisors. divisors 16 [2,3,5,7,11,13] wouldn't return 8, for instance. But this is a minor nitpick.

So if we can call divisors with the right list of primes, then we should be ok, and the isPrime function would also be fine.

The problem is getting the list of candidate primes. For clarity, I will give the code first, and then explain:

primeLst = 2 : [ x | x <- [3..], isPrime x (takeWhile (\p -> p*p <= x) primeLst)]

I have made two changes:

  1. I made sure that primeLst includes 2, by sticking it at the front.

  2. I restricted the candidate primes by taking numbers from the infinite list of primes until I reached a number that was higher than the square root of the number I was testing for primeness. In doing this i changed the definition of the candidate primes slightly, so for instance the candidates for 26 are [2,3,5] instead of [2,3,5,7,11,13,17,19,23]. But it still works.

Two questions for you to think about:

  1. Why does it still work with the new definition of candidate primes?

  2. Why doesn't the following line of code work, even though it seems it should give the original definition of the candidate primes?

:

primeLst = 2 : [ x | x <- [3..], isPrime x (takeWhile (\p -> p < x) primeLst)]

The last question is hard, so if you have questions, post them in the comments.

Upvotes: 2

Robert Tupelo-Schneck
Robert Tupelo-Schneck

Reputation: 10543

Calculating at least one element of primeLst requires calculating isPrime 2 primeLst which requires calculating at least two elements of divisors 2 primeLst which requires calculating at least two elements of [1]++primeLst++[2], which requires calculating at least one element of primeLst. Not gonna happen.

You might be able to make something work that uses [1]++(primesLessThan x)++[x], but I don't see a straightforward way to define (primesLessThan x) in terms of primeLst which avoids computational circularity.

Upvotes: 1

Related Questions