爲什麼Haskell中的這個遞歸函數很慢？

我正在試圖模擬使用Haskell找到所有素數小於某個數的篩。我發現其他Haskell程序以極快的速度使用Sieve方法。然而，我寫的下面的遞歸函數非常慢。代碼如下爲什麼Haskell中的這個遞歸函數很慢？

sieve' :: Integer -> Integer -> [Integer] 

sieve' n 1 = [2 .. n] 

sieve' n (k + 1) | [x | x <- sieve' n k, x == k + 1] == [] = sieve' n k 

    |otherwise = [x | x <- sieve' n k, x == k + 1 || not (mod x (k + 1) == 0)] 



sieve :: Integer -> [Integer] 

sieve n = sieve' n n

篩20需要約2分鐘。在我寫這個問題時篩30仍未完成。

任何人都可以解釋爲什麼這個遞歸函數是如此之慢。感謝您的任何幫助，您可以提供。

來源

2011-08-21 user898033

作爲Eratosthenes在Haskell中篩選的最終權威，您應該閱讀功能規劃期刊（2009）中的Melissa O'Neill的文章（http://lambda-the-ultimate.org/node/3127）。應該有更多的技巧。 – ShiDoiSi

您的sieve'函數的第二個子句正在遞歸調用（sieve' n k）兩次，從而使您的算法在指數時間內執行。

要解決這個問題，你可以術語一些名綁定，從而保證了它的評估一次：響應評論

sieve' n (k + 1) | [x | x <- rec, x == k + 1] == [] = rec 
    |otherwise = [x | x <- rec, x == k + 1 || not (mod x (k + 1) == 0)] 
    where 
    rec = sieve' n k

更新問爲什麼編譯器不會自動執行此操作：

這種稱爲CSE（通用子表達式消除）的轉換通常不是優化，而是時間和空間使用之間的折衷，所以決定最好留給程序員。

谷歌搜索「CSE」，揭示了一些有趣的討論，其中一個由西蒙·佩頓 - 瓊斯this very good example從1987年的書引用了所謂的「函數式編程語言的實現」（噢，我的，這本書幾乎是一樣老，因爲我）

來源

2011-08-21 06:08:34 Rotsor

謝謝，這正是問題所在。它現在運行速度更快。 – user898033

我覺得很奇怪，編譯器錯過了這個優化。 –

@Jon，我已經更新瞭解決此問題的答案。 – Rotsor

爲什麼Haskell中的這個遞歸函數很慢？

回答

相關問題