यह रिकर्सिव सूची कैसे काम करता है?

Question

कुछ समय पहले this was asked and answered स्काला मेलिंग सूची पर:

केविन:

को देखते हुए कुछ आंतरिक संरचना: List[List[...List[T]]] क्या सबसे अच्छा (अधिमानतः टाइप-सुरक्षित) जिस तरह से एक List[T]

करने के लिए इसे समतल करने के लिए

जेस्पर:

impl का एक संयोजन icits और डिफ़ॉल्ट तर्क काम करता है:

case class Flat[T, U](fn : T => List[U]) 

implicit def recFlattenFn[T, U](implicit f : Flat[T, U] = Flat((l : T) 
=> List(l))) = 
    Flat((l : List[T]) => l.flatMap(f.fn)) 

def recFlatten[T, U](l : List[T])(implicit f : Flat[List[T], U]) = f.fn(l) 

उदाहरण:

scala> recFlatten(List(1, 2, 3)) 
res0: List[Int] = List(1, 2, 3) 

scala> recFlatten(List(List(1, 2, 3), List(4, 5))) 
res1: List[Int] = List(1, 2, 3, 4, 5) 

scala> recFlatten(List(List(List(1, 2, 3), List(4, 5)), List(List(6, 7)))) 
res2: List[Int] = List(1, 2, 3, 4, 5, 6, 7) 

मैं थोड़ी देर के लिए इस कोड को देखकर किया गया है। मैं यह नहीं समझ सकता कि यह कैसे काम करता है। ऐसा लगता है कि कुछ रिकर्सन शामिल है ... क्या कोई कुछ प्रकाश डाल सकता है? क्या इस पैटर्न के अन्य उदाहरण हैं और क्या इसका नाम है?

Answer 1

ओह वाह, यह एक पुराना है! मैं कोड थोड़ा सफाई और वर्तमान मुहावरेदार परंपराओं से लाइन में यह खींच कर शुरू करेंगे:

case class Flat[T, U](fn: T => List[U]) 

implicit def recFlattenFn[T, U](
    implicit f: Flat[T, U] = Flat((xs: T) => List(xs)) 
) = Flat((xs: List[T]) => xs flatMap f.fn) 

def recFlatten[T, U](xs: List[T3])(implicit f: Flat[List[T], U]) = f fn xs 

फिर, आगे की हलचल के बिना, कोड को तोड़ने।

case class Flat[T, U](fn: T => List[U]) 

इस समारोह T => List[U] के लिए एक नामित आवरण से ज्यादा कुछ नहीं, एक समारोह है कि एक List[U] का निर्माण करेगा जब प्रकार T का एक उदाहरण दिया है: सबसे पहले, हम अपने Flat वर्ग की है। ध्यान दें कि T यहां List[U], या U, या List[List[List[U]]] इत्यादि भी हो सकता है। आम तौर पर, ऐसा फ़ंक्शन सीधे पैरामीटर के प्रकार के रूप में निर्दिष्ट किया जा सकता है। लेकिन हम इस मामले का उपयोग प्रत्यारोपण में करने जा रहे हैं, इसलिए नामित रैपर एक निहित संघर्ष के किसी भी जोखिम से बचाता है।

फिर, recFlatten से पीछे की ओर काम कर रहे:

def recFlatten[T, U](xs: List[T])(implicit f: Flat[List[T], U]) = f fn xs 

इस विधि ले जाएगा xs (एक List[T]) और यह एक U में बदलने का। इस लक्ष्य को हासिल करने के लिए, यह तब Flat[T,U] का एक अंतर्निहित उदाहरण पता लगाता है और संलग्न समारोह का आह्वान, fn

, असली जादू:

implicit def recFlattenFn[T, U](
    implicit f: Flat[T, U] = Flat((xs: T) => List(xs)) 
) = Flat((xs: List[T]) => xs flatMap f.fn) 

यह अंतर्निहित recFlatten द्वारा आवश्यक पैरामीटर को संतुष्ट करता है, यह भी एक और निहित परमाटर लेता है । सबसे महत्वपूर्ण बात:

• recFlattenFn अपनी ही निहित पैरामीटर के रूप में कार्य कर सकते हैं
• यह रिटर्न एक फ्लैट [सूची [X], X], इसलिए recFlattenFn केवल परोक्ष का समाधान हो जाएगा के रूप में एक Flat[T,U] अगर T एक List
है अंतर्निहित संकल्प विफल रहता है
• निहित f एक डिफ़ॉल्ट मान पर वापस आने कर सकते हैं (यानी T एक List नहीं है)

