स्कैला में Stream.cons का उपयोग कर गैर-लीकिंग पूंछ-रिकर्सिव फ़ंक्शन कैसे लिखें?

Question

Stream (ओं) पर चल रहे फ़ंक्शन को लिखते समय, रिकर्सन के विभिन्न विचार हैं। पहले सामान्य अर्थ है, तो तुरन्त मूल्यांकन नहीं तो समारोह तुरंत वापस लौट, संकलक स्तर पर पुनरावर्ती नहीं है पूंछ के बाद से, लेकिन उसके परिणाम धारा पुनरावर्ती है:

final def simpleRec[A](as: Stream[A]): Stream[B] = 
    if (a.isEmpty) Stream.empty    
    else someB(a.head) #:: simpleRec(a.tail) 

प्रत्यावर्तन के ऊपर धारणा किसी भी समस्याओं का कारण नहीं है । दूसरा एक संकलक स्तर पर सही मायने में पूंछ पुनरावर्ती है:

@tailrec 
final def rec[A](as: Stream[A]): Stream[B] = 
    if (a.isEmpty) Stream.empty    // A) degenerated 
    else if (someCond) rec(a.tail)   // B) tail recursion 
    else someB(a.head) #:: rec(a.tail)  // C) degenerated 

समस्या है कि यहाँ C) मामले, एक गैर tailrec कॉल के रूप में संकलक द्वारा पता लगाया जाता है, भले ही कोई वास्तविक कॉल किया जाता है। यह एक सहायक समारोह में धारा पूंछ बाहर बाँटे से बचा जा सकता:

@tailrec 
final def rec[A](as: Stream[A]): Stream[B] = 
    if (a.isEmpty) Stream.empty    
    else if (someCond) rec(a.tail)   // B) 
    else someB(a.head) #:: recHelp(a.tail) 

@tailrec 
final def recHelp[A](as: Stream[A]): Stream[B] = 
    rec(as) 

हालांकि यह संकलित, इस दृष्टिकोण अंततः एक स्मृति रिसाव का परिणाम है। चूंकि पूंछ-रिकर्सिव rec को अंततः recHelp फ़ंक्शन से बुलाया जाता है, recHelp फ़ंक्शन के ढेर फ्रेम में स्टीम हेड का संदर्भ होता है, और rec कॉल रिटर्न तक स्ट्रीम को कचरा नहीं होने देता है, जो काफी लंबा हो सकता है (रिकर्सन चरणों के संदर्भ में) B) पर कॉल की संख्या के आधार पर।

ध्यान दें कि असहिष्णु मामले में भी, यदि कंपाइलर @tailrec की अनुमति देता है, तो स्मृति लीक अभी भी मौजूद हो सकती है क्योंकि आलसी धारा पूंछ प्रभावी रूप से स्ट्रीम हेड के संदर्भ में अज्ञात ऑब्जेक्ट होल्डिंग बना देगा।

Answer 1

समस्या, जैसा कि आपने संकेत दिया है, यह है कि कोड में आपने फ़िल्टर चिपकाया हैल्पल्प फ़ंक्शन सिर को रखता है (इसलिए आपका समाधान इसे हटा देता है)।

सबसे अच्छा जवाब यह आश्चर्यजनक व्यवहार से बचने के लिए है, स्कालाज़ एफेमेरलस्ट्रीम का उपयोग करें और इसे दोनों ओम देखें और जीसी के बहुत अच्छे के रूप में काफी तेज दौड़ें। यह हमेशा काम करने के लिए आसान नहीं है उदा। सिर एक() => ए नहीं ए, कोई निकालने वाला आदि नहीं है, लेकिन यह सब एक उद्देश्य, भरोसेमंद स्ट्रीम उपयोग के लिए तैयार है।

आपका filterHelper समारोह आम तौर पर के बारे में है, तो इसके चारों ओर एक संदर्भ रहता देखभाल करने के लिए नहीं है:

import scalaz.EphemeralStream 

@scala.annotation.tailrec 
def filter[A](s: EphemeralStream[A], f: A => Boolean): EphemeralStream[A] = 
    if (s.isEmpty) 
    s 
    else 
    if (f(s.head())) 
     EphemeralStream.cons(s.head(), filterHelp(s.tail() , f)) 
    else 
     filter(s.tail(), f) 

def filterHelp[A](s: EphemeralStream[A], f: A => Boolean) = 
    filter(s, f) 

def s1 = EphemeralStream.range(1, big) 

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

Answer 2

recHelp विधि को स्ट्रीम हेड के संदर्भ में रखने के लिए एक संभावित कामकाज नहीं है। यह यह करने के लिए एक लिपटे धारा गुजर, और आवरण परिवर्तनशील इसे से संदर्भ को मिटाने के लिए प्राप्त किया जा सकता:

@tailrec 
final def rec[A](as: Stream[A]): Stream[B] = 
    if (a.isEmpty) Stream.empty    
    else if (someCond) rec(a.tail)   
    else { 
    // don't inline and don't define as def, 
    // or anonymous lazy wrapper object would hold reference 
    val tailRef = new AtomicReference(a.tail) 
    someB(a.head) #:: recHelp(tailRef) 
    } 

@tailrec 
final def recHelp[A](asRef: AtomicReference[Stream[A]]): Stream[B] = 
    // Note: don't put the content of the holder into a local variable 
    rec(asRef.getAndSet(null)) 

AtomicReference बस सुविधा, atomicity इस मामले में की आवश्यकता नहीं है, किसी भी सरल धारक वस्तु करना होगा ।

भी ध्यान रखें कि जब से recHelp एक धारा Cons पूंछ में लपेटा जाता है, इसलिए यह केवल एक बार मूल्यांकन किया जाएगा, और Cons भी तुल्यकालन का ख्याल रखता है।