2009-09-03 19 views
14

यह प्रश्न इस प्रकार है कि स्कैला पैटर्न मिलान और सूचियों के साथ पुनरावृत्ति करता है और इसका प्रदर्शन करता है।स्कैला सूची रिकर्सन प्रदर्शन

अगर मैं एक समारोह है कि एक सूची से अधिक recurses है और मैं एक विपक्ष पर मिलान की तरह उदाहरण के कुछ करने के लिए, के साथ यह करना: मैं उपयोग कर रहा हूँ

myFunction [] = [] 
myFunction (x:xs) = «something» : myFunction xs 

:

def myFunction(xs) = xs match { 
    case Nil => Nil 
    case x :: xs => «something» myFunction(xs) 
} 

हास्केल में वही अर्थशास्त्र जो मैं करता हूं, उदाहरण के लिए, हास्केल। मुझे नहीं लगता कि हास्केल कार्यान्वयन के बारे में कोई सवाल होगा क्योंकि यह केवल सूचियों से निपटने का तरीका है। एक लंबी सूची के लिए (मैं कुछ हज़ार नोड्स के साथ एक सूची पर काम कर रहा हूं), हास्केल झपकी नहीं देगा (हालांकि मैं कल्पना करता हूं; मैंने कभी कोशिश नहीं की है)।

लेकिन से मैं क्या स्काला के साथ समझते हैं, मैच बयान विपक्ष के आसपास सूची विभाजित है और, करने के लिए एक समारोह है कि सूची में कुछ नहीं करता है के लिए उदाहरण का विस्तार करने के unapply निकालने विधि कहेंगे:

def myFunction(xs) = xs match { 
    case Nil => Nil 
    case x :: xs => x :: myFunction(xs) 
} 

हास्केल में:

myFunction [] = [] 
myFunction (x:xs) = x : myFunction xs 

यह इसे वापस एक साथ विपक्ष को निकालने तरीका लागू कहेंगे। एक लंबी सूची के लिए मुझे लगता है कि यह बहुत महंगा होगा।

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

मैं वास्तव में प्रत्यावर्तन के प्रत्येक चरण के लिए निर्माणकर्ता और एक्सट्रैक्टर्स बुला अगर मैं एक लंबी सूची से अधिक recurse करना चाहते हो जाएगा? या वहाँ अनुकूलन हैं? या इसे करने के बेहतर तरीके? इस मामले में मैं कई संचायक चर की आवश्यकता होगी और स्पष्ट रूप से मैं बस कुछ नहीं कर रहे एक सूची से अधिक recursing जा नहीं होगा ...

(कृपया मेरी हास्केल बहाना, मैं दो साल के लिए एक लाइन नहीं लिखा है।)

(और हाँ, मैं पूंछ प्रत्यावर्तन के लिए जा रहा हूँ।)

उत्तर

19

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

def myFunction[T](l: List[T]): Stream[T] = l match { 
    case Nil => Stream.empty 
    case x :: xs => x #:: myFunction(xs) 
} 

यह एक List, जो सख्त है प्राप्त करता है, और एक Stream जो गैर सख्त है देता है।

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

def myFunction[T](xs: List[T]): Stream[T] = 
    if (xs.isEmpty) Stream.empty else xs.head #:: myFunction(xs.tail) 

मैं सिर्फ महसूस किया तुम जाओ करने का इरादा पूंछ रिकर्सन के लिए। आपने जो लिखा है वह पूंछ-पुनरावर्ती नहीं है, क्योंकि आप को परिणाम पुनरावृत्ति के लिए पूर्ववत करते हैं।जब सूचियों से निपटने, आप पूंछ प्रत्यावर्तन यदि आप पीछे की ओर परिणामों की गणना के मिल जाएगा और फिर उलटने:

class ListExample { 
    def test(o: Any): Any = o match { 
    case Nil => Nil 
    case x :: xs => xs 
    case _ => null 
    } 
} 

उत्पन्न करता है:

def myFunction[T](xs: List[T]): List[T] = { 
    def recursion(input: List[T], output: List[T]): List[T] = input match { 
    case x :: xs => recursion(xs, x :: output) 
    case Nil => output 
    } 
    recursion(xs, Nil).reverse 
} 

