Prestazioni di "tutti" in haskell

Question

Non ho quasi nessuna conoscenza di haskell e ho cercato di risolvere alcuni problemi di Eulero di progetto. Mentre risolvere Number 5 ho scritto questa soluzione (per 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..] 

Ora ho scoperto, che all viene implementata in questo modo:

all p   = and . map p 

non significa questo, la condizione è controllato per ogni elemento? Non sarebbe molto più veloce spezzare il primo Falso-Risultato della condizione? Ciò renderebbe più veloce l'esecuzione del codice sopra.

Grazie

Answer 1

and per sé è in corto circuito e dal momento che entrambi map e all valutazione è pigro, si otterrà solo il maggior numero di elementi come necessario - non di più.

È possibile verificare che con una sessione 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

Stai assumendo che non è and corto circuito. and interromperà l'esecuzione sul primo risultato false che vede, quindi è "veloce" come ci si potrebbe aspettare.

Answer 3

map non valuta tutti i suoi argomenti prima dell'esecuzione di and. E and è in cortocircuito.

Si noti che in GHC all non è veramente definito come questo.

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

vediamo che all p (x:xs) = p x && all p xs, quindi, quando p x è falso, la valutazione si ferma.

Inoltre, c'è una regola di semplificazione all/build, che trasforma in modo efficace il vostro all p [1..max] in un semplice ciclo fail-veloce *, quindi non credo che si può migliorare molto di modificare all.

---

^{*. Il codice semplificato dovrebbe assomigliare:}

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

Si tratta di un buon programma per l'ottimizzazione di fusione, come tutti i loop sono espressi come combinatori fusibili. Quindi puoi scriverlo usando, ad es. Data.Vector e ottieni prestazioni migliori rispetto agli elenchi.

Da N = 20, con liste come nel vostro programma:

• 52.484s

Inoltre, utilizzare rem invece di mod.

• 15.712s

Dove le funzioni della lista diventano operazioni vettoriali:

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