पैटर्न मिलान और अनंत स्ट्रीम

Question

तो, मैं खुद को स्कैला सिखाने के लिए काम कर रहा हूं, और जिन चीजों के साथ मैं खेल रहा हूं उनमें से एक Stream वर्ग है।

object LazyHammingBad { 
    private def merge(a: Stream[BigInt], b: Stream[BigInt]): Stream[BigInt] = 
    (a, b) match { 
     case (x #:: xs, y #:: ys) => 
     if (x < y) x #:: merge(xs, b) 
     else if (y < x) y #:: merge(a, ys) 
     else x #:: merge(xs, ys) 
    } 

    val numbers: Stream[BigInt] = 
    1 #:: merge(numbers map { _ * 2 }, 
     merge(numbers map { _ * 3 }, numbers map { _ * 5 })) 
} 

दुभाषिया में एक स्पिन के लिए इस उठाते हुए नेतृत्व जल्दी से निराशा करने के लिए:

scala> LazyHammingBad.numbers.take(10).toList 
java.lang.StackOverflowError 

मैं यह देखने के लिए देखने का फैसला किया मैं आलोचनात्मक संख्या समस्या का classic Haskell version of Dijkstra's solution की एक सीधी सादी अनुवाद का उपयोग करने की कोशिश की अन्य लोगों हास्केल दृष्टिकोण का उपयोग कर स्काला में समस्या हल हो गया था, और Rosetta कोड से this solution अनुकूलित:

object LazyHammingGood { 
    private def merge(a: Stream[BigInt], b: Stream[BigInt]): Stream[BigInt] = 
    if (a.head < b.head) a.head #:: merge(a.tail, b) 
    else if (b.head < a.head) b.head #:: merge(a, b.tail) 
    else a.head #:: merge(a.tail, b.tail) 

    val numbers: Stream[BigInt] = 
    1 #:: merge(numbers map {_ * 2}, 
      merge(numbers map {_ * 3}, numbers map {_ * 5})) 
} 

यह एक अच्छी तरह से काम किया, लेकिन मुझे अभी भी आश्चर्य है कि मैं LazyHammingBad में गलत कैसे हुआ। #:: का उपयोग x #:: xs को किसी कारण से xs के मूल्यांकन के लिए मजबूर करता है? असीमित धाराओं के साथ सुरक्षित रूप से मेल खाने वाले पैटर्न का उपयोग करने का कोई तरीका है, या क्या आपको head और tail का उपयोग करना है यदि आप चीजों को उड़ाना नहीं चाहते हैं?

Answer 1

