Doing "all" in haskell

Question

I hardly knew about haskell and tried to solve some problems of Project Euler. When 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 executed as follows:

 all p = and . map p 

Does this not mean that the condition is checked for each element? Wouldn't it be much faster to overcome the first false result of this condition? This will speed up the code above.

thanks

Answer 1

and itself is shorted, and since the estimates of map and all lazy, you get only as many elements as necessary - no 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 arguments before and . And and shorted.

Note that in GHC all is not really defined like that.

 -- | 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) = px && 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) = px && all p xs , so whenever the px is false, the evaluation stops.

In addition, there is an all/build simplification rule that effectively converts your all p [1..max] into a simple fault-tolerant loop *, so I don’t think you can significantly improve the modification of all .

---

^{*. Simplified code should look like this:}

 eftIntFB cn 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# 

Answer 3

This is a good merge optimization program since all your loops are expressed as fusible combinators. Thus, you can write it using, for example, 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

If 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 

Answer 4

You assume that and not short-circuited. and will stop the execution of the first result false , so it will be "fast", as you might expect.