Rendimiento de "todos" en haskell

Question

Casi no tenía conocimiento de Haskell y traté de resolver algunos problemas de Project Euler. Mientras que la solución de Number 5 escribí esta solución (por 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..] 

Ahora me enteré, que all se implementa como esto:

all p   = and . map p 

no significa esto, la condición es revisado por cada elemento? ¿No sería mucho más rápido romper con el primer False-Result de la condición? Esto haría que la ejecución del código anterior sea más rápida.

Gracias

Answer 1

and sí es cortocircuitado y puesto que tanto map y all evaluación es perezoso, sólo obtendrá tantos elementos como sea necesario - no más.

Puede comprobar que con una sesión GHCi:

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

Estás asumiendo que no es and cortocircuitos. and detendrá la ejecución en el primer resultado false que vea, por lo que es "rápido" como cabría esperar.

Answer 3

map no evalúa todo su argumento antes de que and se ejecute. Y and está cortocircuitado.

Observe que en GHC all realmente no se define así.

-- | 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 

vemos que all p (x:xs) = p x && all p xs, así que cuando p x es falso, la evaluación se detendrá.

Por otra parte, hay una regla de simplificación all/build, que transforma eficazmente su all p [1..max] en un simple fallo de bucle rápido *, así que no creo que se puede mejorar mucho de la modificación all.

---

^{*. El código simplificado debe verse como:}

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# 

Answer 4

Este es un buen programa para la optimización de la fusión, ya que todos sus bucles se expresan como combinadores fusibles. Por lo tanto, puedes escribirlo usando, por ej. Data.Vector, y obtener un mejor rendimiento que con las listas.

De n = 20, con listas como en su programa:

• 52.484s

También, el uso rem en lugar de mod.

• 15.712S

Cuando las funciones de lista se convierten en operaciones vectoriales:

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