performance - 合并功能很多

我写了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和prime合并为一个函数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..]

是Prime 40000000000000000001

=> 0.5秒

isPrime2 40000000000000000001

=> 19.8秒

我的机器是Ubuntu 17.10 x86-64。我正在使用ghc 8.2.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的每次调用将共享相同的prime列表。