अंतिम, चलो देखने के लिए एक उदाहरण डिकंपाइल कि यह कैसे काम करता है

public class ListExample extends java.lang.Object implements scala.ScalaObject{ 
public ListExample(); 
    Code: 
    0: aload_0 
    1: invokespecial #10; //Method java/lang/Object."<init>":()V 
    4: return 

public java.lang.Object test(java.lang.Object); 
    Code: 
    0: aload_1 
    1: astore_2 
    2: getstatic  #18; //Field scala/Nil$.MODULE$:Lscala/Nil$; 
    5: aload_2 
    6: invokestatic #24; //Method scala/runtime/BoxesRunTime.equals:(Ljava/lang/Object;Ljava/lang/Object;)Z 
    9: ifeq 18 
    12: getstatic  #18; //Field scala/Nil$.MODULE$:Lscala/Nil$; 
    15: goto 38 
    18: aload_2 
    19: instanceof  #26; //class scala/$colon$colon 
    22: ifeq 35 
    25: aload_2 
    26: checkcast  #26; //class scala/$colon$colon 
    29: invokevirtual #30; //Method scala/$colon$colon.tl$1:()Lscala/List; 
    32: goto 38 
    35: aconst_null 
    36: pop 
    37: aconst_null 
    38: areturn 

public int $tag() throws java.rmi.RemoteException; 
    Code: 
    0: aload_0 
    1: invokestatic #42; //Method scala/ScalaObject$class.$tag:(Lscala/ScalaObject;)I 
    4: ireturn 

} 

डीकोडिंग, यह पहले पास पैरामीटर और Nil पर विधि equals विधि को कॉल करता है। यदि सत्य हो तो उत्तरार्द्ध लौटाता है। अन्यथा, यह ऑब्जेक्ट पर instanceOf[::] पर कॉल करता है। यदि सही है, तो यह उस वस्तु को उस पर रखता है, और उस पर tl विधि को आमंत्रित करता है। उन सभी को विफल करना, कोसेंटेंट null लोड करता है और इसे वापस करता है।

तो, आप देखते हैं, x :: xs कोई निकालने वाला नहीं है।

जमा के रूप में, वहाँ एक और पैटर्न आप विचार करना चाह सकते हैं:

val list = List.fill(100)(scala.util.Random.nextInt) 
case class Accumulator(negative: Int = 0, zero: Int = 0, positive: Int = 0) 
val accumulator = list.foldLeft(Accumulator())((acc, n) => 
    n match { 
    case neg if neg < 0 => acc.copy(negative = acc.negative + 1) 
    case zero if zero == 0 => acc.copy(zero = acc.zero + 1) 
    case pos if pos > 0 => acc.copy(positive = acc.positive + 1) 
    }) 

डिफ़ॉल्ट मापदंडों और कॉपी तरीकों एक स्काला 2.8 सुविधा मैं सिर्फ उदाहरण सरल बनाने के लिए उपयोग किया जाता है, लेकिन बिंदु उपयोग कर रहा है foldLeft विधि जब आप किसी सूची में चीजें जमा करना चाहते हैं।

+0

धन्यवाद! हां, जो मैं लिख रहा हूं वह पूंछ-रिकर्सिव होगा, दूसरा स्निपेट एक बुरा उदाहरण था! जो मैं वास्तव में करना चाहता हूं वह कुछ गैर-तुच्छ कार्य के आधार पर इनपुट स्ट्रिंग को विभिन्न हिस्सों में विभाजित कर रहा है: नतीजा यह है कि जमाकर्ता कोई नक्शा या गुना शैली आउटपुट नहीं करते हैं। शायद मैं इस सामान्य मामले में सामान्य पैटर्न की तलाश में प्रश्न को सामान्य बनाने की कोशिश कर रहा था। – Joe

+0

ठीक है, मैंने जो आखिरी उदाहरण जोड़ा है उसे देखें। –

+0

बिल्कुल सही, जो दोनों पहलुओं का उत्तर देता है। आपका बहुत बहुत धन्यवाद! – Joe

संबंधित मुद्दे