क्या मैं फ़ोल्डर के संदर्भ में फ़िल्टर की परिभाषा के बारे में ध्वनि समीकरण तर्क का उपयोग कर रहा हूं?

Question

अच्छी तरह से, इस foldr का उपयोग कर फिल्टर समारोह की परिभाषा है:

myFilter p xs = foldr step [] xs 
    where step x ys | p x  = x : ys 
        | otherwise = ys 

तो उदाहरण के लिए मान लीजिए कि मैं इस कार्य हो जाने:

myFilter odd [1,2,3,4] 

तो यह हो जाएगा:

foldr step [] [1,2,3,4] 

और यह

step 1 (foldr step [] [2,3,4]) 

,210

और इस

step 1 (step 2 (foldr step [] [3,4])) 

हो जाएगा और इस

step 1 (step 2 (step 3 (foldr step [] [4]))) 

हो जाएगा और इस

step 1 (step 2 (step 3 (step 4 (foldr step [] [])))) 

और foldr step [] [] हो जाएगा तो [] है:

step 1 (step 2 (step 3 (step 4 []))) 

अब हम वास्तव में step फ़ंक्शन में पहुंच जाएंगे।
यहाँ, myFilter समारोह अंदर step की परिभाषा है ऊपर से:

step x ys | p x  = x : ys 
      | otherwise = ys 

भी, मैं तुम्हें याद दिलाना है कि p वास्तव में हमारे उदाहरण में odd कार्य है। अजीब

step 1 (step 2 (step 3 (step 4 []))) 

और

सबसे भीतरी step में x = 4, और 4 नहीं है, तो हम ys लौटने, जो []

है:

अच्छी तरह से, फिर से, हम यहाँ हैं तो अब हम इसे प्राप्त करते हैं:

step 1 (step 2 (step 3 [])) 

अब, में सबसे भीतरी step, x = 3, और 3 अजीब है, इसलिए हम x:ys लौटने के लिए, जो 3 : [] है, जो [3] है, और अब हम पाते हैं:

step 1 (step 2 [3]) 

और अब, भीतरी step में, x = 2, और 2 अजीब नहीं है, इसलिए हम ys लौटने के लिए, जो [3] है, इसलिए अब हम मिल जाएगा:

step 1 [3] 

और अब, x = 1, और 1 अजीब है, इसलिए हम x : ys लौटते हैं, जो 1 : [3] है, जो [1,3] है।

अंत :-)।

क्या मैं अपनी सभी चालों में सही हूं?
बहुत बहुत धन्यवाद :-)।

पेज। myFilter की परिभाषा अध्याय 4 में Real World Haskell पुस्तक से है।

Answer 1

यह मुझे पहले पढ़ने पर सही लगता है।

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

step 1 (step 2 (step 3 (step 4 []))) 

अधिक

तरह

step 1 <block1> 

जो हो जाता है

[1, <block1>] 

फिर अगर आप उस सूची से अगले तत्व खींचने की कोशिश, इसका मूल्यांकन करेंगे हो जाता है

[1, step 2 <block2>] 

जो

[1, <block2>] 

और फिर

[1, step 3 (step 4 [])] 

का मूल्यांकन करने की कोशिश कर रहा हो जाता है

[1, step 3 <block3>] 

जो

[1, 3, <block3>] 

आदि हो जाता है यह मैं कुछ समय लिया समझने के लिए बन जाता है। यह मेरे लिए किया गया था counterintuitive कि foldr के बाद से (जो है) कि foldr "में बाहर" से मूल्यांकन किया जाता है आलसी हो सकता है, जबकि foldl सख्त है "अंदर बाहर" लेकिन foldl से मूल्यांकन किया जा रहा है। लेकिन अगर आप इसके बारे में सोचते हैं जिस तरह से मैंने ऊपर उल्लिखित किया है, तो यह समझ में आता है (वैसे भी, वैसे भी)।

Answer 2

पहली नज़र में, आपके विशिष्ट उदाहरण में आपके द्वारा उठाए गए कदम अलग-अलग दिखते हैं। हालांकि, मैं करते रहे कि filter और foldr दोनों उपयोगी अनंत सूचियों --which इंगित करना चाहिए कि अपने कदम के क्रम जहाँ तक हास्केल का सवाल है वह सही नहीं है करने के लिए लागू किया जा सकता चाहते हैं।

Answer 3

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

myFilter करने के लिए कॉल का परिणाम प्रयोग किया जाता है (उदाहरण के मुद्रित के लिए), समारोह निम्न क्रम में मूल्यांकन किया जाएगा:

myFilter odd [1,2,3,4] 

पहले myFilter समारोह मूल्यांकन किया जाता है:

foldr step [] [1,2,3,4] 

अब foldr बाहरीतम कार्य है और मूल्यांकन किया जाता है:

step 1 (foldr step [] [2,3,4]) 

अब step एक 1 उत्पादन का मूल्यांकन किया जाता है, के बाद से 1 अजीब है:

1 : foldr step [] [2,3,4] 

अब परिणाम सूची के पहले तत्व उपलब्ध है और फोन करने के समारोह के द्वारा प्रयोग किया जा सकता है। बुला समारोह भी उपयोग करता है तो निम्नलिखित तत्वों मूल्यांकन के साथ जारी है foldr:

1 : step 2 (foldr step [] [3,4]) 

step के मूल्यांकन अब, किसी भी नए तत्वों का उत्पादन नहीं करता, क्योंकि 2 भी है:

1 : foldr step [] [3,4] 

तो foldr दोबारा:

1 : step 3 (foldr step [] [4]) 

अब step का मूल्यांकनका उत्पादन करता है:

1 : 3 : foldr step [] [4] 

foldr का मूल्यांकन;

1 : 3 : step 4 (foldr step [] []) 

और step एक बार फिर:

1 : 3 : foldr step [] [] 

अंत में foldr एक खाली सूची का मूल्यांकन: उस के लिए

1 : 3 : []