"कॉम्बिनेटर्स" (गैर गणितज्ञों के लिए) की अच्छी व्याख्या

Question

किसी को भी "संयोजक" (वाई-संयोजक आदि) और the company) का अच्छा स्पष्टीकरण मिला है?

मैं व्यावहारिक प्रोग्रामर के लिए एक की तलाश कर रहा हूं जो रिकर्सन और उच्च-आदेश कार्यों को समझता है, लेकिन इसमें मजबूत सिद्धांत या गणित पृष्ठभूमि नहीं है।

(नोट: यह है कि मैं these things के बारे में बात कर रहा हूँ)

Answer 1

यह एक अच्छा article है। कोड उदाहरण योजना में हैं, लेकिन उन्हें पालन करना मुश्किल नहीं होना चाहिए।

Answer 2

जब तक आप सिद्धांत में गहराई से न हों, तो आप वाई संयोजक पर मोनैड जैसे फ़ंक्शंस के साथ एक साफ चाल के रूप में देख सकते हैं।

मोनाड्स आपको चेन क्रियाओं की अनुमति देता है, वाई संयोजक आपको स्वयं-पुनरावर्ती कार्यों को परिभाषित करने की अनुमति देता है।

पायथन अंतर्निहित स्वयं पुनरावर्ती कार्यों के लिए समर्थन है, तो आप वाई बिना उन्हें परिभाषित कर सकते हैं:

> def fun(): 
> print "bla" 
> fun() 

> fun() 
bla 
bla 
bla 
... 

funfun ही अंदर पहुंचा जा सकता है, तो हम आसानी से यह कह सकते हैं।

लेकिन क्या होगा अगर अजगर अलग थे, और fun fun अंदर पहुंच में नहीं थे?

> def fun(): 
> print "bla" 
> # what to do here? (cannot call fun!) 

समाधान fun ही एक तर्क के रूप fun को पारित करने के लिए है:

> def fun(arg): # fun receives itself as argument 
> print "bla" 
> arg(arg) # to recur, fun calls itself, and passes itself along 

और वाई संभव है कि बनाता है:

> def Y(f): 
> f(f) 

> Y(fun) 
bla 
bla 
bla 
... 

सभी इसे एक समारोह के साथ ही फोन करता है तर्क के रूप में।

(यदि Y की इस परिभाषा 100% सही है मैं नहीं पता है, लेकिन मुझे लगता है कि यह सामान्य विचार है।)

Answer 3

रेजिनाल्ड ब्रेथवेट (उर्फ Raganwald) पर रूबी में combinators पर एक बड़ा श्रृंखला लिख ​​कर दिया गया है अपने नए ब्लॉग पर, homoiconic।

जबकि वह (मेरी जानकारी के लिए) वाई Combinator में ही नहीं लगती है, वह अन्य combinators पर देखने के उदाहरण के लिए करता है:

• Kestrel
• Thrush
• Cardinal
• Obdurate Kestrel
• अन्य क्विर्की पक्षी

और canuse पर कुछ पोस्ट्स पर कुछ पोस्ट।

Answer 4

मैं सिद्धांत पर बहुत छोटा हूं, लेकिन मैं आपको एक उदाहरण दे सकता हूं जो मेरी कल्पना को रोकता है, जो आपके लिए उपयोगी हो सकता है। सबसे सरल दिलचस्प संयोजन शायद "परीक्षण" है। अन्यथा तीसरे,

>>> test(tru,"goto loop","break") 
'goto loop' 
>>> test(fls,"goto loop","break") 
'break' 

परीक्षण दूसरा तर्क का मूल्यांकन करता है, तो पहला तर्क सही है:

आशा है कि आप जानते हैं कि अजगर

tru = lambda x,y: x 
fls = lambda x,y: y 

test = lambda l,m,n: l(m,n) 

प्रयोग।

>>> x = tru 
>>> test(x,"goto loop","break") 
'goto loop' 

संपूर्ण सिस्टम कुछ बुनियादी संयोजकों से बनाया जा सकता है।

Answer 5

उद्धरण विकिपीडिया (इस उदाहरण और अधिक या कम के प्रकार और बेंजामिन सी पियर्स द्वारा प्रोग्रामिंग भाषाएं से बाहर नकल की जाती है):

एक Combinator एक उच्च क्रम समारोह केवल समारोह आवेदन का उपयोग करता है और पहले परिभाषित संयोजकों को इसके तर्कों से परिणाम परिभाषित करने के लिए परिभाषित किया गया था।

अब इसका क्या अर्थ है? इसका मतलब है कि एक संयोजक एक कार्य है (आउटपुट पूरी तरह से इसके इनपुट द्वारा निर्धारित किया जाता है) जिसका इनपुट एक फ़ंक्शन को तर्क के रूप में शामिल करता है।

ऐसे कार्य क्या दिखते हैं और उनका उपयोग किस प्रकार किया जाता है? यहाँ कुछ उदाहरण हैं:

(f o g)(x) = f(g(x))

