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

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 2

map does not evaluate all its argument before and executes. And and is short-circuited.

Notice that in GHC all isn't really defined like this.

-- | Applied to a predicate and a list, 'all' determines if all elements
-- of the list satisfy the predicate.
all                     :: (a -> Bool) -> [a] -> Bool
#ifdef USE_REPORT_PRELUDE
all p                   =  and . map p
#else
all _ []        =  True
all p (x:xs)    =  p x && all p xs
{-# RULES
"all/build"     forall p (g::forall b.(a->b->b)->b->b) . 
                all p (build g) = g ((&&) . p) True
 #-}
#endif

We see that all p (x:xs) = p x && all p xs, so whenever p x is false, the evaluation will stop.

Moreover, there is a simplification rule all/build, which effectively transforms your all p [1..max] into a simple fail-fast loop*, so I don't think you can improve much from modifying all.

---

^{*. The simplified code should look like:}

eftIntFB c n x0 y | x0 ># y    = n        
                  | otherwise = go x0
                 where
                   go x = I# x `c` if x ==# y then n else go (x +# 1#)

eftIntFB ((&&) . p) True 1# max#