a match {case x#::xs =>...val (x, xs) = (a.head, a.tail) जैसा ही है। तो खराब संस्करण और अच्छे के बीच का अंतर यह है कि उसमें खराब संस्करण में, आप a.tail और b.tail पर शुरुआत में शुरुआत कर रहे हैं, बजाय परिणामस्वरूप स्ट्रीम की पूंछ बनाने के लिए उनका उपयोग करें। इसके अलावा जब आप उन्हें #:: (पैटर्न मिलान नहीं करते हैं, लेकिन परिणाम का निर्माण करते हैं, #:: merge(a.b.tail) में आप वास्तव में विलय को कॉल नहीं कर रहे हैं, जो बाद में किया जाएगा, लौटा स्ट्रीम की पूंछ तक पहुंचने पर। तो अच्छे में संस्करण, एक कॉल विलय करने के लिए tail बिल्कुल फोन नहीं करता है। बुरा संस्करण में, यह यह सही शुरू में कहता है।

अब अगर आप संख्या पर विचार करें, या यहाँ तक कि एक सरलीकृत संस्करण, 1 #:: merge(numbers, anotherStream) कहते हैं, जब आप कॉल आप tail फोन (के रूप में take(10) होगा) कि पर, merge। आप जोपर tails कॉल numbers पर tail फोन है, जो पैरामीटर के रूप में numbers साथ merge कहते हैं, का मूल्यांकन किया जाना है 0, जो merge पर कॉल करता है, जो tail कहता है ...

इसके विपरीत, सुपर आलसी हास्केल में, जब आप पैटर्न मिलान करते हैं, तो यह मुश्किल से कोई काम करता है। जब आप case l of x:xs करते हैं, तो यह l का मूल्यांकन करेगा ताकि यह पता चल सके कि यह एक खाली सूची या विपक्ष है या नहीं। यदि यह वास्तव में एक विपक्ष है, x और xs दो थंक के रूप में उपलब्ध होगा, जो फ़ंक्शंस अंततः सामग्री तक पहुंच प्रदान करेगा। स्कैला में निकटतम समकक्ष केवल का परीक्षण करना होगा।

ध्यान दें कि स्कैला स्ट्रीम में, tail आलसी है, head नहीं है। जब आपके पास एक (खाली नहीं) स्ट्रीम होता है, तो सिर को जाना जाना चाहिए। जिसका अर्थ यह है कि जब आप धारा की पूंछ प्राप्त करते हैं, तो खुद ही एक धारा, उसका सिर, जो कि मूल धारा का दूसरा तत्व है, की गणना की जानी चाहिए। यह कभी-कभी समस्याग्रस्त होता है, लेकिन आपके उदाहरण में, आप वहां पहुंचने से पहले विफल हो जाते हैं।

Answer 2

ध्यान दें कि आप Stream के लिए एक बेहतर पैटर्न मिलान को परिभाषित करते हुए आप क्या चाहते हैं कर सकते हैं: तुम सिर्फ सुनिश्चित करने की आवश्यकता

object HammingTest { 
    // A convenience object for stream pattern matching 
    object #:: { 
    class TailWrapper[+A](s: Stream[A]) { 
     def unwrap = s.tail 
    } 
    object TailWrapper { 
     implicit def unwrap[A](wrapped: TailWrapper[A]) = wrapped.unwrap 
    } 
    def unapply[A](s: Stream[A]): Option[(A, TailWrapper[A])] = { 
     if (s.isEmpty) None 
     else { 
     Some(s.head, new TailWrapper(s)) 
     } 
    } 
    } 

    def merge(a: Stream[BigInt], b: Stream[BigInt]): Stream[BigInt] = 
    (a, b) match { 
     case (x #:: xs, y #:: ys) => 
     if (x < y) x #:: merge(xs, b) 
     else if (y < x) y #:: merge(a, ys) 
     else x #:: merge(xs, ys) 
    }            //> merge: (a: Stream[BigInt], b: Stream[BigInt])Stream[BigInt] 

    lazy val numbers: Stream[BigInt] = 
    1 #:: merge(numbers map { _ * 2 }, merge(numbers map { _ * 3 }, numbers map { _ * 5 })) 
                //> numbers : Stream[BigInt] = <lazy> 
    numbers.take(10).toList       //> res0: List[BigInt] = List(1, 2, 3, 4, 5, 6, 8, 9, 10, 12) 
} 

अब:

यहाँ एक सा मैं सिर्फ एक Scala Worksheet में एक साथ खींच लिया है जब भी यह पैटर्न मिलान कर रहा है, तब Stream.class में स्केल को object #:: मिलती है। इसे सुविधाजनक बनाने के लिए, #>: या ##:: जैसे किसी भिन्न नाम का उपयोग करना सबसे अच्छा हो सकता है और फिर पैटर्न मिलान करते समय हमेशा उस नाम का उपयोग करना याद रखें।

यदि आपको कभी भी खाली स्ट्रीम से मिलान करने की आवश्यकता है, तो case Stream.Empty का उपयोग करें। case Stream() का उपयोग पैटर्न मिलान में आपकी पूरी स्ट्रीम का मूल्यांकन करने का प्रयास करेगा, जिससे उदासी हो जाएगी।