क्या कार्यात्मक प्रोग्रामिंग में "एल्गोरिदम" मौजूद है?

Question

क्या यह आपके सॉफ़्टवेयर के "एल्गोरिदम" दस्तावेज़ (कहने के लिए, एक डिज़ाइन विनिर्देशन में) कहने के लिए कहने के लिए व्यर्थ है यदि यह कार्यात्मक प्रतिमान में लागू किया गया है? जब भी मैं तकनीकी दस्तावेजों में एल्गोरिदम के बारे में सोचता हूं, मैं अनुक्रमिक चरणों के समूह के साथ थोड़ी देर लूप की कल्पना करता हूं।

एक एल्गोरिथ्म के अनौपचारिक शब्दकोश अर्थ को देखते हुए:

गणित और कंप्यूटर विज्ञान में, एक एल्गोरिथ्म की गणना के लिए एक कदम-दर-कदम प्रक्रिया है।

वाक्यांश "कदम-दर-कदम" (मैं यह समझ के रूप में), क्योंकि कार्यात्मक कार्यक्रम, इसके विपरीत में कार्यक्रमों अनिवार्य करने के लिए कार्यात्मक प्रोग्रामिंग के प्रतिमान के खिलाफ प्रतीत होता है, में समय का कोई जागरूकता उनके hypothetical मशीन। क्या यह तर्क सही है? या आलसी मूल्यांकन एक अंतर्निहित समय घटक लागू करता है जो इसे "चरण-दर-चरण" बनाता है?

