हास्केल

Question

के आलसी मूल्यांकन व्यवहार को समझने में मदद की ज़रूरत है मैंने निक्सन समस्या के दो संस्करण लिखे हैं और मुझे लगता है कि उनके पास समान दक्षता होनी चाहिए लेकिन ऐसा नहीं है। मुझे लगता है कि यह हास्केल के आलसी मूल्यांकन व्यवहार के कारण है। कृपया कोई व्याख्या कर सकते हैं कि यह कैसे निम्न उदाहरण के लिए काम करता है,

nqueens1 n 1 = [[i] | i <- [1..n]] 
nqueens1 n k = [ i:q | i <- [1..n], q <- (nqueens1 n (k - 1)), isSafe i q k] 

isSafe i q n = isSafeHelper i (zip q [(n-1),(n-2)..1]) 
     where isSafeHelper i [] = True 
       isSafeHelper i (x:xs) = (i /= fst x) && abs(i - (fst x)) /= abs(n - (snd x)) && 
             isSafeHelper i xs 
nqueens2 n 1 = [[i] | i <- [1..n]] 
nqueens2 n k = [ i:q | i <- [1..n], q <- boards, isSafe i q k] 
      where boards = nqueens2 n (k-1) 

आप उन्हें मूल्यांकन कर सकते हैं nqueens1 8 8 या nqueens2 8 8 बुला आकार 8.

के एक बोर्ड के लिए यह मूल्यांकन करने के लिए एक ओर जहां nqueens2 काफी काम करता है के द्वारा कुशलता से nqueens1 प्रदर्शन मुद्दों है। मुझे विश्वास है कि ऐसा इसलिए है क्योंकि रिकर्सिव कॉल (nqueens n (k-1)) का मूल्यांकन कई बार किया जा रहा है। हास्कल्स आलसी मूल्यांकन की मेरी समझ से यह मामला नहीं होना चाहिए।

कृपया इस व्यवहार को समझने में मेरी मदद करें।

अग्रिम धन्यवाद।

Answer 1

हां, रिकर्सिव कॉल का मूल्यांकन कई बार किया जाता है। विशेष रूप से i के लिए प्रत्येक मान के लिए इसका मूल्यांकन किया जाता है।

आप इस से बचना चाहते हैं, तो आप जनरेटर पुनर्व्यवस्थित कर सकते हैं ताकि q <- हिस्सा i <- भाग से पहले आता है:

[ i:q | q <- nqueens2 n (k - 1), i <- [1..n], isSafe i q k] 

हालांकि इस परिणामों का क्रम बदल जाएगा। तो यह स्वीकार्य नहीं है, तो आप let उपयोग कर सकते हैं एक बार पुनरावर्ती कॉल के परिणाम की गणना करने के लिए और उसके बाद इस तरह इसका इस्तेमाल:

[ i:q | let rec = nqueens2 n (k - 1), i <- [1..n], q <- rec, isSafe i q k]