क्या कार्यात्मक प्रोग्रामिंग में 'ब्रेक विद ब्रेक' या 'संचयक के साथ ढूंढ' के लिए कोई अवधारणा है?

Question

शीर्षक यह सब कहता है, वास्तव में; सामग्रियों के बाहर राज्य को संरक्षित करते समय संग्रह को पुन: स्थापित करना और तत्वों से बाहर निकलने के अलावा समाप्ति स्थिति के आधार पर पुनरावृत्ति परिष्करण करना आवश्यक प्रोग्रामिंग में कुछ भी हासिल करने के लिए सबसे आम पैटर्न हो सकता है। मुझे ऐसा लगता है लेकिन जैसे कि यह कुछ कार्यात्मक gentleprogrammers बारे में बात नहीं पर सहमति व्यक्त की है, या कम से कम मैं इसे कभी नहीं या इस तरह के map, fold, reduce साथ के रूप में एक अर्द्ध Standarized नाम के लिए एक मुहावरा का सामना करना पड़ा, आदि

मैं अक्सर उपयोग स्केल में फॉलोइनिग कोड:

implicit class FoldWhile[T](private val items :Iterable[T]) extends AnyVal { 
    def foldWhile[A](start :A)(until :A=>Boolean)(op :(A, T)=>A) :A = { 
     if (until(start)) start 
     else { 
      var accumulator = start 
      items.find{ e => accumulator = op(accumulator, e); until(accumulator) } 
      accumulator 
     } 

    } 

} 

लेकिन यह बदसूरत है। जब भी मैं एक और अधिक कथात्मक तरीके का प्रयास करें, मैं भी लंबे समय तक और लगभग निश्चित रूप से धीमी कोड, सदृश करने के लिए साथ आते हैं:

Iterator.iterate((start, items.iterator)){ 
    case (acc, i) if until(acc) => (acc, i) 
    case (acc, i) if i.hasNext => (op(acc, i.next()), i) 
    case x => x 
}.dropWhile { 
    case (acc, i) => !until(acc) && i.hasNext 
}.next()._1 

(एक और अधिक कार्यात्मक संस्करण List या Stream रों का प्रयोग करेंगे, लेकिन iterators परिवर्तित करने से यकीनन कम भूमि के ऊपर है itemsStream पर, क्योंकि बाद के लिए डिफ़ॉल्ट कार्यान्वयन किसी भी प्रकार के नीचे एक इटरेटर का उपयोग करता है)।

मेरे प्रश्न हैं:

1) इस अवधारणा को कार्यात्मक प्रोग्रामिंग में एक नाम है, और यदि हां, इसके कार्यान्वयन के साथ जुड़े पैटर्न क्या है?

2) स्केल में इसे लागू करने के लिए सबसे अच्छा (यानी संक्षिप्त, सामान्य, आलसी, और कम से कम ओवरहेड) तरीका क्या होगा?

Answer 1

यह स्केला शुद्धतावादियों द्वारा पर सिकोड़ी है, लेकिन आप एक return बयान इस तरह उपयोग कर सकते हैं:

def foldWhile[A](zero: A)(until:A => Boolean)(op: (A,T) => A): A = items.fold(zero) { 
     case (a, b) if until(a) => return a 
     case (a,b) => op(a, b) 
} 

या, यदि आप त्योरी चढ़ा हुआ उन में से एक हैं, और गंदे जरूरी चाल के बिना एक पूरी तरह कार्यात्मक समाधान चाहते हैं , आप एक iterator या एक धारा की तरह कुछ आलसी उपयोग कर सकते हैं,:

items 
    .toStream // or .iterator - it doesn't really matter much in this case 
    .scanLeft(zero)(op) 
    .find(until) 

Answer 2

इस तरह के काम करने के कार्यात्मक रास्ता Tail Recursion के माध्यम से है:

implicit class FoldWhile[T](val items: Iterable[T]) extends AnyVal { 

    def foldWhile[A](zero: A)(until: A => Boolean)(op: (A, T) => A): A = { 
    @tailrec def loop(acc: A, remaining: Iterable[T]): A = 
     if (remaining.isEmpty || !until(acc)) acc else loop(op(acc, remaining.head), remaining.tail) 

    loop(zero, items) 
    } 
} 

