Haskell गुना आपरेशन

Question

data Tree a = Tree a [Tree a] 

ध्यान दें कि हम खाली पेड़ की अनुमति नहीं है, और एक पत्ता उपतरू के एक खाली सूची के साथ एक पेड़ है।

treeFold :: (a -> [b] -> b) -> Tree a -> b 
treeFold f (Tree x s) = f x (map (treeFold f) s) 

उपरोक्त जानकारी को देखते हुए, मुझे समझ नहीं आता कैसे पेड़ गुना समारोह रिकर्सिवली subtrees को गुना आपरेशन लागू करने के लिए, तो जड़ और परिणाम पर लेबल के लिए समारोह लागू करके किसी परिणाम देता है subtrees से वापस आ गया।

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

उदाहरण के लिए, पेड़ के आकार का कार्य नीचे पेड़ के नोड्स की गणना करता है।

treeSize :: Tree a -> Int 
treeSize = treeFold (\x ys -> 1 + sum ys) 

तो TreeSize पेड़ जहां tree = Tree 4 [Tree 1 [Tree 2 [], Tree 3 []]] ऊपर पेड़ आकार समारोह में के रूप में 4.

पेड़ के आकार देता है, पेड़ गुना समारोह भी दो के बजाय एक तर्क पारित हो जाता है चल रहा है। इसके अलावा, पेड़ गुना समारोह में पारित एक्स कहीं भी उपयोग नहीं किया जा रहा है, तो आपको इसकी आवश्यकता क्यों है। इसे हटाने से प्रोग्राम संकलित नहीं होता है और यह निम्न त्रुटि संदेश देता है।

Couldn't match type `a' with `[[Int] -> Int]' 
     `a' is a rigid type variable bound by 
      the type signature for treeSize :: Tree a -> Int 
      at treeFold.hs:15:1 
    In the first argument of `sum', namely `ys' 
    In the second argument of `(+)', namely `sum ys' 
    In the expression: 1 + sum ys 

किसी भी मदद की सराहना की जाएगी।

Answer 1

पहला सवाल थोड़ा मुश्किल है, क्योंकि यह रिकर्सन के साथ बात है ... शिक्षकों का कहना है: "रिकर्सन को समझने के लिए, आपको सीखना होगा कि कैसे रिकर्सन काम करता है"। :-P एक छोटी सी सलाह: treeFold के एक पेड़ के साथ एक पेड़ या पेड़ के साथ आवेदन करने का प्रयास करें और इसे अपने आप (कागज़ पर या तो) का मूल्यांकन करें। मुझे लगता है, तो आप क्या हो रहा है इसके बारे में एक महसूस कर सकते हैं ... (निश्चित रूप से पेड़ के लिए एक तर्क के रूप में एक साधारण कार्य का उपयोग करें; उस तरह, जो आपके पेड़ आकार का उपयोग करता है)।

treeFold, नक्शे शरीर में केवल एक ही तर्क हो जाता है क्योंकि mapa->b से एक समारोह की आवश्यकता है, और treeFold, प्रकार (a -> [b] -> b) -> Tree a -> b. है, इसलिए यदि आप यह 2 तर्कों मिलेगा, इसलिये आप map को केवल एक मूल्य के पास होता है, जो एक कारण बनता है विफलता। (एक समझने योग्य उदाहरण: (+) को दो तर्कों की आवश्यकता होती है। यदि आप map (+1) [1,2,3] लिखते हैं तो आपको [2,3,4] मिल जाएगा, क्योंकि (+1) सूची में प्रत्येक तत्व पर लागू होता है (और (+1) स्पष्ट रूप से एक और तर्क की आवश्यकता है, ऊपर अपने treeFold f)

आपका उदाहरण TreeSize:। यह सही नहीं है, जब आप कहते हैं, यह केवल एक तर्क हो जाता है कि आप

treeSize t = treeFold (\x ys -> 1 + sum ys) t 

अपनी परिभाषा के बजाय

ऊपर लिख सकते है एक्स नहीं है। इसका इस्तेमाल किया जाता है क्योंकि इसे गिनने के लिए बेकार है। लेकिन, treeFoldn एक कार्य करने के लिए eeds, जो दो तर्क लेता है, तो आप इसे एक्स देते हैं। यही एकमात्र कारण है। आप कोई अन्य मूल्य पारित कर सकते हैं।

Answer 2

अप्रयुक्त तर्क

पहले, जिस तरह से आप स्पष्ट रूप से एक चर के रूप में चिह्नित किया जा रहा है अप्रयुक्त _ साथ चर को बदलने के लिए है। तो तुम सच में चाहते थे:

treeFold (\_ ys -> 1 + sum ys) 

आप क्योंकि आप ने लिखा है एक संकलक त्रुटि मिली:

treeFold (\ys -> 1 + sum ys) 

... जो एक ही बात नहीं है।

फोल्ड्स

दूसरा, मैं एक उदाहरण के पेड़ पर treeSize का मूल्यांकन हाथ करेंगे जिससे कि आप देख सकते हैं है कि वहाँ कोई जादू हो रहा:

treeSize (Tree 1 [Tree 2 [], Tree 3 []]) 

-- Inline definition of 'treeSize' 
= treeFold (\_ ys -> 1 + sum ys) (Tree 1 [Tree 2 [], Tree 3 []]) 

-- Evaluate treeFold 
= (\_ ys -> 1 + sum ys) 1 (map (treeFold (\_ ys -> 1 + sum ys)) [Tree 2 [], Tree 3 []]) 

-- Apply the anonymous function 
= 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) [Tree 2 [], Tree 3 []]) 

