फ़ंक्शनल प्रोग्रामिंग: फ़ंक्शन, map, filter और fold

फ़ंक्शनल पैराडाइम क्या है?

प्रोग्रामिंग पैराडाइम प्रोग्राम लिखने की एक शैली है। इम्पेरेटिव प्रोग्राम में आप चरण-दर-चरण आदेश देते हैं जो चर (variable) बदलते हैं। फ़ंक्शनल प्रोग्राम में उत्तर को डेटा पर लगाए गए फ़ंक्शनों के रूप में लिखते हैं।

फ़ंक्शन, प्रांत और सह-प्रांत

फ़ंक्शन हर इनपुट को ठीक एक आउटपुट से जोड़ता है। मान्य इनपुटों का समुच्चय प्रांत (domain) है। जिस समुच्चय से आउटपुट आते हैं, वह सह-प्रांत (co-domain) है। फ़ंक्शन type लिखते हैं f: A → B।

उदाहरण: isEven: integer → Boolean। प्रांत = पूर्णांक, सह-प्रांत = {True, False}।

शुद्ध फ़ंक्शन, कोई side effect नहीं

• शुद्ध (pure): एक ही इनपुट पर हमेशा वही आउटपुट।
• कोई side effect नहीं: global चर, फ़ाइल या स्क्रीन नहीं बदलता।
• अपरिवर्तनीय डेटा (immutable): मान बदला नहीं जाता, नया मान बनता है।
• Referential transparency: फ़ंक्शन कॉल की जगह उसका नतीजा रख दें तो प्रोग्राम वैसा ही रहे।

फ़ायदा: कोड जाँचना और सही साबित करना आसान, और कई प्रोसेसरों पर एक साथ चलाना सुरक्षित।

First-class फ़ंक्शन, partial application और composition

First-class फ़ंक्शन

फ़ंक्शन first-class है जब उसे किसी भी मान की तरह इस्तेमाल किया जा सके: नाम देना, argument में देना, नतीजे में लौटाना, सूची में रखना।

Higher-order फ़ंक्शन

जो फ़ंक्शन किसी फ़ंक्शन को argument में ले या लौटाए, वह higher-order है। map, filter, fold ऐसे ही हैं।

Partial application (आंशिक अनुप्रयोग)

add x y = x + y का type integer → (integer → integer) मानिए। सिर्फ़ 5 देने पर नया फ़ंक्शन add5 = add 5 मिलता है, type integer → integer। फिर add5 2 = 7।

Composition (संयोजन)

g ∘ f का अर्थ: पहले f, फिर g: (g ∘ f) x = g(f(x))। अगर f: A → B और g: B → C तो g ∘ f: A → C। f का सह-प्रांत g के प्रांत से मेल खाना चाहिए। क्रम मायने रखता है।

सूची: head, tail और सूची संक्रियाएँ

फ़ंक्शनल भाषाओं में सूची या तो ख़ाली [] होती है, या एक head (पहला सदस्य) जो tail (बाक़ी सदस्यों की सूची) से जुड़ा है।

• head [4,7,9] = 4
• tail [4,7,9] = [7,9]
• tail [9] = []; [] का head त्रुटि है
• आगे जोड़ना (prepend): 2 : [7,9] = [2,7,9]
• पीछे जोड़ना (append): [7,9] ++ [2] = [7,9,2]
• ख़ाली है? null [] = True; लंबाई length [4,7,9] = 3

सूची head + tail है, इसलिए कई फ़ंक्शन रिकर्शन से लिखे जाते हैं: head के साथ कुछ करो, फिर tail पर वही फ़ंक्शन, और ख़ाली सूची पर रुको।

total [] = 0
total (x:xs) = x + total xs

map, filter और fold (reduce)

• map f सूची: हर सदस्य पर f लगाकर उतनी ही लंबी नई सूची। map (*2) [1,2,3] = [2,4,6]।
• filter p सूची: सिर्फ़ वे सदस्य जिन पर जाँच p True हो। filter (>2) [1,2,3,4] = [3,4]।
• fold f शुरुआत सूची (reduce भी कहते हैं): सब सदस्यों को एक मान में मिलाता है। fold (+) 0 [1,2,3] = ((0+1)+2)+3 = 6। fold left बाएँ से, fold right दाएँ से चलता है; घटाने जैसी संक्रिया में फ़र्क़ पड़ता है।

इन्हें जोड़ सकते हैं: [1..6] की सम संख्याओं के वर्गों का योग = fold (+) 0 (map (^2) (filter even [1..6])) = 4 + 16 + 36 = 56।

करके देखें

आख़िरी 3D चरण में map, filter या fold चुनिए और सूची की लंबाई खिसकाइए। पहले ज़ोर से अनुमान बोलिए। फिर Python में आज़माइए: list(map(lambda x: x*3, [1,2,3])), list(filter(lambda x: x%2, [1,2,3,4])) और functools.reduce(lambda a,b: a+b, [1,2,3], 0)।

मुख्य सूत्र और परिभाषाएँ

• फ़ंक्शन type: f: A → B (A = प्रांत, B = सह-प्रांत)
• Composition: (g ∘ f)(x) = g(f(x)); f: A → B और g: B → C से g ∘ f: A → C
• Partial application: add: int → (int → int); add 5 एक फ़ंक्शन int → int है
• map f [x1, …, xn] = [f x1, …, f xn]
• filter p सूची = वे x जिनके लिए p x = True
• fold f a [x1, x2, …, xn] = f(…f(f(a, x1), x2)…, xn)
• सूची = head : tail; head [a,b,c] = a; tail [a,b,c] = [b,c]

हल किए गए उदाहरण

आम गलतियाँ

• यह सोचना कि map सूची की लंबाई बदल सकता है। map हमेशा उतनी ही लंबी सूची देता है; छोटी filter करता है।
• g ∘ f को 'पहले g' पढ़ना। g ∘ f में पहले f लगता है, फिर g।
• tail को आख़िरी सदस्य समझना। tail head के बाद की पूरी सूची है, और हमेशा सूची होती है।
• मान लेना कि शुद्ध फ़ंक्शन print कर सकता है या global चर बदल सकता है। ऐसा करना side effect है, तब वह शुद्ध नहीं रहता।