आप कैसे जानते हैं कि फोल्ड-बाएं का उपयोग कब करें और फोल्ड-राइट का उपयोग कब करें?

Question

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

तो क्या मैं जानना चाहता हूँ है:

• क्या छोड़ दिया गुना या सही गुना करना है कि क्या निर्धारित करने के लिए अंगूठे का कुछ नियम हैं?
• मैं जिस समस्या का सामना कर रहा हूं, उसके बाद मैं किस प्रकार का गुना उपयोग कर सकता हूं?

एक समारोह समतल कहा जाता है जो एक एकल सूची में तत्व सूचियों की एक सूची concatenates लिखने के लिए एक गुना का उपयोग करने का Scala by Example (पीडीएफ) में एक उदाहरण है। उस स्थिति में, एक सही गुना उचित विकल्प है (सूचियों को समेकित करने के तरीके के अनुसार), लेकिन मुझे इस निष्कर्ष पर पहुंचने के लिए थोड़ा सा सोचना पड़ा।

चूंकि फोल्डिंग (कार्यात्मक) प्रोग्रामिंग में ऐसी सामान्य कार्रवाई है, इसलिए मैं इन प्रकार के निर्णयों को जल्दी और आत्मविश्वास से बनाने में सक्षम होना चाहता हूं। तो ... कोई सुझाव?

Answer 1

आप एक इन्फ़िक्स ऑपरेटर अंकन में एक गुना हस्तांतरण कर सकते हैं (बीच में लेखन):

यह उदाहरण संचायक फ़ंक्शन का उपयोग गुना x

fold x [A, B, C, D] 

इस प्रकार के बराबर होती है

A x B x C x D 

आप अब बस अपने ऑपरेटर की सहयोगीता के बारे में कारण होना चाहिए (कोष्ठक डालकर!)।

आप एक बाएं साहचर्य ऑपरेटर है, तो आप कोष्ठकों इस

((A x B) x C) x D 

की तरह यहाँ पर सेट कर देंगे, तो आप एक बाईं गुना का उपयोग करें। उदाहरण (Haskell शैली स्यूडोकोड)

foldl (-) [1, 2, 3] == (1 - 2) - 3 == 1 - 2 - 3 // - is left-associative 

अपने ऑपरेटर को राइट-साहचर्य (सही गुना), कोष्ठक इस तरह निर्धारित किया जाएगा है:

A x (B x (C x D)) 

उदाहरण: विपक्ष-ऑपरेटर

foldr (:) [] [1, 2, 3] == 1 : (2 : (3 : [])) == 1 : 2 : 3 : [] == [1, 2, 3] 

सामान्यतः, अंकगणितीय ऑपरेटरों (अधिकांश ऑपरेटरों) बाएं-सहयोगी होते हैं, इसलिए foldl अधिक व्यापक है। लेकिन अन्य मामलों में, इंफिक्स नोटेशन + कोष्ठक काफी उपयोगी है।

Answer 2

यह भी ध्यान देने योग्य है (और मुझे एहसास है कि यह थोड़ा स्पष्ट बता रहा है), एक कम्यूटेटिव ऑपरेटर के मामले में दोनों काफी समकक्ष हैं।इस स्थिति में एक foldl बेहतर विकल्प हो सकता है:

foldl: (((1 + 2) + 3) + 4) प्रत्येक ऑपरेशन की गणना और संचित मूल्य आगे

foldr ले जा सकता है: (1 + (2 + (3 + 4))) ढेर फ्रेम की जरूरत है की गणना से पहले 1 + ? और 2 + ? के लिए खोले जाने के लिए 3 + 4, तो इसे वापस जाने और प्रत्येक के लिए गणना करने की आवश्यकता है।

मैं यह कहने के लिए कार्यात्मक भाषाओं या कंपाइलर अनुकूलन पर एक विशेषज्ञ के लिए पर्याप्त नहीं हूं कि यह वास्तव में एक अंतर बनायेगा लेकिन यह निश्चित रूप से कम्यूटेटिव ऑपरेटरों के साथ एक फोल्ड का उपयोग करने के लिए क्लीनर लगता है।

