वाई-कॉम्बिनेटर का उपयोग कैसे करें; यह अनंत रिकर्सन 9 क्यों लौटाता है?

Question

Y - Combinator

मैं वाई के बारे में जानने की कोशिश कर रहा है - combinators (उस पर एक स्पष्टीकरण के रूप में अच्छी तरह से सुंदर हो जाएगा) और इस wiki से एक उदाहरण भर में आया था। हास्केल या पायथन में विषय पर गहराई से स्पष्टीकरण की सराहना की जाएगी। Pleaaase!

कोड

fix :: (a -> a) -> a 
fix f = f (fix f) 

समस्या

समारोह कहा जाता fix रिटर्न 9 जब fix(\x -> 9) लिए आवेदन किया है और मैं कोई सुराग नहीं क्यों है; जब मैं ढेर का पालन करता हूं तो मैं f(f ... (fix f) ...) को विज़ुअलाइज़ करता हूं।

>> fix (\x -> 9) 
>> 9 

Answer 1

सबसे पहले: fix समारोह आप एक निश्चित बिंदु Combinator प्रत्यक्ष प्रत्यावर्तन के साथ लागू किया है। वाई combinator विशेष फिक्स्ड-पॉइंट संयोजक है कि को सिंटैक्टिक रिकर्सन की आवश्यकता नहीं है, इसलिए यह fix जैसी ही चीज़ को पूरा करता है लेकिन एक अलग तरीके से।

यदि आप उत्सुक हैं, तो आप यहां SO12 पर how to implement the Y combinator in Haskell देख सकते हैं। यह स्थिर प्रकारों के साथ थोड़ा मुश्किल है-इसे काम करने के लिए एक पुनरावर्ती प्रकार की आवश्यकता है।

आपके दूसरे प्रश्न के लिए, कोड आलस्य के लिए धन्यवाद काम करता है। यदि आप (\ x -> 9) से पर कुछ भी लागू करते हैं, तो उस चीज़ का मूल्यांकन कभी नहीं किया जाएगा। इस प्रयास करें:

λ> (\ x -> 9) (error "fail") 
9 

यह fix की परिभाषा में पुनरावर्ती कॉल भी शामिल है। क्या होता है को देखो जब आप fix की परिभाषा में (\ x -> 9) साथ बाहरी सबसे f बदल देते हैं:

(\ x -> 9) (fix f) 

error साथ संस्करण के रूप में बिल्कुल एक ही तर्क के बाद, पुनरावर्ती कॉल कभी नहीं का मूल्यांकन किया जाता है और आप बस मिल एक 9 बाहर।