Консолидированная функция намного медленнее

Question

Я написал функцию isPrime. Он проверяет, является ли данное число простым или нет. Последний "прайм" список дается отдельно.

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

Я думал, что всегда было лучше объединить две функции в одну, если это возможно.. поэтому я объединил isPrime и простую в одну функцию isPrime2. Но производительность isPrime2 очень плохая.

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 секунды

isPrime2 40000000000000000001

=> 19,8 секунд

Моя машина Ubuntu 17.10 x86-64. Я использую GHC 8.2.1. Кто-нибудь знает почему?

Answer 1

Первый фрагмент будет содержать только один список primeв памяти.

Второй фрагмент будет вычислять свой собственный prime до тех пор n^2 каждый раз isPrime2 называется. Ранее обнаруженные простые числа отбрасываются и пересчитываются с нуля при каждом вызове. поскольку isPrime2 рекурсивно это приводит к взрыву.

Промежуточный подход может быть таким:

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

Это пересчитает prime при каждом вызове isPrime2, но не приведет к взрыву, так как каждый вызов внутреннего isPrime поделится тем же списком primes.