项目欧拉概率10使用哈斯克尔

Question

好吧，所以我做了一个小的修改，似乎已经使哈斯克尔很大的不同。这是怎么回事：

我实施Eratosthenes筛从项目欧勒Prob 10。这是怎么一回事呢：

primesBelowN :: Integer -> [Integer] 
primesBelowN n = 2:3:filter f [6*k+i | k <- [1..(n-1)`div`6], i <- [-1, 1]] 
       where f x = foldr g True [2..truncate(sqrt(fromInteger x))] 
          where g t ac = (x `rem` t /= 0) && ac 

main = print $ sum $ primesBelowN 2000000 

与GHC编译它，我获得8.95秒的运行时间：

$ ghc -O3 010SummationOfPrimes.hs 
$ time 010SummationOfPrimes 
142913828922 
8.739u 0.122s 0:08.95 98.8% 0+0k 2384+0io 1pf+0w 

我想我可以在g功能采取Haskell的惰性计算的优势，优化代码。可以这样做（或因此我认为）通过简单地将ac作为第一个参数&&，因此，如果ac == False不计算不等式：

primesBelowN :: Integer -> [Integer] 
primesBelowN n = 2:3:filter f [6*k+i | k <- [1..(n-1)`div`6], i <- [-1, 1]] 
       where f x = foldr g True [2..truncate(sqrt(fromInteger x))] 
          where g t ac = ac && (x `rem` t /= 0) 

main = print $ sum $ primesBelowN 2000000 

出人意料的是，它使程序4X慢！。运行时现在明显更大，为30.94s：

$ ghc -O3 010SummationOfPrimes.hs 
$ time 010SummationOfPrimes 
142913828922 
30.765u 0.157s 0:30.94 99.9% 0+0k 2384+0io 1pf+0w 

我不知道哪里出了问题......任何提示/建议/答案？提前致谢！

编辑

所以，我玩这个，当我摔倒了另一件事。看起来很容易地转为无限循环，如果我只是调节这样我的函数：

primesBelowN :: Integer -> [Integer] 
primesBelowN n = 2:3:filter f [6*k+i | k <- [1..(n-1)`div`6], i <- [-1, 1]] 
       where f x = foldr g True [m | m <- [2..], 
               m <= truncate(sqrt(fromInteger x))] 
          where g t ac = (x `rem` t /= 0) && ac 

main = print $ sum $ primesBelowN 2000000 

进程的内存只是不断在这种情况下，以庞大的数字（80Gig之前，我杀了它）爆炸，没有任何输出：

$ ghc -O3 010SummationOfPrimes.hs 
$ time 010SummationOfPrimes 
^C20.401u 7.994s 0:28.42 99.8% 0+0k 2384+0io 1pf+0w 

任何想法现在怎么回事？

Answer 1

有关问题的通知的第一部分如何foldr操作：

foldr g x0 [x1, x2, x3, .., xn] = g x1 (g x2 (g x3 (..(..(g xn x0)))..) 

在我们的情况下，

foldr g True [2..truncate(sqrt(fromInteger x))] 
     where g t ac = (x `rem` t /= 0) && ac 

等同于：

foldr g True (map h [2..truncate(sqrt(fromInteger x))]) 
     where g t ac = t && ac 
      h t = x `rem` t /= 0 

这相当于：

foldr (&&) True (map h [2..truncate(sqrt(fromInteger x))]) 
     where h t = x `rem` t /= 0 

和这又相当于：

(h x1) && ((h x2) && ((h x3) &&(....((h xn) && True)))..) 

请记住，我们正在处理一个懒惰的语言中，评价通过模式匹配主导。 &&仅在其第一个参数中是严格的，这意味着除非必要，否则将不必生成第二个参数表达式，即使此时它只会继续执行，直到(h x2)处于最外层。 作为这样的多/适当/表示是一个诸如此（部分伪代码）：

(h x1) && {instructions to generate (h x2) && ((h x3) && (....((h xn) && True)))..)} 

结果存储器需求来计算满& &表达主要是恒定的。我们只需要保留(h x1)以及生成下一个值的说明。如果(h x1)是False我们停止，否则我们丢弃它并生成另一对值和指令。这显然不是哈斯克尔实际上如何实现的，而是作为一个模型。

现在，如果您切换参数顺序，&&必须首先评估第二个参数的表达式，其中&&必须完全评估下一个子表达式等等，并要求所有中间值保持在直到整个表达式完全展开并根据需要进行评估。另外请注意，余数检查将以相反的顺序完成，这使得程序效率更低，因为与较小的素数相比，合成数字不是较大素数的倍数。结果总运行时间和内存要求更差。

关于问题的第二个（已编辑）部分，问题是您不再使用有限列表。对列表理解的限制作为过滤而不是限制。要使foldr使用&&完成，您需要提供一个空列表（对于无限列表定义来说这是不可能的），或者对谓词返回False的列表中的单个元素提供模式匹配。不幸的是，有些情况（x是prime），谓词不会返回False，foldr将继续尝试对其它元素进行模式匹配。所有这些都是徒劳无益的，因为守卫之后没有更多的元素会在一分之后产生。它失败了几乎相同的原因，这种失败：

head $ filter (const False) [1..]