कृपया सबसे सरल, सबसे शब्दजाल मुक्त अंग्रेजी, "गुना की सार्वभौमिक संपत्ति" में समझाएं?

Question

मैं "रियल वर्ल्ड हास्केल" के माध्यम से काम कर रहा हूं, जिसके कारण "A tutorial on the universality and expressiveness of fold" नामक एक मुफ्त पीडीएफ हुआ। यह मुद्दा बनाता है कि एक "गुना" "सार्वभौमिक" है। मैं "सार्वभौमिक" की परिभाषा के साथ कुश्ती कर रहा हूं, और उन लोगों से सुनना चाहूंगा जिन्होंने पहले ही इसे पचाने का समय निवेश किया है: कृपया सबसे सरल, सबसे शब्दजाल मुक्त अंग्रेजी, "गुना की सार्वभौमिक संपत्ति" में समझाएं? यह "सार्वभौमिक संपत्ति" क्या है, और यह क्यों महत्वपूर्ण है?

धन्यवाद।

Answer 1

(:-)

सार्वभौमिक संपत्ति शब्दजाल मोड बंद सिर्फ साबित करते हुए कि दो भाव बराबर हैं का एक तरीका है। (यही कारण है कि शब्दजाल "सबूत सिद्धांत" का क्या मतलब है है।) सार्वभौमिक संपत्ति का कहना है अगर आप इन दो समीकरणों को साबित करने में सक्षम हैं

g []  = v 
g (x:xs) = f x (g xs) 

तो आप अतिरिक्त समीकरण निष्कर्ष निकाल सकते हैं कि

g = fold f v 

बातचीत भी सच है, लेकिन fold की परिभाषा का विस्तार करके यह दिखाने के लिए तुच्छ है। सार्वभौमिक संपत्ति एक बहुत ही गहरी संपत्ति है (जो यह कहने का एक सौहार्दपूर्ण तरीका है कि यह सच क्यों है।)

कारण यह करना दिलचस्प है कि यह आपको प्रेरण से प्रमाण से बचने देता है, जो कि है लगभग हमेशा से बचने लायक है।

Answer 2

कागज दो गुणों को परिभाषित:

g []  = v 
g (x : xs) = f x (g xs) 

और उसके बाद कहा गया है कि fold न केवल एक समारोह है कि उन गुणों को संतुष्ट करता है, लेकिन केवल समारोह है कि उन गुणों को संतुष्ट करता है। कि उस संबंध में यह अनोखा है कि कागज का उपयोग करने के अर्थ में यह 'सार्वभौमिक' बनाता है।

Answer 3

जो संपत्ति गुना है वह यह है कि यह एक सूची-पुनरावर्ती कार्य है, जो अन्य सभी सूची-पुनरावर्ती कार्यों के बराबर है, बशर्ते आप इसे सही पैरामीटर दें।

इसमें यह संपत्ति है, क्योंकि यह पैरामीटर के रूप में स्वीकार करता है, जो फ़ंक्शंस सूची में आइटम पर लागू होंगे।

उदाहरण के लिए, अगर हम एक सरल योग समारोह लिखा है:

sum []   = 0 
sum (head:tail) = head + (sum tail) 

तो हम वास्तव में यह एक गुना समारोह के बजाय के रूप में, लिख सकता है (+) ऑपरेटर जो हम गठबंधन करने के लिए उपयोग करना चाहते हैं में पारित करके आइटम:

sum list = foldl (+) 0 list 

तो कोई भी फ़ंक्शन जो किसी सूची में आसानी से और पुनरावर्ती रूप से कार्य करता है उसे एक गुना फ़ंक्शन के रूप में पुनः लिखा जा सकता है। वह समानता वह संपत्ति है जो इसे रखती है। मेरा मानना ​​है कि वह संपत्ति सार्वभौमिक कहता है, क्योंकि यह अपवाद के बिना सभी इन रैखिक-सूची-रिकर्सिव एल्गोरिदम पर काम करता है।

और जैसा कि वह बताता है, इस संपत्ति का कारण इतना उपयोगी है, क्योंकि हम इन सभी अन्य एल्गोरिदम वास्तव में गुना के बराबर साबित कर सकते हैं, गुना के बारे में कुछ साबित करके, हम इसे अन्य सभी एल्गोरिदम के लिए भी साबित करते हैं।

मैं व्यक्तिगत रूप से गुना समारोह समझना कठिन पाया, तो कभी कभी मैं अपने खुद के लिए प्रयोग किया जाता है जो इस प्रकार है:

