Haskell list comprehension for finding primes

问题:

I'm trying to find all the primes less than some integer n as concisely as possible, using list comprehensions. I'm learning Haskell, and this is just an exercise. I'd like to write something like:

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

primes :: Integral a => a -> [a]  
primes n = [i | i <- [1,3..n], mod i k /= 0 | k <- primes (isqrt i)]

which of course doesn't work. Is there a way to have a list comprehension inside a list comprehension?

Here is the error I'm getting:

exercise-99-1.hs:138:39: Not in scope: `k'

exercise-99-1.hs:138:46:
    Illegal parallel list comprehension: use -XParallelListComp

exercise-99-1.hs:138:68: Not in scope: `i'

BUT - I wasn't really expecting the syntax to even be legit :-)

The intent was to translate as directly as possible: " primes n = the set of odd integers i less than n such that i is not divisible by any k, for all k in the set: primes (isqrt i)" - more or less. (I hope I got that right?)

Thanks!

回答1:

I made some progress with the following:

primes :: Integral a => a -> [a]  
primes 2 = [2]  
primes n = 2:[i | i <- [3,5..n], all (\k -> if (mod i k /= 0) then True else False) 
                                     (primes (isqrt i))]

Is there a shorter way to write the lambda predicate?

edit: Yes, there is, thanks to the remarks in the comments!

primes :: Integral a => a -> [a]  
primes 2 = [2]  
primes n = 2:[i | i <- [3,5..n], all ((/= 0) . mod i) (primes (isqrt i))]

回答2:

your code,

primes n = [i | i <- [1,3..n], mod i k /= 0 
              | k <- primes (isqrt i)]

is interpreted as parallel list comprehension; i.e. instead of combining the two generators in the usual nested fashion, they are combined in parallel:

primes n = [i | (i,k) <- zip [i | i <- [1,3..n], mod i k /= 0]
                                    -- not in scope: k ^
                             [k | k <- primes (isqrt i)] ]
                                  -- not in scope: i ^

Instead, to express what you intended, it can be written as

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

thus having a list comprehension inside a list comprehension - but as part of a guard, not generator. The function and :: [Bool] -> Bool makes this possible.

---

Incidentally, calling primes recursively for each new candidate i makes it run slow, with run times growing too fast, empirically:

 > length $ primes 10000     -- => 1229    (0.50 secs)

 > length $ primes 20000     -- => 2262    (1.40 secs)

 > logBase (2262/1229) (1.4/0.5)      -- => 1.6878      ~ n^1.69

 > length $ primes 40000     -- => 4203    (4.07 secs)

 > logBase (4203/2262) (4.07/1.4)     -- => 1.7225      ~ n^1.72

Optimal trial division usually runs at ~ n^1.4..1.45, list-based sieve of Eratosthenes at ~ n^1.2..1.25 and, if optimally implemented on mutable arrays, at ~ n^1.0..1.1 (with n the number of primes produced, not the upper limit).