consolidated function is much slower

Question

I wrote isPrime function. It checks if a given number is prime or not. The last "prime" list is given separately.

prime :: [Integer]
prime = 2 : filter isPrime [3..]
isPrime :: Integer -> Bool
isPrime n | n < 2 = False
isPrime n = all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ prime

I thought it was always better to consolidate two functions into one if possible..so I consolidated isPrime and prime into one function isPrime2. But the isPrime2's performance is very bad.

isPrime2 :: Integer -> Bool
isPrime2 n | n < 2 = False
isPrime2 n = all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ 2 : filter isPrime2 [3..]

isPrime 40000000000000000001

=> 0.5 second

isPrime2 40000000000000000001

=> 19.8 seconds

My machine is Ubuntu 17.10 x86-64. I am using ghc 8.2.1. Does anyone know why?

Answer 1

The first snippet will keep only one list of primes in memory.

The second snippet will compute its own prime until n^2 every single time isPrime2 is called. Previously discovered primes are discarded and recomputed from scratch at every call. Since isPrime2 is recursive this leads to a blow-up.

An intermediate approach can be this one:

isPrime2 :: Integer -> Bool
isPrime2 m = isPrime m
   where
   prime :: [Integer]
   prime = 2 : filter isPrime [3..]
   isPrime :: Integer -> Bool
   isPrime n | n < 2 = False
   isPrime n = all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ prime

This will recompute prime at every call of isPrime2, but will not lead to a blow-up since each call of the inner isPrime will share the same list of primes.