Performance of "all" in haskell

Question

I got nearly no knowledge of haskell and tried to solve some Project Euler Problems. While solving Number 5 I wrote this solution (for 1..10)

--Check if n can be divided by 1..max
canDivAll :: Integer -> Integer -> Bool 
canDivAll max n = all (\x ->  n `mod` x == 0) [1..max]

main = print $ head $ filter (canDivAll 10) [1..]

Now I found out, that all is implemented like this:

all p            =  and . map p

Doesn't this mean, the condition is checked for every element? Wouldn't it be much faster to break upon the first False-Result of the condition? This would make the execution of the code above faster.

Thanks

Answer 1

You're assuming that and is not short-circuiting. and will stop execution on the first false result it sees, so it is "fast" as one might expect.

Answer 2

and itself is short-circuited and since both map and all evaluation is lazy, you will only get as many elements as needed - not more.

You can verify that with a GHCi session:

Prelude Debug.Trace> and [(trace "first" True), (trace "second" True)]
first
second
True
Prelude Debug.Trace> and [(trace "first" False), (trace "second" False)]
first
False

Answer 3

This is a good program for the fusion optimization, as all your loops are expressed as fusible combinators. Thus you can write it using, e.g. Data.Vector, and get better performance than with lists.

From N=20, with lists as in your program:

• 52.484s

Also, use rem instead of mod.

• 15.712s

Where the list functions become vector operations:

import qualified Data.Vector.Unboxed as V

canDivAll :: Int -> Int -> Bool
canDivAll max n = V.all (\x ->  n `rem` x == 0) (V.enumFromN 1 max)

main = print . V.head $ V.filter (canDivAll 20) $ V.unfoldr (\a -> Just (a, a+1)) 1