हास्केल में, यह एक निश्चित बिंदु की एक सरल (भोली) परिभाषा है

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

लेकिन, हास्केल वास्तव में इसे कैसे लागू करता है (अधिक कुशल)

fix f = let x = f x in x

मेरा सवाल यह है कि दूसरा पहले की तुलना में अधिक कुशल क्यों है?

19
Vijaya Rani 21 मई 2016, 20:45

3 जवाब

सबसे बढ़िया उत्तर

धीमा fix रिकर्सन के प्रत्येक चरण पर f कॉल करता है, जबकि तेज़ वाला f ठीक एक बार कॉल करता है। इसे ट्रेसिंग के साथ देखा जा सकता है:

import Debug.Trace

fix  f = f (fix f)
fix' f = let x = f x in x

facf :: (Int -> Int) -> Int -> Int
facf f 0 = 1
facf f n = n * f (n - 1)

tracedFacf x = trace "called" facf x

fac  = fix tracedFacf
fac' = fix' tracedFacf

अब कुछ दौड़ने का प्रयास करें:

> fac 3
called
called
called
called
6
> fac' 3
called
6

अधिक विवरण में, let x = f x in x के परिणामस्वरूप x के लिए एक आलसी थंक आवंटित किया जाता है, और इस थंक के लिए एक पॉइंटर f को पास कर दिया जाता है। पहले fix' f का मूल्यांकन करने पर, थंक का मूल्यांकन किया जाता है और इसके सभी संदर्भ (यहां विशेष रूप से: जिसे हम f में पास करते हैं) परिणामी मूल्य पर पुनर्निर्देशित किए जाते हैं। ऐसा होता है कि x को एक मान दिया जाता है जिसमें x का संदर्भ भी होता है।

मैं मानता हूं कि यह दिमाग को झुकाने वाला हो सकता है। यह कुछ ऐसा है जिसे आलस्य के साथ काम करते समय आदत डालनी चाहिए।

22
András Kovács 21 मई 2016, 22:48

मुझे नहीं लगता कि यह हमेशा (या आवश्यक रूप से हमेशा) मदद करता है जब आप एक फ़ंक्शन के साथ fix को कॉल कर रहे होते हैं जो एक तर्क लेने वाले फ़ंक्शन को उत्पन्न करने के लिए दो तर्क लेता है। देखने के लिए आपको कुछ बेंचमार्क चलाने होंगे। लेकिन आप इसे एक तर्क लेने वाले फ़ंक्शन के साथ भी कॉल कर सकते हैं!

fix (1 :)

एक सर्कुलर लिंक्ड सूची है। fix की भोली परिभाषा का उपयोग करते हुए, यह इसके बजाय एक अनंत सूची होगी, जिसमें नए टुकड़े आलस्य से बनाए जाएंगे क्योंकि संरचना को मजबूर किया जाता है।

10
dfeuer 21 मई 2016, 22:23

मेरा मानना ​​​​है कि यह पहले ही पूछा जा चुका है, लेकिन मुझे इसका जवाब नहीं मिला। कारण यह है कि पहला संस्करण

fix f = f (fix f)

एक पुनरावर्ती कार्य है, इसलिए इसे रेखांकित नहीं किया जा सकता है और फिर अनुकूलित किया जा सकता है। GHC मैनुअल:

उदाहरण के लिए, एक स्व-पुनरावर्ती फ़ंक्शन के लिए, लूप ब्रेकर केवल फ़ंक्शन ही हो सकता है, इसलिए एक INLINE प्रगति को हमेशा अनदेखा किया जाता है।

परंतु

fix f = let x = f x in x

पुनरावर्ती नहीं है, रिकर्सन को let बाइंडिंग में ले जाया जाता है, इसलिए इसे इनलाइन करना संभव है।

अद्यतन करें: मैंने कुछ परीक्षण किए और जबकि पूर्व संस्करण इनलाइन नहीं है, जबकि बाद वाला करता है, यह प्रदर्शन के लिए महत्वपूर्ण नहीं लगता है। तो अन्य स्पष्टीकरण (ढेर पर एक ही वस्तु बनाम प्रत्येक पुनरावृत्ति बनाना) अधिक सटीक प्रतीत होता है।

5
Petr 28 मई 2016, 22:31