सूची फ़ैक्टर नोडेटर्मेनिस्टिक विकल्प के संदर्भ का प्रतिनिधित्व क्यों करता है?

Question

इस उद्धरण का क्या अर्थ है?

the list functor represents a context of nondeterministic choice; 

कार्यात्मक प्रोग्रामिंग में फंक्चर के संदर्भ में।

मुझे लगता है कि मैं समझता हूं कि एक फंक्शन एक प्रकार का "कंटेनर" है जिसमें संरचना को बदलने के बिना कंटेनर में तत्वों को समान रूप से फ़ंक्शन लागू करने की क्षमता होती है। तो शायद एक फंक्चर है जो संभावित विफलता के साथ एक संदर्भ या कंटेनर का प्रतिनिधित्व करता है, लेकिन सूची नोडेटर्मेनिस्टिक विकल्प के साथ संदर्भ या कंटेनर का प्रतिनिधित्व क्यों करती है?

Answer 1

जितना मैं कह सकता हूं उतना ही, गणना "नोडेटर्मिनिस्टिक" है यदि उसके पास कई संभावित उत्तर हैं। खैर, एक सूची में कई संभावित उत्तर हो सकते हैं। इसलिये।

(के रूप में करने के लिए कारण है कि यह गैर नियतात्मक कहा जाता है, मुझे पता नहीं है ... मैं गैर नियतात्मक की उम्मीद है | यादृच्छिक, जो कुछ अलग है मतलब करने के लिए।)

Answer 2

"शास्त्रीय" संगणना 1 इनपुट लेने के लिए और देना 1 आउटपुट आप इन गैर-निर्धारिती गणनाओं के साथ क्या प्रतिनिधित्व करना चाहते हैं: अगर मैं इनपुट के बारे में निश्चित नहीं हूं तो आउटपुट के बारे में मैं क्या कह सकता हूं? अनिश्चितता का प्रतिनिधित्व करने के

दो सामान्य तरीकों पर विचार करना है:

1. कि इनपुट का एक तत्व है एक दिया
2. सेट है कि इनपुट एक ज्ञात संभावना वितरण द्वारा दिया जाता है

उदाहरण के तौर पर, फ़ंक्शन (2 *) पर विचार करें जो इनपुट को दोगुना करता है। इनपुट के मरने के परिणाम होने पर आप उस फ़ंक्शन के आउटपुट के बारे में क्या कह सकते हैं?

1. मैं जानता हूँ कि मरने 6 चेहरे है तो परिणाम सेट में है {} 2,4,6,8,10,12
2. मैं हर चेहरे की संभावनाओं को पता है 1/6 तो मैं जानता हूँ कि है कि इनमें से प्रत्येक संख्या में

सूची फ़ैक्टर 1 की भावना में गैर-निर्धारक गणनाओं का प्रतिनिधित्व करता है .: यह सूचियों द्वारा सेट का प्रतिनिधित्व करता है।

foo = do 
    x <- [1 .. 10] 
    y <- [2, 3, 5, 7] 
    return (x * y) 

क्या foo है:

Answer 3

निम्नलिखित पर विचार करें? खैर, यह, x * y है x 1 से 10 के एक नंबर जा रहा है, और y 5, या 7. जा रहा है या तो 2, 3, इसलिए की गैर नियतात्मक विकल्पों के साथ छोड़कर, foo कम्प्यूटेबिलिटी और जटिलता में [2, 3, 5, 7, 4, 6, 10, 14, etc... ]

Answer 4

परंपरागत रूप से है, एक नोडेटर्मिनिस्टिक गणना मॉडल ने एक मॉडल को संदर्भित किया है जिसमें आप "शाखा" कर सकते हैं।

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

सूची मोनाड में, यह वही है जो आप कर रहे हैं। उदाहरण के लिए, सूची इकाई में, clique problem के निर्णय संस्करण के लिए इस समाधान पर विचार करें:

cliques :: Int -> Graph -> [[Node]] 
cliques 0 _ = [[]] 
cliques minCliqueSize graph = do 
    v <- nodes graph 
    vs <- cliques (minCliqueSize - 1) (deleteNode v graph) 
    mapM_ (\ w -> guard (isAdjacent v w graph)) vs 
    return (v:vs) 

यह ठीक है कि कैसे आप जैसे कार्यक्रम था क्लिक्स समस्या को हल करने के लिए एक नोडेटर्मिनिस्टिक ट्यूरिंग मशीन।

Answer 5

एक कंटेनर के रूप में एक मजेदार देखने के अलावा, आप इसे एक निश्चित प्रकार के संदर्भ के रूप में भी देख सकते हैं। आपके मान उस संदर्भ में हैं, और यदि आप उन पर काम करना चाहते हैं, तो आप संदर्भ में फ़ंक्शन उठाने के लिए map का उपयोग करते हैं। इसे डालने का एक और तरीका यह है कि आपके मान उस संदर्भ के साथ बढ़ाए गए हैं।

यह समझने के लिए कि कैसे सूची फ़ैक्टर नोडेटर्मेनिस्टिक पसंद का संदर्भ है, यह देखने के लिए उपयोगी हो सकता है कि एक और मज़ेदार कैसे एक संदर्भ है: शायद मज़ेदार एक गणना का संदर्भ है जो असफल हो सकता है। यदि आप किसी फंक्शन में किसी फ़ंक्शन को फ़ंक्शन लागू करने का प्रयास करते हैं, तो परिणामी मान अभी भी वही संदर्भ रखेगा चाहे वह पहले स्थान पर असफल गणना हो या नहीं।

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

दान Burtons जवाब से थोड़ा उधार, सूचियों के लिए monadic अंकन को देखो:

foo = do 
    x <- [1 .. 10] 
    y <- [2, 3, 5, 7] 
    return (x * y) 

यह पहले थोड़ा अजीब लगता है पर जब से अंकन में इंगित करता है, कि आप से एक मान निकाल सकते प्रत्येक सूची में, लेकिन फिर आप परिणामस्वरूप एक सूची प्राप्त करते हैं जो 40 तत्व लंबा है। जब आप एक मूल्य के संदर्भ के रूप में फ़ैक्टर (अच्छी तरह से, इस मामले में monads) को देखते हैं तो यह अधिक समझ में आता है। उदाहरण में, x और y ऐसे मूल्य हैं, लेकिन उनका संदर्भ यह है कि वे nondeterministic हैं। जब आप दो ऐसे मानों को गुणा करते हैं, तो आपको और अधिक नोडेटर्मिनिज्म मिलता है, जिसके परिणामस्वरूप लंबी सूची होती है। तो monads और >>= के साथ, संदर्भ बदला जा सकता है, जबकि functors और map के साथ, यह नहीं कर सकता।