यह हास्केल कोड स्निपेट क्यों असीमित रूप से रिकर्सिव नहीं है?

Question

हास्केल सीखने में मेरी सहायता के लिए, मैं प्रोजेक्ट यूलर की समस्याओं के माध्यम से काम कर रहा हूं। प्रत्येक समस्या को हल करने के बाद, मैं बेहतर कोडिंग प्रथाओं को सीखने के प्रयास में हास्केल विकी के खिलाफ अपना समाधान जांचता हूं।

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) 

इस बात का मेरे अनुभवहीन पढ़ने कि primesprimeFactors, जो primes के संदर्भ में परिभाषित किया गया है के रूप में परिभाषित किया गया है: यहाँ the solutionproblem 3 है। इसलिए primeFactors 9 का मूल्यांकन इस प्रक्रिया का पालन करेगा:

1. factor 9 primes का मूल्यांकन करें।
2. अपने पहले तत्व के लिए primes पूछें, जो 2.
3. अपने अगले तत्व के लिए primes से पूछें।
4. इस प्रक्रिया के हिस्से के रूप में, primeFactors 3 का मूल्यांकन करें।
5. अपने पहले तत्व के लिए primes पूछें, जो 2.
6. अपने अगले तत्व के लिए primes से पूछें।
7. इस प्रक्रिया के हिस्से के रूप में, primeFactors 3 का मूल्यांकन करें।
8. ...

दूसरे शब्दों में, चरण 2-4 असीम दोहराने जाएगा। स्पष्ट रूप से मैं गलत हूं, क्योंकि एल्गोरिदम समाप्त हो जाता है। मैं यहाँ क्या गलती कर रहा हूँ?

Answer 1

primeFactors केवल मूल्यांकन की संख्या के वर्ग रूट तक पढ़ता है। यह सूची में आगे कभी नहीं दिखता है, जिसका अर्थ है कि यह सूची में शामिल करने के लिए परीक्षण की संख्या तक "पकड़ नहीं लेता" है। क्योंकि हास्केल आलसी है, इसका मतलब है कि primeFactors परीक्षण समाप्त हो जाता है।

याद करने के लिए दूसरी बात यह है कि primes एक समारोह है कि एक सूची में आप इसे उपयोग हर बार का मूल्यांकन करता है, बल्कि एक सूची है कि lazily निर्माण किया है नहीं है। तो एक बार 15 वें तत्व को एक बार एक्सेस किया गया है, इसे दूसरी बार एक्सेस करना "मुफ़्त" है (उदाहरण के लिए इसे किसी और गणना की आवश्यकता नहीं है)।

Answer 2

primeFactors 3, अपने अगले तत्व, केवल पहले एक के लिए primes पूछना नहीं है क्योंकि 2*23 से अधिक पहले से ही

Answer 3

केविन का जवाब संतोषजनक है, लेकिन मुझे अपने तर्क में दोष इंगित करने के लिए अनुमति देते हैं। यह # 6 है जो गलत है। इसलिए हम primeFactors 3 मूल्यांकन कर रहे हैं:

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

thunk निर्धारित करने के लिए कि primeFactor 3[3] है कभी नहीं मूल्यांकन किया जाना है।