CODEWITHSUNDEEP
haskell
rem
rem

Reputation: 893

haskell list comprehension optimization

I have a piece of code written for project euler: 

primes :: [Integer]
primes = filter isPrime [2..]
    where isPrime n = not $ any (\x -> n `mod` x == 0) [2..n-1]

ans = max [x | x <- primes, 600851475143 `mod` x == 0]

Of course I didn't wait for it to terminate. But I'm wondering will it ever return? I guess it depends on whether haskell knows to stop at 600851475143?

Upvotes: 1

Views: 108

Answers (1)

Cubic
Cubic

Reputation: 15693

No, this will never return. Haskell has non-strict semantics, so a compliant implementation doesn't need to evaluate parts of an expression that are unused; However it is not a theorem prover. The runtime system does not attempt to prove that there can't be any larger number in your list. Instead, when your expression is evaluated max will have to look at every single item in your list to determine its maximum value. Which is going to be a problem, because per what I said above, your list can never be determined to be done (because the source list is infinite, there's always more elements that are potentially included in your list expression).

What you need here is takeWhile followed by filter before your max.

Also, I probably don't need to point this out but your primes method is incredibly inefficient and will take a really long time to generate numbers as high as you seem to need for this problem.

Upvotes: 3

Related Questions