Haskell Does Not Evaluate Lazily takeWhile

Question

isqrt :: Integer -> Integer
isqrt = floor . sqrt . fromIntegral

primes :: [Integer]
primes = sieve [2..] where
 sieve (p:ps) = p : sieve [x | x <- ps, x `mod` p > 0]

primeFactors :: Integer -> [Integer]
primeFactors n = takeWhile (< n) [x | x <- primes, n `mod` x == 0]

Here is my code. I think you guessed what I am trying to do: A list of prime factors of a given number using infinite list of prime numbers. But this code does not evaluate lazily.

When I use ghci and :l mycode.hs and enter primeFactors 24, the result is [2, 3 ( and the cursor constantly flashing there) there isn't a further Prelude> prompt. I think there is a problem there. What am I doing wrong?

Thanks.

Answer 1

takeWhile never terminates for composite arguments. If n is composite, it has no prime factors >= n, so takeWhile will just sit there.

Apply takeWhile to the primes list and then filter the result with n mod x, like this:

primeFactors n = [x | x <- takeWhile (<= n) primes, n `mod` x == 0]

(<= is used instead of < for maximum correctness, so that prime factors of a prime number would consist of that number).