एफ # निरंतरता के आधार पर पूंछ प्रत्यावर्तन

Question

कोई स्पष्ट कर सकता हूँ acc "" के लिए की जरूरत है जब निम्न उदाहरण की तरह एक निरंतरता के आधार पर पूंछ पुनरावर्ती क्रिया समाप्त:

let rec repeat_cont i s acc = 
if i = 0 then acc "" 
else repeat_cont (i-1) s (fun x -> acc(s + x)) 

repeat_cont 4 "xo" id 
val it : string = "abababab" 

यदि परिणाम एक सूची है, यह हो जाएगा पूर्णांक के लिए acc [], और acc 0।

Answer 1

जबकि अन्य उत्तर निरंतरता-गुजर शैली में काम करता है लेखन का एक अच्छा पृष्ठभूमि देते हैं, वे एक महत्वपूर्ण बात यह है मेरे मन में भी आसान समझने के लिए कैसे काम करता है सीपीएस करता है कि याद आती है:

आप की जरूरत नहीं है आधार मामले में निरंतरता को बुलाओ। यह है कि रिकर्सन को समाप्त करते समय acc "" की आवश्यकता नहीं है।

मुझे यकीन है कि आप एक श्रृंखला के माध्यम से एक आवर्ती कॉल के माध्यम से एक संचयक गुजरने की मूर्खता को समझते हैं और धीरे-धीरे डेटा संरचना का निर्माण करते हैं - चलो एक सूची या पेड़ कहें। सीपीएस एक अलग नहीं है, सिवाय इसके कि आप संचयक में निर्मित संरचना को एक समारोह है। और चूंकि हम एक कार्यात्मक भाषा में हैं, यह आधार मामले में किसी अन्य के रूप में वापस आने के लिए मूल्य के बराबर है।

let inline repeat_cont i s = 
    let rec inner i s acc = 
     if i = 0 
      then acc 
      else inner (i-1) s (fun x -> acc(s + x)) 
    inner i s id 

let res1: string -> string = repeat_cont 4 "xo" 
res1 "" // "xoxoxoxo" 
res1 "ab" // "xoxoxoxoab" 

let res2: int -> int = repeat_cont 4 1 
res2 0 // 4 
res2 5 // 9 

मैं repeat_cont फिर से लिख दिया यह FSI में इनलाइन किए जाने के साथ काम करने के लिए आदेश में एक आंतरिक पुनरावर्ती क्रिया का उपयोग करने के अपने बहुत ही कोड, अन्यथा:

निम्न उदाहरण की तुलना करें। आप देखेंगे कि इसका प्रकार int -> 'a -> ('b -> 'b) है, यानी आप परिणाम के रूप में एक फ़ंक्शन वापस लेते हैं। जो एक अर्थ में एक सूची या एक int (जमाकर्ताओं के लिए उपयोग किए जाने वाले सामान्य प्रकार) लौटने से अलग नहीं है, सिवाय इसके कि आप इसे प्रारंभिक मान देकर इसे कॉल कर सकते हैं।

Answer 2

जब आप सूची बना रहे हैं, तो तत्वों का acc के परिणामस्वरूप एक ही प्रकार है।

रिकर्सन को समाप्त करने के लिए, आपको बेस केस की आवश्यकता है, इसलिए आप सही प्रकार के साथ कुछ उत्पन्न करने के लिए ज्ञात मान के साथ acc पर कॉल करें।

यह देखते हुए कि अपने उदाहरण, acc = id में, आप के साथ ""

Answer 3

संपादित acc "" की जगह सकता है: इस continuation-passing style के रूप में जाना जाता है। प्रत्येक रिकर्सिव कॉल अपने निरंतरता समारोह को बनाता है और इसे अगले रिकर्सिव कॉल के साथ पास करता है, जिसे कॉल चुनने के रूप में उपयोग किया जाता है (यह आधार आधार है या नहीं)।

---

बस कमी चरणों लिख:

repeat_cont 4 "xo" id 
repeat_cont 3 "xo" k1  where k1 x = id ("xo" + x) 
repeat_cont 2 "xo" k2  where k2 x = k1 ("xo" + x) 
repeat_cont 1 "xo" k3  where k3 x = k2 ("xo" + x) 
repeat_cont 0 "xo" k4  where k4 x = k3 ("xo" + x) 
k4 "" 
k3 ("xo" + "") 
k2 ("xo" + ("xo" + "")) 
k1 ("xo" + ("xo" + ("xo" + ""))) 
id ("xo" + ("xo" + ("xo" + ("xo" + "")))) 
"xoxoxoxo" 

प्रत्येक निरंतरता समारोह ki कि "नतीजा यह है कि पुनरावर्ती कॉल से प्राप्त हो जाएगा के साथ क्या करना है"।

पुनरावर्ती मामले हैं, ki, कहते हैं कि "जो कुछ भी पुनरावर्ती परिणाम x मैं दिया हूँ, आगे जोड़ते इसे करने के लिए s और बढ़े स्ट्रिंग नए, संशोधित परिणाम के रूप में श्रृंखला को पारित"।

बाहरीतम, id, बस कहता है "" अंतिम (परिणाम) परिणाम लौटाएं "।

जब 0 का आधार मामला पहुंच गया है, k4 निरंतरता समारोह बनाया गया है और यह अपना काम करने के लिए इसके तर्क प्राप्त करने के लिए तैयार है। यह "xo" स्ट्रिंग को इसके तर्क में जोड़ देगा, और k3 पर निरंतरता कार्यों की श्रृंखला के साथ परिणाम पास करेगा। तर्क का उपयोग "xo" + x में किया जाएगा, इसलिए यह एक स्ट्रिंग होना चाहिए।

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

एनबी: first-class continuations के साथ भ्रम से बचने के लिए मैं हमेशा "निरंतरता समारोह" कहने के लिए सतर्क हूं, जो पूरी तरह से अलग और अधिक शक्तिशाली जानवर हैं (सुनिश्चित नहीं है कि एफ # में उन्हें है)।