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.

Witchery

Note that the list [x | x <- primes, 10 `mod` x == 0] is not [2,5], but something like 2:5:infiniteLoop, because after 5 infinitely many primes x will be tried since they might pass the test. Of course we know they won't, but the list comprehension does not know that. Then takeWhile gets stuck in the loop. – Wanettawanfried

@Wanettawanfried Yes, I am aware of that it will be an infinite list, thank you. But I thought that takeWhile would stop evaluating the infinite list when the predicate does not hold anymore. – Witchery

Nope. It is not an infinite list. On that takeWhile would have no problems. Try takeWhile (<=10) [1..] and takeWhile (<=10) (1:2:5:let f n = f (n+1) in f 3). Here [1..] is an infinite list, while 1:2:5:... is not -- it is a list with an undefined spine after its 3rd element. In an infinite list, take n list will always return, instead when the spine is undefined it will not. – Wanettawanfried

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

Distended

Your code worked well, thanks. But I am not sure I understood the takeWhile situation. Where does actually it stops? Or is it the list comprehension that causes the infinity? – Witchery

@D.Jones It's both. Consider: takeWhile p xs, if xs is finite than takeWhile p xs is finite too, however if xs is infinite than takeWhile p xs might be finite or infinite, depending on whether there exist a finite prefix of xs where p becomes false. In your case the list comprehension will yield a finite prefix where all elements make p true, and after that no more elements are generated however the list-comprehension keeps trying the primes forever. – Synoptic

It is important to distinguish between "finite" (a.k.a. terminating) lists and lists that only have a finite number of elements. E.g. 1:2:3:[] is finite (terminating) and 1:2:3:infiniteLoop is not though it only ever has 3 elements. So the list comprehension doesn't terminate, even though it only produces a finite number of elements; and takeWhile doesn't terminate, because the condition never becomes false and the list argument (the list comprehension) doesn't terminate. – Distended

Answer 2

Have an illustration of what happens:

http://sketchtoy.com/67338195

Marybethmaryellen

Answer 3

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.

Seto