項目歐拉概率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..]