[Haskell-cafe] how to make haskell faster than python at finding primes?

Alex Jacobson alex at alexjacobson.com
Mon Aug 6 03:55:06 EDT 2007

This implementation of calculating 10000 primes (compiled with GHC -O2) 
is 25% slower than the naive python implementation.  Shouldn't it be 
faster?  Am I doing something obviously stupid?

   primes = map (\(x,_,_)->x) $ filter (\(_,isP,_)->isP) candidates
   candidates = (2,True,[]):(3,True,[]): map next (tail candidates)

   next (candidate,isP,modCounts) =
     let newCounts = map incrMod2 modCounts in -- accumulate mods
     (candidate+2 -- we only need to bother with odd numbers
     ,(isPrime newCounts) -- track whether this one is prime
     ,if isP then (candidate,2):newCounts else newCounts) -- add if prime
   isPrime = and .  map ((/=0).snd)
   incrMod2 (p,mc) = let mc' = mc+2 in
     if mc'<p then (p,mc') else if mc'>p then (p,1) else (p,0)

Note: It is shorter than the python, but I would have assumed that GHC 
could deliver faster as well.


More information about the Haskell-Cafe mailing list