यहाँ o एक Combinator कि 2 काम करता है, f और g में लेता है, और उसके परिणाम, g, अर्थात् f o g साथ f की संरचना के रूप में एक समारोह देता है।

तर्क को छिपाने के लिए कॉम्बिनेटर्स का उपयोग किया जा सकता है। मान लें कि हमारे पास डेटा प्रकार NumberUndefined है, जहां NumberUndefined संख्यात्मक मान Num x या एक मान Undefined पर ले सकता है, जहां x a Number है। अब हम इस नए संख्यात्मक प्रकार के लिए अतिरिक्त, घटाव, गुणा, और विभाजन बनाना चाहते हैं। अर्थशास्त्र Number के समान हैं, सिवाय Undefined एक इनपुट है, आउटपुट Undefined भी होना चाहिए और 0 संख्या से विभाजित होने पर आउटपुट भी Undefined है।

Undefined +' num = Undefined 
num +' Undefined = Undefined 
(Num x) +' (Num y) = Num (x + y) 

Undefined -' num = Undefined 
num -' Undefined = Undefined 
(Num x) -' (Num y) = Num (x - y) 

Undefined *' num = Undefined 
num *' Undefined = Undefined 
(Num x) *' (Num y) = Num (x * y) 

Undefined /' num = Undefined 
num /' Undefined = Undefined 
(Num x) /' (Num y) = if y == 0 then Undefined else Num (x/y) 

सूचना कैसे सब Undefined इनपुट मानों के विषय में एक ही तर्क है:

एक के रूप में नीचे थकाऊ कोड लिख सकते हैं। केवल विभाजन थोड़ा और करता है। समाधान इसे एक संयोजक बनाकर तर्क निकालना है।

comb (~) Undefined num = Undefined 
comb (~) num Undefined = Undefined 
comb (~) (Num x) (Num y) = Num (x ~ y) 

x +' y = comb (+) x y 
x -' y = comb (-) x y 
x *' y = comb (*) x y 
x /' y = if y == Num 0 then Undefined else comb (/) x y 

यह तथाकथित Maybe इकाई है कि प्रोग्रामर हास्केल तरह कार्यात्मक भाषाओं में का उपयोग करने में सामान्यीकृत किया जा सकता है, लेकिन मैं वहाँ नहीं जाना होगा।

Answer 6

संक्षेप में, वाई संयोजक एक उच्च आदेश फ़ंक्शन है जिसका प्रयोग लैम्ब्डा अभिव्यक्तियों (अज्ञात कार्यों) पर पुनरावर्तन को लागू करने के लिए किया जाता है। माइक वैनेयर द्वारा आलेख How to Succeed at Recursion Without Really Recursing पर आलेख देखें - यह मैंने देखा है इस मामले का सबसे अच्छा व्यावहारिक स्पष्टीकरण है।

इसके अलावा, स्कैन, इसलिए ऐसे संग्रह:

• What is a y-combinator?
• Y-Combinator Practical Example

Answer 7

एक Combinator कोई मुफ्त चर साथ कार्य है। इसका मतलब है कि, अन्य चीजों के साथ, संयोजक के पास फ़ंक्शन के बाहर की चीज़ों पर निर्भरता नहीं होती है, केवल फ़ंक्शन पैरामीटर पर।

let sum a b = a + b;; //sum function (lambda) 

उपरोक्त मामले संक्षेप में एक Combinator क्योंकि a और b दोनों फ़ंक्शन पैरामीटर करने के लिए बाध्य कर रहे हैं:

एफ # का उपयोग करते हुए इस combinators की मेरी समझ है।

let sum3 a b c = sum((sum a b) c);; 

ऊपर समारोह नहीं एक Combinator के रूप में यह sum का उपयोग करता है, जो एक बाध्य चर (यानी यह पैरामीटर के किसी भी से नहीं आती है) नहीं है।

हम तो बस एक पैरामीटर के रूप में योग समारोह पारित करके sum3 एक Combinator बना सकते हैं:

let sum3 a b c sumFunc = sumFunc((sumFunc a b) c);; 

इस तरह sumFunc बाध्य है और इसलिए पूरे समारोह एक Combinator है।

तो, यह संयोजकों की मेरी समझ है। दूसरी ओर, उनका महत्व, अभी भी मुझसे बच निकला है। जैसा कि अन्य ने बताया, निश्चित बिंदु संयोजक explicit रिकर्सन के बिना एक रिकर्सिव फ़ंक्शन व्यक्त करने की अनुमति देते हैं। अर्थात। खुद को कॉल करने के बजाए रिकर्ससिव फ़ंक्शन लैम्ब्डा को कॉल करता है जिसे तर्कों में से एक के रूप में पारित किया जाता है।

यहां सबसे समझा जा सकता Combinator derivations कि मैंने पाया में से एक है:

http://mvanier.livejournal.com/2897.html

Answer 8

यह एक अच्छा एक दिखता है: http://www.catonmat.net/blog/derivation-of-ycombinator/