合并功能要慢得多

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和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..]

isPrime 40000000000000000001

=> 0.5秒

isPrime2 40000000000000000001

=> 19.8秒

我的机器是Ubuntu 17.10 x86-64.我正在使用ghc 8.2.1.有谁知道为什么？

Answer 1

第一个片段只prime在内存中保留一个s 列表.

第二个片段将计算自己的片段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 列表.