Perha ps इस सबसे अच्छा उदाहरण के संदर्भ में समझा जाता है:

recFlatten(List(List(1, 2, 3), List(4, 5))) 

• प्रकार TList[List[Int]] के रूप में मान लिया जाता है
• अंतर्निहित देखने के लिए एक `फ्लैट [सूची का प्रयास किया है [सूची [इंट]], यू]
• यह एक के अनुरूप है रिकर्सिवली recFlattenFn

मोटे तौर पर परिभाषित बोल:

recFlattenFn[List[List[Int]], U] (f = 
    recFlattenFn[List[Int], U] (f = 
    Flat[Int,U]((xs: T) => List(xs)) //default value 
) 
) 

ध्यान दें कि recFlattenFn केवल एक Flat[List[X], X] के लिए एक अंतर्निहित खोज और प्रकार से मेल खाएगी पैरामीटर [Int,_] इस मैच असफल क्योंकि Int एक List नहीं है। यह वही है जो फॉलबैक को डिफ़ॉल्ट मान पर ट्रिगर करता है।

प्रकार निष्कर्ष यह भी कहा कि संरचना पीछे की ओर काम करता है, प्रत्यावर्तन के प्रत्येक स्तर पर U परम हल करने:

recFlattenFn[List[List[Int]], Int] (f = 
    recFlattenFn[List[Int], Int] (f = 
    Flat[Int,Int]((xs: T) => List(xs)) //default value 
) 
) 

कौन सा बस Flat उदाहरणों में से एक घोंसले है, हर एक (अंतरतम को छोड़कर) एक flatMap प्रदर्शन नेस्टेड List संरचना के एक स्तर को अनलॉक करने के लिए ऑपरेशन। अंतरतम Flat बस लपेटता सभी अलग-अलग तत्वों एक भी List में बैक अप।

Q.E.D.

Answer 2

एक अच्छा समाधान हो सकता है कि यह देखने के लिए कि किस तरह के प्रकार शामिल हैं। अस्पष्टता से बचने के लिए, हमें जेनरिक नाम बदलने करते हैं: पहला मामला res0 में

case class Flat[T, U](fn : T => List[U]) 

implicit def recFlattenFn[T2, U2](implicit f : Flat[T2, U2] = 
            Flat((l : T2) => List(l))) = 
    Flat((l : List[T2]) => l.flatMap(f.fn)) 

def recFlatten[T3, U3](l : List[T3])(implicit f : Flat[List[T3], U3]) = f.fn(l) 

, T3 के प्रकार Int आप अभी तक U3 के प्रकार के अनुमान नहीं लगा सकता है, लेकिन आप जानते हैं कि आप एक Flat[List[Int, U3]] वस्तु की आवश्यकता होगी कि पूरी तरह से प्रदान किया जाएगा। केवल एक "निहित उम्मीदवार" है: recFlattenFn फ़ंक्शन का परिणाम और इसका प्रकार Flat[List[T2], List[U2]] है। इस प्रकार T2 = Int और U2 = U3 (जिसे हमें अभी भी अनुमान लगाने की आवश्यकता है)।

अब, अगर हम recFlatten उपयोग करने के लिए सक्षम होने के लिए weant हम इसे एक पैरामीटर f प्रदान करनी चाहिए। यहां चाल है। आप या तो Int => List[Int] प्रकार के डिफ़ॉल्ट मान प्रकार Flat[Int, U2]या के अंतर्निहित उपयोग का उपयोग कर सकते हैं। आइए उपलब्ध उपलब्धियों को देखें। जैसा कि recFlattenFn से पहले बताया गया है Flat[List[T2], U2] (एक नए T2 और U2) ऑब्जेक्ट प्रदान कर सकता है। यह इस बिंदु पर f के अपेक्षित हस्ताक्षर फिट नहीं है। इस प्रकार, यहां कोई अच्छा उम्मीदवार नहीं है और हमें डिफ़ॉल्ट तर्क का उपयोग करना होगा। डिफ़ॉल्ट तर्क के प्रकार के रूप में int => सूची [Int], U2 और U3Int हैं और वहां हम जाते हैं।

आशा है कि यह लंबा गद्य मदद करेगा। मैं आपको res1 और res2 के संकल्प के साथ छोड़ देता हूं।