संपादित करें -। इतने सारे अच्छे जवाब, यह अनुचित है मुझे सभी दृष्टिकोणों के लिए एक सबसे अच्छी प्रतिक्रिया :(धन्यवाद का चयन करने के लिए, वे सभी महान अवलोकन करें

Answer 1

हां, एल्गोरिदम अभी भी कार्यात्मक भाषाओं में मौजूद हैं, हालांकि वे हमेशा अनिवार्य लोगों के समान दिखते नहीं हैं।

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

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

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

factorial n = product [1..n] 

यह दो से बना भागों है: पहला, हम एक सूची उत्पन्न 1n के लिए और फिर से हम इसे गुणा (product) द्वारा गुना। लेकिन, आलस्य के लिए धन्यवाद, सूची पूरी तरह से स्मृति में मौजूद नहीं है! हम पैदा समारोह के रूप में ज्यादा का मूल्यांकन के रूप में हम product के प्रत्येक चरण पर की जरूरत है, और कचरा कलेक्टर के रूप में हम उन लोगों के साथ काम हो गया पुराने कोशिकाओं reclaims। तो भी इस हालांकि लगता है कि यह O(n) स्मृति की आवश्यकता होगी, यह वास्तव में O(1) साथ दूर हो जाता है। (ठीक है, मानते हैं कि सभी संख्या O(1) मेमोरी लेते हैं।)

इस मामले में, एल्गोरिदम की "संरचना", चरणों का क्रम, सूची संरचना द्वारा प्रदान की जाती है। यहां सूची एक वास्तविक सूची की तुलना में फॉर-लूप के करीब है!

तो कार्यात्मक प्रोग्रामिंग में, हम कुछ अलग-अलग तरीकों से चरणों के अनुक्रम के रूप में एक एल्गोरिदम बना सकते हैं: ट्रांसफॉर्मेशन (शायद सामान्य उच्च-आदेश कार्यों के आधार पर) या मध्यवर्ती डेटा संरचनाओं को बनाकर और उपभोग करके प्रत्यक्ष रिकर्सन द्वारा lazily।

(define (make-list num) 
    (let loop ((x num) (acc '())) 
    (if (zero? x) 
     acc 
     (loop (- x 1) (cons x acc))))) 

(make-list 5)   ; dumb compilers might do this 
(display (make-list 10)) ; force making a list (because we display it) 

अपने तर्क के साथ

make-list एक एल्गोरिथ्म के बाद से यह यह चरणों में गणना है ऐसा नहीं करता विचार नहीं किया जाएगा, लेकिन यह वास्तव में सच है:

Answer 2

मुझे लगता है कि आप कार्यात्मक प्रोग्रामिंग प्रतिमान गलतफहमी हो सकती है

चाहे आप एक कार्यात्मक भाषा (लिस्प, एमएल, हास्केल) या एक अनिवार्य/प्रक्रियात्मक एक (सी/जावा/पायथन) का उपयोग करें, आप संचालन और उनके आदेश को निर्दिष्ट कर रहे हैं (कभी-कभी ऑर्डर निर्दिष्ट नहीं किया जा सकता है, लेकिन यह एक पक्ष मुद्दा है)

कार्यात्मक प्रतिमान कुछ भी सीमा निर्धारित करता है जो आप कर सकते हैं (उदाहरण के लिए, कोई दुष्प्रभाव नहीं), जिससे कोड के बारे में तर्क करना आसान हो जाता है (और, संयोग से, "पर्याप्त रूप से स्मार्ट कंपाइलर" लिखना आसान होता है)।

पर विचार करें, उदाहरण के लिए, भाज्य का एक कार्यात्मक कार्यान्वयन:

(defun ! (n) 
    (if (zerop n) 
     1 
     (* n (! (1- n))))) 

एक बार आसानी से निष्पादन के आदेश देख सकते हैं: n-1 गुणा और तर्क n के लिए subtractions देखते हैं कि 1 * 2 * 3 * .... * n और तथ्य यह है।

कंप्यूटर विज्ञान का सबसे महत्वपूर्ण हिस्सा याद रखना है कि भाषा केवल कंप्यूटर से बात करने का माध्यम है। सीएस कंप्यूटर के बारे में है, खगोल विज्ञान से दूर टेलीस्कोप के बारे में नहीं है, और एल्गोरिदम को एक अमूर्त (ट्यूरिंग) मशीन पर निष्पादित किया जाना है, जो हमारे सामने वास्तविक बॉक्स द्वारा अनुकरण किया जाता है।

Answer 3

नहीं, मुझे लगता है कि अगर आपने कोई समस्या हल की है और आपने इसे अनिवार्य रूप से हल किया है, तो आप दो अलग-अलग एल्गोरिदम हैं। प्रत्येक एक एल्गोरिदम है। एक एक कार्यात्मक एल्गोरिदम है और एक अनिवार्य एल्गोरिदम है। कार्यात्मक प्रोग्रामिंग भाषाओं में एल्गोरिदम के बारे में कई किताबें हैं।

ऐसा लगता है कि आप यहां तकनीकी/अर्थशास्त्र में पकड़े जा रहे हैं। यदि आपको किसी समस्या को हल करने के लिए एल्गोरिदम दस्तावेज करने के लिए कहा जाता है, तो जो भी आपको पूछता है कि आप यह जानना चाहते हैं कि आप समस्या को कैसे हल कर रहे हैं। यहां तक ​​कि यदि इसके कार्यात्मक, समाधान तक पहुंचने के लिए कदमों की श्रृंखला भी होगी (यहां तक ​​कि सभी आलसी मूल्यांकन के साथ)। यदि आप समाधान तक पहुंचने के लिए कोड लिख सकते हैं, तो आप छद्म कोड में कोड लिख सकते हैं, जिसका अर्थ है कि आप जहां तक ​​चिंतित हैं, एल्गोरिदम के संदर्भ में कोड लिख सकते हैं।

और, के बाद से ऐसा लगता है तुम बहुत यहाँ परिभाषा पर लटका दिया जा रहा है, मैं एक सवाल अपने तरीके से कि मेरी बात साबित होता मानना ​​होगा। प्रोग्रामिंग भाषाएं, चाहे कार्यात्मक या अनिवार्य, आखिरकार मशीन पर चलती हैं। सही? आपके कंप्यूटर को चलाने के लिए निम्न स्तर के निर्देशों के चरण-दर-चरण प्रक्रिया को बताया जाना चाहिए। यदि यह कथन सत्य है, तो प्रत्येक उच्च स्तरीय कंप्यूटर प्रोग्राम को उनके निम्न स्तर के निर्देशों के संदर्भ में वर्णित किया जा सकता है। इसलिए, प्रत्येक कार्यक्रम, चाहे कार्यात्मक या अनिवार्य, एक एल्गोरिदम द्वारा वर्णित किया जा सकता है। और यदि आपको उच्च स्तरीय एल्गोरिदम का वर्णन करने का कोई तरीका नहीं मिल रहा है, तो बाइटकोड/असेंबली आउटपुट करें और इन निर्देशों के संदर्भ में अपने एल्गोरिदम को समझाएं

Answer 4

इस कार्यात्मक योजना उदाहरण पर विचार करें?

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

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