वैकल्पिक वाई संयोजक परिभाषा

Question

मैंने हाल ही में वाई संयोजन के चारों ओर अपने सिर को लपेटने में कुछ समय बिताया है, और मैंने पाया है कि यह आमतौर पर परिभाषित (अधिक या कम) होता है (यह सी # में है, लेकिन पसंद की भाषा है महत्वपूर्ण नहीं है):

public delegate TResult SelfApplicable<TResult>(SelfApplicable<TResult> r); 

public static TResult U<TResult>(SelfApplicable<TResult> r) 
{ 
    return r(r); 
} 

public static Func<TArg1, TReturn> Y<TArg1, TReturn>(Func<Func<TArg1, TReturn>, Func<TArg1, TReturn>> f) 
{ 
    return U<Func<TArg1, TReturn>>(r => arg1 => f(U(r))(arg1)); 
} 

है कि पूरी तरह से कार्यात्मक (यमक इरादा) है, यह प्रतीत होता है कि मेरी परिभाषा बहुत सरल है:

public static Func<TArg1, TReturn> Y<TArg1, TReturn>(Func<Func<TArg1, TReturn>, Func<TArg1, TReturn>> f) 
{ 
    return f(n => Y(f)(n)); 
} 

वहाँ किसी भी कारण है कि बाद के परिभाषा उतना आम नहीं है (मुझे अभी तक इसे नेट पर नहीं मिला है)? क्या संभवतः वाई को परिभाषित करने के साथ कुछ करना होगा?

Answer 1

हास्केल करी को परिभाषित करने और untyped लैम्ब्डा पथरी में गुमनाम पुनरावर्ती कार्यों का उपयोग करने के लिए Y Combinator का आविष्कार किया, परिभाषित इस प्रकार है:
Y = λf·(λx·f (x x)) (λx·f (x x))

मेरे परिभाषा यह रूप Y Combinator का मूल उद्देश्य धरा रिकर्सिव कार्यों को परिभाषित करने के लिए सी # के अंतर्निहित समर्थन पर निर्भर करता है। हालांकि, यह अभी भी उपयोगी है कि यह सी # में अज्ञात रिकर्सिव कार्यों को परिभाषित करने की अनुमति देता है।

Answer 2

मुझे यकीन है कि आपका प्रश्न क्या है नहीं कर रहा हूँ, लेकिन मैं कारण यह है कि न तो Y Combinator है और न ही अपने समाधान जंगली में ज्यादा देखा जाता है लगता है कि दोहरा है:

1. गुमनाम पुनरावर्ती कार्यों वास्तव में दुर्लभ हैं; विशेष रूप से सी # में महान नहीं है (पढ़ें: बिलकुल भी नहीं) पूंछ रिकर्सन के लिए समर्थन।

2. वहाँ एक बहुत आसान सी # में छद्म "गुमनाम" पुनरावर्ती lambdas को परिभाषित करने के रास्ते (अधिक uninitiated के लिए पठनीय) है:

   Func<int, int> fac = null; 
   fac = x => x == 0 ? 1 : fac(x - 1) * x; 
   

   दी, इस गुमनाम नहीं है, लेकिन यह "पर्याप्त बंद" व्यावहारिक उद्देश्यों के लिए।

Answer 3

बेनामी प्रत्यावर्तन, यानी एक निश्चित बिंदु Combinator साथ, अक्सर जरूरी, दृढ़ता से टाइप भाषाओं में नहीं देखा जाता है, बहुत ही सरल कारण यह आसान है कि आपके [सेंसर] समारोह नाम के लिए की तुलना में एक गुमनाम परिभाषित करने के लिए के लिए फ़ंक्शन जो एक ही कार्य करता है। इसके अलावा, ओओए & डी हमें सिखाता है कि कोड जो एकाधिक स्थानों में मूल्य है, को डुप्लिकेट नहीं किया जाना चाहिए; इसे नामित किया जाना चाहिए और इस प्रकार एक आम जगह से पहुंचा जा सकता है। Lambdas उनके स्वभाव से एक बंद कर रहे हैं; लूपिंग संरचनाओं जैसे अधिक सामान्य एल्गोरिदम में उपयोग के लिए बहुत ही स्थिति-विशिष्ट कोड की कुछ पंक्तियों को निर्दिष्ट करने का एक तरीका। अधिकतर पुनरावर्ती एल्गोरिदम ऐसी चीजें हैं जिनमें सुंदर सामान्य अनुप्रयोग (सॉर्टिंग, रिकर्सिव श्रृंखला श्रृंखला आदि) होती है, जो आम तौर पर आपको अधिक व्यापक रूप से सुलभ बनाने के लिए प्रेरित करती हैं।

लैम्ब्डा कैलकुस एक तरफ, अधिकांश प्रोग्रामिंग भाषाओं में एक अज्ञात फ़ंक्शन एफ का उपयोग करने से पहले मौजूद होना चाहिए। यह स्वयं के संदर्भ में किसी फ़ंक्शन की परिभाषा को रोकता है।,

Fact(0) -> 1 

Fact(i) -> Fact(i-1) * i 

यह ठीक होगा कि इस Erlang-दुनिया में छोड़कर: इस तरह के Erlang के रूप में कुछ कार्यात्मक भाषाओं में, समारोह एफ 'भार के ", जहां सरल कार्यों को और अधिक जटिल लोगों के लिए आधार मामलों के रूप में उपयोग किया जाता है का उपयोग कर परिभाषित किया गया है अब एक नामित फ़ंक्शन "फैक्ट" है, और जब उस विधि को कॉल करते समय प्रोग्राम ओवरलोड के माध्यम से "गिर जाएगा" जब तक कि यह पहला पैरामीटर नहीं मिलता है जिसके लिए पैरामीटर मिलान होता है। इस सटीक निर्माण के लिए सी # में बराबर नहीं है क्योंकि सी # मूल्य के आधार पर ओवरलोड को चुनने का समर्थन नहीं करता है।

चाल किसी भी तरह से फ़ंक्शन को संदर्भित करने के लिए किसी फ़ंक्शन का संदर्भ प्राप्त करना है। कई तरीके हैं, जिनमें से सभी को पूर्व-मौजूदा संदर्भ की आवश्यकता है। यदि आप नाम से फ़ंक्शन का संदर्भ नहीं दे सकते हैं, तो एफपी-संयोजक फ़ंक्शन का प्रकार Func<Func<Func<Func<Func<... है। कोनराड की विधि सबसे आसान है, लेकिन सी # में यह एक हैक की तरह समाप्त होता है (यह संकलित करता है लेकिन रीशेर्पर अभी भी शिकायत करता है कि यह एक संभावित अवैधऑपरेशन अपवाद है; एक शून्य विधि सूचक नहीं आ सकता है)।

यहाँ, कुछ मैं साधारण मामलों के लिए उपयोग करते हैं, मूल रूप से परोक्ष एक परोक्ष टाइप लैम्ब्डा टाइप करने के लिए सक्षम नहीं होने के लिए प्रतिनिधि वैकल्पिक हल का उपयोग कर:

public static class YCombinator 
{ 
    public delegate TOut RLambda<TIn, TOut>(RLambda<TIn, TOut> rLambda, TIn a); 
    public static Func<T,T> Curry<T>(this RLambda<T,T> rLambda) 
    { 
     return a => rLambda(rLambda, a); 
    } 
} 

//usage 
var curriedLambda = YCombinator.Curry<int>((f, i) => i <= 0 ? 1 : f(f, i - 1)*i) 
var shouldBe120 = curriedLambda(5); 

आप एक Curry<TIn, TOut> अधिभार मामलों को संभालने के लिए जहां इनपुट प्रकार घोषणा कर सकते हैं आउटपुट प्रकार नहीं है, जैसे कि पहले एन प्राइम नंबरों की सूची तैयार करना; उस फंक्शन पी को फिर से फ़ंक्शन के रूप में परिभाषित किया जा सकता है जो सभी सकारात्मक पूर्णांक की एक सूची उत्पन्न करता है जो किसी भी कम प्राथमिक संख्या द्वारा विभाजित नहीं होते हैं। निश्चित बिंदु पी (1) => 2 एक आधार मामला है जहाँ से पुनरावर्ती एल्गोरिदम परिभाषित किया जा सकता को परिभाषित करता है (नहीं यद्यपि एक बहुत ही कुशल एक):

var curriedLambda = 
      YCombinator.Curry<int, List<int>>(
       (p, i) => i == 1 
           ? new List<int>{2} 
           : p(p, i - 1) 
            .Concat(new[] 
               { 
                Enumerable.Range(p(p, i - 1)[i - 2], 
                    int.MaxValue - p(p, i - 1)[i - 2]) 
                 .First(x => p(p, i - 1).All(y => x%y != 0)) 
               }).ToList() 
       ); 
     Assert.AreEqual(new []{2,3,5,7,11}, curriedLambda(5)); 

और इस तरह पहेली में प्रस्तुत करता है; यद्यपि आप निश्चित रूप से सब कुछ उच्च-आदेश फ़ंक्शन के रूप में परिभाषित कर सकते हैं, लेकिन यह प्राइम-फाइंडर बहुत तेज़ होगा यदि कार्यात्मक रूप से अनिवार्य रूप से परिभाषित किया गया हो। मुख्य गति बस प्रत्येक स्तर पर पी (पी, आई -1) परिभाषित कर रही है, इसलिए इसका मूल्यांकन प्रति बार 3 बार मूल्यांकन नहीं किया जाता है। काम करने के लिए डिज़ाइन की गई एक स्मार्ट भाषा आपके लिए यह करेगी।