統合機能がはるかに遅い

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 

私はpossible..soは、私は1つの関数isPrime2にisPrimeと首相を統合した場合、一つに二つの機能を統合するために、常により良いと思いました。しかし、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の1つのリストのみをメモリに保持します。

isPrime2が呼び出される毎回n^2まで、第2のスニペットは、prime、独自に計算します。以前に発見された素数は、すべての呼び出し時にゼロから破棄され、再計算されます。 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 

これはisPrime2のすべての呼び出しでprimeを再計算しますが、内部isPrimeの各呼び出しは同じリストを共有することになりますので、ブローアップにつながることはありませんprime s。