-- Apply the 'map' function 
= 1 + sum [ treeFold (\_ ys -> 1 + sum ys) (Tree 2 []) 
      , treeFold (\_ ys -> 1 + sum ys) (Tree 3 []) 
      ] 

-- Apply both 'treeFold' functions 
= 1 + sum [ (\_ ys -> 1 + sum ys) 2 (map (treeFold (\_ ys -> 1 + sum ys)) []) 
      , (\_ ys -> 1 + sum ys) 3 (map (treeFold (\_ ys -> 1 + sum ys)) []) 
      ] 

-- Apply the anonymous functions 
= 1 + sum [ 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) []) 
      , 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) []) 
      ] 

-- map f [] = [] 
= 1 + sum [ 1 + sum [] 
      , 1 + sum [] 
      ] 

-- sum [] = 0 
= 1 + sum [1 + 0, 1 + 0] 
= 1 + sum [1, 1] 

-- Apply 'sum' 
= 1 + 2 
= 3 

हालांकि, वहाँ एक आसान तरीका कैसे याद करने के लिए treeFold है काम करता है। यह सब आपके द्वारा प्रदान की जाने वाली फ़ंक्शन के साथ प्रत्येक Tree कन्स्ट्रक्टर को प्रतिस्थापित करता है।

तो अगर आप हैं:

Tree 1 [Tree 2 [Tree 3 [], Tree 4[]], Tree 5 [Tree 6 [], Tree 7 []]] 

... और आपको लगता है कि करने के लिए treeFold f लागू होते हैं, इसका मूल्यांकन करेंगे करने के लिए:

f 1 [f 2 [f 3 [], f 4 []], f 5 [f 6 [], f 7 []]] 

treeSum सिर्फ विशेष मामला है जहां f = (\_ ys -> 1 + sum ys):

1 + sum [1 + sum [1 + sum [], 1 + sum []], 1 + sum [1 + sum [], 1 + sum []]] 

= 7 

करी

अंतिम बिंदु यह है कि कैसे हास्केल में करीना काम करता है। जब आप की तरह एक समारोह को परिभाषित:

foo = \x -> (\y -> x + y) 

यही कारण है कि आप आंशिक रूप से कार्य करता है हास्केल में सिर्फ एक तर्क करने के लिए आवेदन कर सकते हैं:

foo x y = x + y 

... संकलक वास्तव में उस के लिए दो नेस्टेड कार्यों desugars। जब आप foo 1 लिखते हैं, इसकी अनुवाद करने के लिए:

foo 1 

= (\x -> (\y -> x + y)) 1 

= \y -> 1 + y 

दूसरे शब्दों में, यह एक तर्क का एक नया समारोह देता है।

हास्केल में, सभी कार्य बिल्कुल एक तर्क लेते हैं, और हम नए कार्यों को वापस कर कई तर्कों के कार्यों को अनुकरण करते हैं। इस तकनीक को "करी" के रूप में जाना जाता है।

आप अधिक पारंपरिक मुख्यधारा भाषाओं के बहु तर्क दृष्टिकोण चाहें, तो आप यह समारोह एक टपल तर्क स्वीकार करने को कहकर अनुकरण कर सकते हैं:

f (x, y) = x + y 

हालांकि, कि वास्तव में मुहावरेदार हास्केल नहीं है, और यह जीत लिया ' आपको किसी प्रकार का प्रदर्शन सुधार नहीं देता है।