निम्नलिखित में, लाइन maybeNext.map{rec}.getOrElse(n) रिकर्स या एस्केप पैटर्न को लागू करने के लिए Option मोनैड का उपयोग करती है।

scala> @tailrec                                          
     | def rec(n: Int): Int = {                          
     |   val maybeNext = if (n >= 99) None else Some(n+1)
     |   maybeNext.map{rec}.getOrElse(n)                 
     | }

हालांकि अच्छा लग रहा है:

<console>:7: error: could not optimize @tailrec annotated method: 
it contains a recursive call not in tail position
       def rec(n: Int): Int = {
           ^

मुझे लगता है कि संकलक इस मामले में पूंछ रिकर्सन को हल करने में सक्षम होना चाहिए। यह निम्नलिखित (कुछ हद तक प्रतिकारक, लेकिन संकलन योग्य) नमूने के बराबर है:

scala> @tailrec                                          
     | def rec(n: Int): Int = {                          
     |   val maybeNext = if (n >= 99) None else Some(n+1)
     |   if (maybeNext.isEmpty) n                        
     |   else rec(maybeNext.get)                         
     | }
rec: (n: Int)Int

क्या कोई यहां रोशनी दे सकता है? संकलक इसका पता क्यों नहीं लगा सकता? क्या यह एक बग है, या एक निरीक्षण है? क्या समस्या बहुत कठिन है?

संपादित करें: पहले उदाहरण से @tailrec हटाएं और विधि संकलित करें; लूप समाप्त हो जाता है। अंतिम कॉल हमेशा getOrElse होती है जो if option.isEmpty defaultValue else recurse के बराबर होती है। मुझे लगता है कि यह संकलक द्वारा अनुमान लगाया जा सकता है और होना चाहिए।

2
Synesso 4 मई 2011, 04:05

1 उत्तर

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

यह एक बग नहीं है, यह एक निरीक्षण नहीं है, और यह एक पूंछ रिकर्सन नहीं है।

हां, आप कोड को टेल रिकर्सिव तरीके से लिख सकते हैं, लेकिन इसका मतलब यह नहीं है कि प्रत्येक समकक्ष एल्गोरिदम को टेल रिकर्सिव बनाया जा सकता है। आइए इस कोड को लें:

maybeNext.map{rec].getOrElse(n)

सबसे पहले, आखिरी कॉल getOrElse(n) पर है। यह कॉल वैकल्पिक नहीं है - यह हमेशा की जाती है, और परिणाम को समायोजित करना आवश्यक है। लेकिन चलिए इसे अनदेखा करते हैं।

अगली से अंतिम कॉल map{rec} पर है। नहीं से rec तक। वास्तव में, rec को आपके कोड में बिल्कुल नहीं कहा जाता है! कुछ अन्य फ़ंक्शन इसे कॉल करते हैं (और, वास्तव में, यह map पर अंतिम कॉल भी नहीं है), लेकिन आपका फ़ंक्शन नहीं।

पूंछ पुनरावर्ती होने के लिए कुछ के लिए, आपको कॉल को "गोटो" के साथ बदलने में सक्षम होना चाहिए, इसलिए बोलने के लिए। ऐशे ही:

def rec(n: Int): Int = { 
  BEGINNING:                         
  val maybeNext = if (n >= 99) None else Some(n+1)
  if (maybeNext.isEmpty) n                        
  else { 
    n = maybeNext.get
    goto BEGINNING
   }                         
}

यह दूसरे कोड में कैसे होगा?

def rec(n: Int): Int = {                  
  BEGINNING:        
  val maybeNext = if (n >= 99) None else Some(n+1)
  maybeNext.map{x => n = x; goto BEGINNING}.getOrElse(n)                 
}

यहां गोटो rec के अंदर नहीं है। यह एक अनाम Function1 के apply के अंदर है, जो अपनी बारी से, Option के map के अंदर है, इसलिए यहां एक शाखा दो स्टैक फ्रेम को छोड़ देगी प्रत्येक कॉल। मान लें कि अंतर-विधि शाखाकरण पहली जगह में संभव था।

8
Daniel C. Sobral 4 मई 2011, 18:58
@tailrec निकालें और विधि संकलित करें; लूप समाप्त हो जाता है। अंतिम कॉल getOrElse है, जो `if option.isEmpty defaultValue के बराबर है, अन्यथा गोटो BEGINNING। मुझे लगता है कि यह अनुमान लगाया जा सकता है और होना चाहिए।
 – 
Synesso
4 मई 2011, 04:43
(मुझे पूरा यकीन है कि इस तरह के परिवर्तन का अनुमान लगाने का कोई तुच्छ तरीका नहीं है, लेकिन सबसे तुच्छ आकस्मिक मामले हैं। पोस्ट में एक टेल-रिक समतुल्य पोस्ट किया गया था। स्केलैक कंपाइलर होने के बाद कोड को फिर से लिखने का प्रयास करें। एक समकक्ष के लिए जो पूंछ-पुनरावर्ती हो सकता है यकीनन दायरे से बाहर है और विभिन्न संकलन मॉड्यूल के साथ एक साइड-इफेक्टिंग भाषा चीजों की मदद नहीं करती है। @tailrec बस कहता है "सुनिश्चित करें कि यह है पूंछ-पुनरावर्ती" - कोई एआई नहीं, एक बॉक्स में कोई सूक्ति नहीं।)
 – 
user166390
4 मई 2011, 07:30
यह शर्म की बात है क्योंकि (मुझे लगता है) map{recursiveCall}.getOrElse(nonRecursiveValue) स्पष्ट रूप से तार्किक रूप से पूंछ-पुनरावर्ती है। और, इस पैटर्न की अनुमति नहीं देना (भले ही इसे संकलक तर्क में स्पष्ट रूप से सक्षम किया जाना है), इसका मतलब है कि लोग एनोटेशन छोड़ देंगे या कम सुरुचिपूर्ण कोड लिखेंगे।
 – 
Synesso
4 मई 2011, 09:58
1
एक कंपाइलर प्लगइन लिखें :-)
 – 
user166390
4 मई 2011, 10:54
1
ओह, वाकई। मैं एक पल के लिए वहां उलझन में था, लेकिन एक पूंछ रिकर्सन एक फंक्शन कॉल को एक शाखा के साथ उस बिंदु पर बदल रहा है, अवधि। कुछ और करने के लिए, कम से कम, कि स्कैला कंपाइलर जानता है कि विकल्प कैसे काम करता है, और यह कुछ ऐसा है जिसके खिलाफ ओडर्स्की बहुत अधिक है। उदाहरण के लिए, लूप के दौरान समझ के लिए सीमा को अनुकूलित नहीं करने पर उनका पूर्ण आग्रह देखें।
 – 
Daniel C. Sobral
4 मई 2011, 18:56