CODEWITHSUNDEEP
haskelllist-comprehensionprimeslazy-evaluationprime-factoring
D. Jones
D. Jones

Reputation: 481

Haskell Does Not Evaluate Lazily takeWhile

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.

Upvotes: 5

Views: 338

Answers (3)

Ben
Ben

Reputation: 71400

Your problem isn't directly takeWhile, but rather the list comprehension.

[x | x <- primes, n `mod` x == 0]

For n = 24, we get 24 `mod` 2 == 0 and 24 `mod` 3 == 0, so the value of this list comprehension starts with 2 : 3 : .... But consider the ... part.

The list comprehension has to keep pulling values from primes and checking 24 `mod` x == 0. Since there are no more prime factors of 24 nothing will ever pass that test and get emitted as the third value of the list comprehension. But since there's always another prime to test, it will never stop and conclude that the remaining tail of the list is empty.

Because this is lazily evaluated, if you only ever ask for the first two elements of this list then you're fine. But if your program ever needs the third one (or even just to know whether or not there is a third element), then the list comprehension will just spin forever trying to come up with one.

takeWhile (< 24) keeps pulling elements from its argument until it finds one that is not < 24. 2 and 3 both pass that test, so takeWhile (< 24) does need to know what the third element of the list comprehension is.

But it's not really a problem with takeWhile; the problem is that you've written a list comprehension to find all of the prime factors (and nothing else), and then trying to use a filter on the results of that to cut off the infinite exploration of all the higher primes that can't possibly be factors. That doesn't really make sense if you stop to think about it; by definition anything that isn't a prime factor can't be an element of that list, so you can't filter out the non-factors larger than n from that list. Instead you need to filter the input to that list comprehension so that it doesn't try to explore an infinite space, as @n.m's answer shows.

Upvotes: 1

Gurkenglas
Gurkenglas

Reputation: 2317

Have an illustration of what happens:

http://sketchtoy.com/67338195

Upvotes: 1

n. m. could be an AI
n. m. could be an AI

Reputation: 119847

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).

Upvotes: 7

Related Questions