爲什麼這個Haskell代碼片段不是無限遞歸的？

爲了幫助我學習Haskell，我正在解決Project Euler上的問題。解決了每個問題後，我檢查了我的解決方案與Haskell wiki，試圖學習更好的編碼實踐。這裏是the solution到problem 3：爲什麼這個Haskell代碼片段不是無限遞歸的？

primes = 2 : filter ((==1) . length . primeFactors) [3,5..] 

primeFactors n = factor n primes 
    where 
    factor n (p:ps) 
     | p*p > n  = [n] 
     | n `mod` p == 0 = p : factor (n `div` p) (p:ps) 
     | otherwise  = factor n ps 

problem_3 = last (primeFactors 317584931803)

我的這個天真的解讀是，primes中的primeFactors，這是在primes定義的定義。因此，評估primeFactors 9將遵循以下過程：

評估factor 9 primes。
詢問primes爲其第一個元素，即2.
詢問primes的下一個元素。
作爲此過程的一部分，請評估primeFactors 3。
詢問primes爲其第一個元素，即2.
詢問primes的下一個元素。
作爲此過程的一部分，請評估primeFactors 3。
...

換句話說，步驟2-4將重複無限。很明顯，我錯了，算法終止。我在這裏犯了什麼錯誤？

來源

2011-12-12 Matthew Pirocchi

因爲，如這裏的答案說，'直到素的平方超過被測試的數目primeFactors'只訪問'primes'，該代碼相當於'素數= 2：[N |所有（（> 0）.rem n）$ takeWhile（（<= n）。（^ 2））素數]這顯然是非循環的。 –

primeFactors永遠只能最多讀取它的評估數的平方根。它從來沒有在列表中看得更遠，這意味着它永遠不會「追上」它正在測試列入列表中的數字。由於Haskell是懶惰的，這意味着primeFactors測試確實終止。

還有一點要記住的是，primes不是每次訪問它時都會評估列表的函數，而是一個懶惰地構建的列表。因此，一旦第15個元素被訪問過一次，第二次訪問它就是「免費」的（例如，它不需要任何進一步的計算）。

來源

2011-12-12 03:17:30

細節：訪問它第二次還是費15個dereferencings，因爲我們正在做的利弊小區列表...這可能是很多，如果你有上百個列表元素 – naiad

@sparkleshy這將是（約）'開方二次的（N ）'，即將（近似）線性成本添加到*上述線性*計算中。 –

primeFactors 3不問primes它的下一個元素，只有第一個，因爲2*2大於3已經

來源

2011-12-12 05:59:01 asvyazin

凱文的答案是令人滿意的，但讓我找出這個安全漏洞存在的邏輯。＃6是錯的。因此，我們正在評估primeFactors 3：

primeFactors 3   ==> 
factor 3 primes   ==> 
factor 3 (2 : THUNK) ==> 
2*2 > 3 == True   ==> 
[3]

的THUNK永遠不需要進行評估，以確定primeFactor 3是[3]。

來源

2011-12-12 22:17:28

爲什麼這個Haskell代碼片段不是無限遞歸的？

回答

相關問題