-- forall - A kind of for next loop 
-- list is list of things to loop through 
-- f is function to perform on each thing 
-- c is the function which combines the results of f 
-- e is the thing to combine to when the end of the list is reached 
forall :: [a] -> (a->b) -> (b->b->b) -> b -> b 
forall [] f c e = e 
forall (x:xs) f c e = c (f x) (forall xs f c e) 

(क्योंकि यह लागू करने के अतिरिक्त सुविधा है यह वास्तव में थोड़ा foldl से अधिक शक्तिशाली है सूची में प्रत्येक आइटम को फ़ंक्शन करें।)

अच्छी तरह से मेरे कार्य के बारे में कुछ भी साबित नहीं हुआ। लेकिन उस बात नहीं है, क्योंकि मैं दिखा सकते हैं कि मेरे समारोह एक गुना समारोह वास्तव में है:

forall l f c e = foldl c e (map fn l) 

और इसलिए सभी चीजें हैं जो के बारे में गुना साबित किया गया है, यह भी मेरी forall समारोह के लिए सच साबित हो रहे हैं, और मेरे पूरे कार्यक्रम में इसके सभी उपयोग। (ध्यान दें कि हमें यह भी विचार करने की आवश्यकता नहीं है कि प्रत्येक अलग-अलग कॉल में फोरल और फोल्ड करने के लिए किस प्रकार की फ़ंक्शन सी प्रदान की जाती है, इससे कोई फर्क नहीं पड़ता!)

Answer 4

मुझे अभी विकिपीडिया में एक नया (मेरे लिए) प्रविष्टि मिली है, " सार्वभौमिक संपत्ति "। यह इस सवाल पर प्रकाश का एक टन बहता है। सूची से

1. हालांकि आप एक सूची के माध्यम से चलने के लिए 100 अलग अलग तरीकों से, रास्ते में कंप्यूटिंग के बारे में सोच सकता है, और उत्पादन एक अंतिम मूल्य, सभी 100 की: Here's the link: यह से, मैं (tenatively) निम्नलिखित निष्कर्ष निकालना उन तरीकों isomorphic (जिसका अर्थ है कि अंत में, वे वही हैं)। एक सूची को एक मूल्य में कम करने के लिए वास्तव में केवल एक ही तरीका है, और यह फोल्ड है।
2. फोल्ड एक मूल्य को सूची को कम करने के तरीके के लिए "सबसे कुशल समाधान" भी है। या आप कह सकते हैं, सबसे अधिक "फैक्टर" या सबसे अधिक "सरलीकृत" समाधान।

ऐसा लगता है कि, 2 अंक "सार्वभौमिक संपत्ति" शब्द का अर्थ प्राप्त करते हैं।

Answer 5

हालांकि एक स्पष्ट दृष्टिकोण से सार्वभौमिक गुणों को समझाते हुए श्रृंखला में पिछली पोस्ट पढ़ने के बिना इसका पालन करना थोड़ा मुश्किल हो सकता है, यह पोस्ट गुना की सार्वभौमिक संपत्ति, साथ ही नक्शा और फ़िल्टर की एक विस्तृत स्पष्ट व्याख्या प्रदान करता है।

http://jeremykun.com/2013/09/30/the-universal-properties-of-map-fold-and-filter/

हालांकि मैं यह लिखने के लिए अभी तक है, फॉलोअप इस सामान्यीकरण (और यह बहुत सरल समझने के लिए, और अधिक सार यद्यपि बनाना) सामान्य डेटा संरचनाओं पर करने के लिए "गुना की तरह" संचालन होगा।

क्या एक सार्वभौमिक संपत्ति है के बारे में अधिक के लिए यह पोस्ट देखें: http://jeremykun.com/2013/05/24/universal-properties/

और यहाँ श्रृंखला में सभी पोस्ट के लिंक के लिए: http://jeremykun.com/main-content/

सच में, वर्तमान में स्वीकार जवाब समझने के लिए सबसे आसान तरीका है गुना के बारे में सार्वभौमिक संपत्ति क्या कह रही है। ऊपर से जुड़े लेख केवल श्रेणी सिद्धांत के माध्यम से एक और विस्तृत तकनीकी विवरण देते हैं जो प्रश्न में पेपर से अनुपस्थित है। मैं स्वीकार किए गए उत्तर में बयान से असहमत हूं, हालांकि, सार्वभौमिक संपत्ति शब्दावली मुक्त कथन की तुलना में बहुत गहरी संपत्ति है। गुना की सार्वभौमिक संपत्ति ठीक वही कथन है, जो कि श्रेणी सिद्धांत के साथ चीजों का विश्लेषण करने की प्रकृति के अनुसार प्रारंभिक और अंतिम वस्तुओं की भाषा में बस बनी हुई है। यह विश्लेषण अपने प्राकृतिक सामान्यीकरण के कारण मूल्यवान है।