What kind of optimizations does Haskell do here?

Question

So, I'm admittedly a Haskell Newbie, but I so far like it a lot since I've been on a prime number splurge lately. (Which is what turned me on to it)

I've got this relatively basic script. It works exactly as it should, even if it's not as efficient as possible. That's not my question though. Here is my script:

import System.Environment


oddFactors p = [x | x<- [3,5..floor (sqrt (fromIntegral p))], p `mod` x == 0]
prime x = oddFactors (2^x -1) == []

main = do
    args <- getArgs
    print (prime (read (head args) :: Int))

Like I said, simple. oddFactors goes through odd numbers from 3 to sqrt(p) and adds it to a list if it was a factor of p.

primes calls oddFactors on 2^x -1 and checks if the resulting list is equal to the empty list.

The weird thing is, it appears to already be optimized. In the case of primes if I were to do, for example, 61, my program takes 49 seconds to run and returns True. If I do 60 or 62, though, it takes .005s to run and returns False. These are the correct return values, but I'm curious if it's optimized somehow since it knows it's only looking for a list matching [] and after finding one, it returns false, since the list will never be []

Long winded question, but I'm also willing to take any suggestions on my code so far. I picked Haskell up about two hours ago, so be nice :)

EDIT: I of course know I can use something better as a primality test, such as Miller-Rabin, but that's not the point ;)

This is almost an exact duplicate of this question: http://stackoverflow.com/questions/24263611/haskell-is-evaluating-much-faster-then-i-thought-it-would-no-complaints — Cirdec, Jun 23 '14 at 22:25
BTW, don't write `l == []`. It's the same as `null l`, which however doesn't require that the list's element type has an `Eq` instance. — leftaroundabout, Jun 23 '14 at 22:55

score 5 · Accepted Answer · edited May 23 '17 at 12:20

The test list == [] will evaluate list only as much as needed to check the emptiness of list. Technically, as much as needed to discover the outermost constructor of list (which could be : or []), bringing list to weak head normal form (WHNF).

For instance, (error "hello" : error "world") == [] will return False without evaluating the error expressions.

This results from expressions being lazily evaluated and the definition of (==) using pattern matching in the natural way:

[]     == []     = True
[]     == _      = False
_      == []     = False
(x:xs) == (y:ys) = x==y && xs==ys

By comparison, if the definition had been

[]     == []     = True
[]     == (y:ys) = []==ys && False
(x:xs) == []     = xs==[] && False
(x:xs) == (y:ys) = x==y && xs==ys

then list == [] would have forced the computation of the whole list before returning False (or, more precisely, the whole list spine).

bitmask · Answer 2 · 2014-06-23T22:37:59.837

Haskell lazily evaluates function calls. That means it first tries to figure out the == "call" when evaluating, say prime 60 it tries to find the odd factors of 1152921504606846975. When evaluating this, it will descend into the == definition, which for an empty list only tries to figure out if there is at least one element. So effectively it only evaluates if

1152921504606846975 `mod` 3 == 0

Since this is true, it doesn't even evaluate the rest of the list: It already knows 3:(stuff) == [] to be False, regardless of what (stuff) might evaluate to.

When you pass it 61, it tries to find the odd factors of 2305843009213693951, which is a prime, so it has to expand the hole list comprehension, in order to figure out that it is empty. That's why it takes so long.

What kind of optimizations does Haskell do here?

2 Answers2