Answer 3

Olin Shivers ने कहा कि "फ़ोल्डल मौलिक सूची पुनरावर्तक है" और "फ़ोल्डर मौलिक सूची रिकर्सन ऑपरेटर है।" आप को देखो, तो foldl कैसे काम करता है:

((1 + 2) + 3) + 4 

आप संचायक देख सकते हैं (एक पूंछ पुनरावर्ती यात्रा के रूप में) का निर्माण किया जा रहा है। इसके विपरीत, फ़ोल्डर आय:

1 + (2 + (3 + 4)) 

जहां आप बेस केस 4 के ट्रैवर्सल देख सकते हैं और वहां से परिणाम बना सकते हैं।

तो मैं अंगूठे का नियम मानता हूं: यदि यह एक सूची पुनरावृत्ति की तरह दिखता है, तो पूंछ-पुनरावर्ती रूप में लिखना आसान होगा, फोल्ड जाने का रास्ता है।

लेकिन वास्तव में यह आपके द्वारा उपयोग किए जा रहे ऑपरेटरों की सहयोगीता से सबसे स्पष्ट होगा। यदि वे बाएं-सहयोगी हैं, तो फ़ोल्डल का उपयोग करें। यदि वे सही-सहयोगी हैं, तो फ़ोल्डर का उपयोग करें।

Answer 4

अन्य पोस्टर ने अच्छे उत्तर दिए हैं और मैं जो भी कह चुका हूं उसे दोहराना नहीं चाहूंगा। जैसा कि आपने अपने प्रश्न में एक स्कैला उदाहरण दिया है, मैं एक स्कैला विशिष्ट उदाहरण दूंगा। Tricks के रूप में पहले से ही कहा गया है, foldRight को n-1 स्टैक फ़्रेम को संरक्षित करने की आवश्यकता है, जहां n आपकी सूची की लंबाई है और यह आसानी से एक स्टैक ओवरफ़्लो का कारण बन सकता है - और यहां तक ​​कि पूंछ की पुनरावृत्ति भी आपको इससे बचा सकती है।

एक List(1,2,3).foldRight(0)(_ + _) को कम करेगा करने के लिए:

1 + List(2,3).foldRight(0)(_ + _)  // first stack frame 
    2 + List(3).foldRight(0)(_ + _)  // second stack frame 
     3 + 0       // third stack frame 
// (I don't remember if the JVM allocates space 
// on the stack for the third frame as well) 

जबकि List(1,2,3).foldLeft(0)(_ + _) को कम करेगा:

(((0 + 1) + 2) + 3) 

जो iteratively, के रूप में गणना की जा सकती implementation of List में किया।

स्कैला के रूप में सख्ती से मूल्यांकन की गई भाषा में, foldRight बड़ी सूचियों के लिए आसानी से ढेर को उड़ सकता है, जबकि foldLeft नहीं होगा।

उदाहरण:

scala> List.range(1, 10000).foldLeft(0)(_ + _) 
res1: Int = 49995000 

scala> List.range(1, 10000).foldRight(0)(_ + _) 
java.lang.StackOverflowError 
     at scala.List.foldRight(List.scala:1081) 
     at scala.List.foldRight(List.scala:1081) 
     at scala.List.foldRight(List.scala:1081) 
     at scala.List.foldRight(List.scala:1081) 
     at scala.List.foldRight(List.scala:1081) 
     at scala.List.foldRight(List.scala:1081) 
     at scala.List.foldRight(List.scala:1081) 
     at scala.List.foldRight(List.scala:1081) 
     at scala.List.foldRig...

अंगूठे का मेरा नियम इसलिए है - ऑपरेटरों जो किसी विशेष संबद्धता की जरूरत नहीं है, हमेशा foldLeft का उपयोग करें, कम से कम स्काला में के लिए। अन्यथा, उत्तरों में दी गई अन्य सलाह के साथ जाएं;)।