फ़ोल्ड राइट का उपयोग कर सूची को रिवर्स करने का सुरुचिपूर्ण तरीका?

Question

मैं Programming in Scala पुस्तक में गुना तकनीकों के बारे में पढ़ रहा था और इस स्निपेट में आए:

def reverseLeft[T](xs:List[T]) = (List[T]() /: xs) { 
    (y,ys) => ys :: y 
} 

आप देख सकते हैं, यह foldLeft या /: ऑपरेटर का उपयोग किया गया था। जिज्ञासु इसे पसंद करता है, तो मैं इसे :\ का उपयोग कर किया था इस तरह दिखाई देंगे, मैं इस के साथ आया था:

def reverseRight[T](xs:List[T]) = (xs :\ List[T]()) { 
    (y,ys) => ys ::: List(y) 
} 

मैं यह समझ के रूप में, ::: के रूप में तेजी से :: के रूप में होना करने के लिए प्रतीत नहीं होता है और एक रेखीय लागत के आधार पर किया गया है ऑपरेंड सूची का आकार। माना जाता है कि मेरे पास सीएस में कोई पृष्ठभूमि नहीं है और कोई पूर्व एफपी अनुभव नहीं है। तो मेरे प्रश्न हैं:

• समस्या दृष्टिकोण में foldLeft/foldRight के बीच आप कैसे पहचान/अंतर करते हैं?
• ::: का उपयोग किये बिना ऐसा करने का कोई बेहतर तरीका है? एक सूची

Answer 1

मानक पुस्तकालय में List पर foldRight पर रैखिक रिकर्सन का उपयोग करके सख्त और कार्यान्वित किया गया है, तो आपको इसे नियम के रूप में उपयोग करने से बचना चाहिए। foldRight का एक पुनरावृत्ति कार्यान्वयन के रूप में किया जाएगा इस प्रकार है:

def foldLeft[A,B](f: (B, A) => B, z: B, xs: List[A]) = 
    xs.reverse.foldRight(z)((x, y) => f(y, x)) 

तो आप देखते हैं, अगर दोनों सख्त, तो इनमें से एक या अन्य कर रहे हैं:

def foldRight[A,B](f: (A, B) => B, z: B, xs: List[A]) = 
    xs.reverse.foldLeft(z)((x, y) => f(y, x)) 

foldLeft की एक पुनरावर्ती कार्यान्वयन इस हो सकता है reverse के साथ foldRight और foldLeft लागू किया जा रहा है (अवधारणा वैसे भी)। चूंकि सूचियां :: सहयोगियों के साथ दायीं तरफ बनाई गई हैं, सीधी तरफ इटेटिव फोल्ड foldLeft होने जा रहा है, और foldRight बस "फोल्ड लेफ्ट" रिवर्स है।

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

1. "दो बार" एक निरंतर कारक है, इसलिए यह एक बार फोल्डिंग के बराबर है।
2. आपको सूची में दो बार वैसे भी जाना है। एक बार ढेर पर computations धक्का और फिर उन्हें ढेर से पॉप करने के लिए।
3. उपरोक्त foldRight का कार्यान्वयन मानक पुस्तकालय में से एक की तुलना में तेज़ है।

Answer 2

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

::: ऑपरेटर जो सूची के अंत में एक नया तत्व जोड़ता है उसे पूरी सूची की एक नई प्रतिलिपि बनाना है, अन्यथा यह उन अन्य सूचियों को संशोधित करेगा जो आपके द्वारा संलग्न की जा रही सूची के साथ नोड साझा करते हैं। यही कारण है कि ::: रैखिक समय लेता है। स्कैला में एक डेटा संरचना है जिसे ListBuffer कहा जाता है जिसे आप ::: ऑपरेटर के बजाय एक सूची के अंत में तेजी से जोड़ने के लिए उपयोग कर सकते हैं। असल में, आप एक नया ListBuffer बनाते हैं और यह एक खाली सूची से शुरू होता है। ListBuffer प्रोग्राम को किसी भी अन्य सूची से पूरी तरह से अलग सूची बनाए रखता है, इसलिए अंत में जोड़कर इसे संशोधित करना सुरक्षित है। जब आप अंत में जोड़ना समाप्त कर लेंगे, तो आप ListBuffer.toList पर कॉल करें, जो दुनिया में सूची जारी करता है, जिस बिंदु पर आप इसे कॉपी किए बिना अंत में जोड़ सकते हैं।

foldLeft और foldRight भी एक समान असमानता साझा करते हैं। foldRight आपको सूची के अंत तक पहुंचने के लिए पूरी सूची में जाने की आवश्यकता है, और वहां आप जिस तरह से गए हैं, उसका ट्रैक रखें, ताकि आप उन्हें रिवर्स ऑर्डर में देख सकें। यह आमतौर पर बार-बार किया जाता है, और इससे foldRight तक बड़ी सूचियों पर स्टैक ओवरफ्लो हो सकता है। दूसरी तरफ foldLeft, सूची में दिखाई देने वाले क्रम में नोड्स से संबंधित है, इसलिए यह उन लोगों को भूल सकता है जिन्हें पहले से देखा गया है और केवल एक समय में एक नोड के बारे में जानना आवश्यक है। हालांकि foldLeft भी आम तौर पर रिकर्सिवली कार्यान्वित किया जाता है, यह एक अनुकूलन कहा पूंछ प्रत्यावर्तन उन्मूलन, जिसमें संकलक एक पाश में पुनरावर्ती कॉल बदल देती समारोह पुनरावर्ती कॉल से लौटने के बाद कुछ भी नहीं है, क्योंकि का लाभ ले सकते। इस प्रकार, foldLeft बहुत लंबी सूचियों पर भी ढेर को ओवरफ़्लो नहीं करता है। EDIT: foldRight स्कैला 2 में।8 वास्तव में सूची को उलटकर और foldLeft को उलट सूची पर चलाकर कार्यान्वित किया जाता है - इसलिए पूंछ रिकर्सन मुद्दा कोई मुद्दा नहीं है - दोनों डेटा संरचनाएं पूंछ रिकर्सन को सही ढंग से अनुकूलित करती हैं, और आप या तो एक चुन सकते हैं (अब आप इस मुद्दे में शामिल हैं कि आप reversereverse के संदर्भ में परिभाषित कर रहे हैं - यदि आप अपने अपने इसके मजे के लिए रिवर्स विधि को परिभाषित कर रहे हैं, तो आपको चिंता करने की आवश्यकता नहीं है, लेकिन अगर आप थे तो फ़ोल्ड राइट विकल्प नहीं होगा स्काला के रिवर्स विधि को परिभाषित।)

इस प्रकार, आप foldRight और ::: से अधिक foldLeft और :: को प्राथमिकता देनी चाहिए।

(। एक एल्गोरिथ्म है कि :: साथ ::: या foldRight साथ foldLeft गठबंधन आरंभ करेगा, तो आप अपने लिए एक निर्णय करने के लिए के बारे में जो ज्यादा महत्वपूर्ण है की जरूरत है:। स्टैक स्थान या समय से चल रहा है या आप एक ListBuffer साथ foldLeft का उपयोग करना चाहिए)