मानक रिकर्सन

Question

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

findKey :: (Eq k) => k -> [(k,v)] -> Maybe v 
findKey key [] = Nothing 
findKey key ((k,v):xs) = if key == k 
          then Just v 
          else findKey key xs 

किताब फिर foldr

findKey :: (Eq k) => k -> [(k,v)] -> Maybe v 
findKey key = foldr (\(k,v) acc -> if key == k then Just v else acc) Nothing 

का उपयोग कर मानक प्रत्यावर्तन के साथ एक छोटी कार्यान्वयन के साथ इस प्रकार है, समारोह तुरंत लौट जाना एक बार यह हिट प्रदान की गई कुंजी के साथ पहला तत्व। यदि मैं foldr कार्यान्वयन को सही ढंग से समझता हूं, तो यह हर बार पूरी सूची में फिर से चालू हो जाएगा, भले ही यह पहले तत्व से मेल खाता हो। यह समस्या को संभालने के लिए एक बहुत ही कुशल तरीका प्रतीत नहीं होता है।

क्या ऐसा कुछ है जो मुझे नहीं मिल रहा है कि foldr कार्यान्वयन कैसे काम करता है? या क्या हास्केल के भीतर कुछ प्रकार का जादू है जो इस कार्यान्वयन को अक्षम नहीं करता है जैसा कि मुझे लगता है कि यह है?

Answer 1

1. foldr मानक रिकर्सन का उपयोग करके लिखा गया है।

2. foldr पर रिकर्सिव कॉल acc के अंदर छिपा हुआ है। यदि आपका कोड acc का उपयोग नहीं करता है, तो इसकी गणना कभी नहीं की जाएगी (क्योंकि हास्केल आलसी है)। तो foldr संस्करण कुशल है और जल्दी भी वापस आ जाएगा।

   Prelude> foldr (\x z -> "done") "acc" [0 ..] 
   "done" 
   

   यह अभिव्यक्ति देता है "done" तुरंत, भले ही इनपुट सूची असीम लंबा है:

यहाँ एक उदाहरण इस प्रदर्शन है।

---

तो foldr के रूप में परिभाषित किया गया है:

foldr f z (x : xs) = f x (foldr f z xs) 
foldr _ z [] = z 

, तो मूल्यांकन के माध्यम से

f x (foldr f z xs) 
    where 
    f = \x z -> "done" 
    x = 0 
    z = "acc" 
    xs = ... -- unevaluated, but is [1 ..] 

जो

(\x z -> "done") 0 (foldr (\x z -> "done") "acc" [1 ..]) 

जो "done" में बदल जाता है है चला जाता है क्योंकि पहला फ़ंक्शन z का उपयोग नहीं करता है, इसलिए रिकर्सिव कॉल की आवश्यकता नहीं होती है।

Answer 2

यदि मैं फ़ोल्डर कार्यान्वयन को सही ढंग से समझता हूं, तो यह हर बार पूरी सूची में फिर से चालू हो जाएगा, भले ही यह पहले तत्व से मेल खाता हो।

यह गलत है। foldr केवल उतनी ही आवश्यक सूची का मूल्यांकन करेगा।

उदा।

foldr (&&) True [True, False, error "unreached code here"] 

रिटर्न False के बाद से त्रुटि का मूल्यांकन नहीं किया जाता, ठीक

(True && (False && (error "unreached code here" && True))) 

दरअसल के रूप में, के बाद से सूची के अंत तक पहुँच कभी नहीं किया गया है, हम भी लिख सकते हैं

foldr (&&) (error "end") [True, False, error "unreached code here"] 

और अभी भी False प्राप्त करें।

Answer 3

यहाँ कोड है जो यह दर्शाता है कि foldr वास्तव में "शॉर्ट सर्किट" findKey के मूल्यांकन करता है:

import Debug.Trace 

findKey :: (Eq k) => k -> [(k,v)] -> Maybe v 
findKey key = foldr (\(k,v) acc -> if key == k then Just v else acc) Nothing 

tr x = trace msg x 
    where msg = "=== at: " ++ show x 

thelist = [ tr (1,'a'), tr (2,'b'), tr (3, 'c'), tr (4, 'd') ] 

GHCi में findKey चलाने का एक उदाहरण:

*Main> findKey 2 thelist 
=== at: (1,'a') 
=== at: (2,'b') 
Just 'b' 
*Main> 

Answer 4

का उपयोग कर foldr की Think निम्नलिखित परिभाषा (मानक रिकर्सन का उपयोग करके):

foldr :: (a -> b -> b) -> b -> [a] -> b 
foldr f e [] = e 
foldr f e (x:xs) = f x (foldr f e xs) 

तीसरी पंक्ति से पता चलता है कि खोज के लिए दूसरा कार्यान्वयन पहला मैच खोजने पर वापस आ जाएगा।

---

एक sidenote के रूप: मान लें कि आपके पड़ा निम्नलिखित परिभाषा (जो समान कार्यक्षमता नहीं है) findKey के लिए (एक व्यायाम के रूप में आप foldr का उपयोग कर परिभाषा के पुनर्लेखन के लिए चाहते हो सकता है):

findKey :: (Eq k) => k -> [(k,v)] -> [v] 
findKey key [] = [] 
findKey key ((kHead, vHead):rest) = if (key == kHead) then vHead:(findKey key rest) else findKey key rest 

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

head (findKey key li) 

आप पहले मैच (यह मानते हुए वहाँ एक है कि) अपने पहले उदाहरण के रूप में एक ही दक्षता के साथ दे देंगे।

Answer 5

foldr f z [a,b,c,...,n]     == 
a `f` (b `f` (c `f` (... (n `f` z) ...))) == 
f a (foldr f z [b,c,...,n])    == 
f a acc where acc = foldr f z [b,c,...,n] 

तो अगर अपने f रिटर्न से पहलेforcingacc, acc मजबूर नहीं रहता है, अर्थात उसके सिर तत्व a परे सूची तर्क का कोई हिस्सा नहीं जैसे जैसे एक्सेस किया जाता है, आप

f a acc = ... 

है जब, तो दूसरी ओर, अपने f इसकी दूसरा तर्क है, उदा मजबूर करता हैअगर यह रूप में

f a (x:xs) = ... 

परिभाषित किया है तो accf से पहले मजबूर किया जाता है अपने काम शुरू होता है, और सूची प्रसंस्करण से पहले पूरे में पहुँचा जा होगा शुरू होता है - पूरे में, क्योंकि acc = f b acc2 और कि मंगलाचरण fको दूसरा तर्क, acc2 को मजबूर करना चाहिए, इसलिए इसका मान, acc, मजबूर किया जा सकता है ((x:xs) के साथ पैटर्न-मिलान); इत्यादि।