Performance of "all" in haskell

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

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

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#

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

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.