Jeroen,
isPrime :: Int -> Bool isPrime x = isPrime' x primes where isPrime' x (p:ps) | x == p = True | x > p = isPrime' x ps | otherwise = False
main = print $ length (filter (== True) (map isPrime [1..5000])) [...] isPrime x = elem x (takeWhile (<= x) primes)
Here's a couple of things, although I don't know if they account for what you're seeing. All code is untested. 1) A simpler main would be: main = print $ length $ filter isPrime [1..5000] This version manually fuses your map and filter. Of course it's not the same if you're doing anything else besides 'length'. 2) The takeWhile in your second isPrime creates a throwaway list, which doesn't exist in the explicit-recursion isPrime. Unless this gets optimized out, this could be the droid you're looking for. I'd compile with profiling (ghc -O2 --make -prof -auto-all experiment2), and run ./experiment2 +RTS -p -s Find profiling stats in experiment2.prof, and check whether the latter version isn't allocating a lot more. When you feel like Core-diving, it's something specific to look for. 3) Maybe you can get the best of your two versions -- meaning the relative speed of the first and functional style of the second -- by writing your own 'elem' replacement that works on a sorted list. Something like this, with suitably defined elemAsc: -- elemAsc: tests presence of element in an ascending list elemAsc :: (Ord a) => a -> [a] -> Bool elemAsc ... isPrime x = elemAsc x primes Here's a good habit: abstract things like this out. Read the libraries, and look for better and more abstract patterns. Rinse, repeat. 4) This doesn't explain why the version with real primes was 10x slower. Are you comparing apples to apples? Specifically, comparing both versions of isPrime above using real primes, so both of them have to create the primes list? Does your code for real primes still use [Int] and not [Integer] or (Num t) => [t] ? I haven't invested the time yet to stare at GHC Core until it clicks, excepting a few snippets that have been discussed here. I'm not sure how early in the learning curve it's advisable. Probably depends on your background. Good luck Eulering, John