प्रत्यावर्तन का उपयोग करके आप प्रत्येक चरण में तय कर सकते हैं अगर आप break का उपयोग किए बिना और किसी भी भूमि के ऊपर के बिना आगे बढ़ना है या नहीं करना चाहते हैं, क्योंकि पूंछ recursions संकलक से पुनरावृत्तियों में परिवर्तित कर रहे हैं।

इसके अलावा, पैटर्न मिलान अक्सर अनुक्रमों को विघटित करने के लिए उपयोग किया जाता है। उदाहरण के लिए, तुम कर सकते हो अगर आप एक List था:

implicit class FoldWhile[T](val items: List[T]) extends AnyVal { 

    def foldWhile[A](zero: A)(until: A => Boolean)(op: (A, T) => A): A = { 
    @tailrec def loop(acc: A, remaining: List[T]): A = remaining match { 
     case Nil    => acc 
     case _ if !until(acc) => acc 
     case h :: t   => loop(op(acc, h), t) 
    } 

    loop(zero, items) 
    } 
} 

स्काला @scala.annotation.tailrec एनोटेशन बल के समारोह आप टिप्पणी कर रहे पूंछ पुनरावर्ती नहीं है अगर विफल संकलन है। मेरा सुझाव है कि आप इसे जितना कर सकते हैं उतना उपयोग करें क्योंकि यह दोनों त्रुटियों से बचने और कोड को दस्तावेज़ करने में मदद करता है।

Answer 3

एक सही गुना, जब lazily किया, जल्दी समाप्ति कर सकते हैं।

find :: (a -> Bool) -> [a] -> Maybe a 
find p = foldr (\a r -> if p a then Just a else r) Nothing 

-- For reference: 
foldr :: (a -> r -> r) -> r -> [a] -> r 
foldr _ z [] = [] 
foldr f z (a:as) = f a (foldr f z as) 

आप क्या प्रयास करते समय क्या होता है, कहते हैं, find even [1..]: हास्केल में, उदाहरण के लिए, आप foldr साथ find समारोह (कि विधेय को संतुष्ट करता है सूची के पहले तत्व वापसी) लिख सकते हैं? (ध्यान दें कि यह एक अनंत सूची है!)

find even [1..] 
    = foldr (\a r -> if even a then Just a else r) Nothing [1..] 
    = if even 1 
    then Just 1 
    else foldr (\a r -> if even a then Just a else r) Nothing ([2..]) 
    = if False 
    then Just 1 
    else foldr (\a r -> if even a then Just a else r) Nothing ([2..]) 
    = foldr (\a r -> if even a then Just a else r) Nothing ([2..]) 
    = if even 2 
    then Just 2 
    else foldr (\a r -> if even a then Just a else r) Nothing ([3..]) 
    = if True 
    then Just 2 
    else foldr (\a r -> if even a then Just a else r) Nothing ([3..]) 
    = Just 2 

आलस्य का मतलब है कि हम समारोह के साथ (\a r -> if even a then Just a else r) गुना इस सूची में नीचे recurse करने r तर्क-जिसका मूल्यांकन हमें आवश्यकता है मजबूर करने के लिए तय करने के लिए हो जाता है कि -बिलकुल। तो जब even 2True का मूल्यांकन करता है, तो हम if ... then ... else ... की शाखा चुनते हैं जो सूची की पूंछ की गणना के परिणाम को छोड़ देता है जिसका अर्थ है कि हम इसका मूल्यांकन कभी नहीं करते हैं। (यह निरंतर अंतरिक्ष में भी चलता है। जबकि अंतरिक्ष और समाप्ति के मुद्दों के कारण उत्सुक कार्यात्मक भाषाओं में प्रोग्रामर foldr से बचने के लिए सीखते हैं, वे हमेशा आलसी भाषाओं में सच नहीं होते हैं!)

यह निश्चित रूप से इस तथ्य पर निर्भर करता है कि हास्केल का आलसी मूल्यांकन किया गया है, लेकिन फिर भी इसे एक उत्सुक भाषा में अनुकरण करने के लिए संभव होना चाहिए जैसे स्कैला- मुझे पता है कि इसमें lazy val सुविधा है जो इसके लिए उपयोग योग्य हो सकती है। ऐसा लगता है कि आपको lazyFold फ़ंक्शन लिखना होगा जो सही गुना करता है, लेकिन पुनरावृत्ति आलसी मान के अंदर होती है। हालांकि, आपको अंतरिक्ष उपयोग के साथ अभी भी समस्या हो सकती है।