मैं वाई-कॉम्बिनेटर को समझ नहीं पाया, इसलिए मैंने इसे लागू करने की कोशिश की और कुछ कम काम किया, जो काम करता था। वो कैसे संभव है?

Question

मैं वाई-संयोजक को समझ नहीं पाया, इसलिए मैंने एक ऐसे क्रिया को कार्यान्वित करने की कोशिश की जो देशी कार्यान्वयन के बिना रिकर्सन सक्षम कर सके। कुछ सोच के बाद, मैं इस के साथ समाप्त हो गया:

Y = λx.(λv.(x x) v) 

कौन सा वास्तविक एक से भी कम है:

Y = λf.(λx.f (x x)) (λx.f (x x)) 

और, मेरे आश्चर्य के लिए, काम किया। कुछ उदाहरण:

// JavaScript 
Y = function(x){ 
    return function(v){ 
    return x(x, v); 
    }; 
}; 
sum = Y(function(f, n){ 
    return n == 0 ? 0 : n + f(f, n - 1); 
}); 
sum(4); 

; Scheme 
(define Y (lambda (x) (lambda (v) (x x v)))) 
(define sum (Y 
    (lambda (f n) 
     (if (equal? n 0) 
      0 
      (+ n (f f (- n 1))))))) 
(sum 4) 

दोनों स्निपेट आउटपुट 10 (0 से 4 तक सारांश) अपेक्षित के रूप में।

यह क्या है, यह छोटा क्यों है और हम लंबे संस्करण को क्यों पसंद करते हैं?

Answer 1

कारण यह छोटा है कि आपने जो लागू किया है वह वाई संयोजन नहीं है। यह कुछ ऐसा है जो वास्तविक वाई संयोजक के बीच है, और ऐसा कुछ जिसे कभी-कभी यू संयोजक के रूप में जाना जाता है। एक उचित Y Combinator हो, यह काम करना चाहिए:

(define sum 
    (Y (lambda (f) 
     (lambda (v) (if (equal? n 0) 0 (+ n (f (- n 1)))))))) 

या जावास्क्रिप्ट में:

sum = Y(function(f) { return function(n) { 
    return n == 0 ? 0 : n + f(n-1); 
};}); 

आप कुछ करता है कि कि काम करने के लिए अपने तरीके से काम करते हैं, तो आप पाएंगे कि एक बात इससे अधिक समय लगेगा कि आपको डुप्लिकेट f चीज को वाई में स्थानांतरित करने की आवश्यकता है, और अगली चीज़ जो इसे और भी अधिक बनाती है, जब आप x x फ़ंक्शन के अंदर स्वयं-एप्लिकेशन की सुरक्षा समाप्त करते हैं क्योंकि ये भाषा सख्त होती है।

Answer 2

"वास्तविक" संस्करण से अंतर यह है कि आपको अपने स्वयं के फ़ंक्शन को पैरामीटर के साथ पास करने की आवश्यकता होती है, जिसे आप आमतौर पर करने की आवश्यकता नहीं रखते हैं - वाई आपके कार्य को अपने आप को रिकर्सिस संस्करण देकर उस पर सार करता है । जावास्क्रिप्ट में

योग सिर्फ

Y (function(rec){ return function (n) { return n==0 ? 0 : n + rec(n-1); };}) 

मैं Y Combinator समझा जब मैं पुनर्गठित common JS expression

function Y (f) { 
    function alt (x) { 
     function rec (y) { // this function is basically equal to Y (f) 
      return x(x)(y); // as x === alt 
     } 
     return f (rec); 
    } 
    return alt(alt); 
}