ट्री के लिए शून्य मूल्य एक - हास्केल

Question

में> एक ​​तो मैं एक पेड़ के रूप में परिभाषित

data Tree a = Leaf | Node a (Tree a) (Tree a) deriving Show 

मैं जानता हूँ कि मैं पत्ता एक होने के लिए पत्ता को परिभाषित कर सकते हैं। लेकिन मैं वास्तव में सिर्फ अपने नोड्स के मूल्यों को चाहता हूं। मेरी समस्या यह है कि मैं प्रकार

Tree a -> a 

की वापसी मान समारोह है के बाद से लीफ़्स कोई मूल्य नहीं मैं कैसे कहने के लिए उलझन में हूँ जब मैं कोई खोज करते है अगर आप एक पत्ता कुछ नहीं कर मुठभेड़। मैंने nil, " ", ' ', [] कुछ भी काम करने की कोशिश नहीं की।

संपादित कोड

data Tree a = Leaf | Node a (Tree a) (Tree a) deriving Show 


breadthFirst :: Tree a -> [a] 
breadthFirst x = _breadthFirst [x] 

_breadthFirst :: [Tree a] -> [a] 
_breadthFirst [] = [] 
_breadthFirst xs = map treeValue xs ++ 
       _breadthFirst (concat (map immediateChildren xs)) 

immediateChildren      :: Tree a -> [Tree a] 
immediateChildren (Leaf)    = [] 
immediateChildren (Node n left right) = [left, right] 

treeValue       :: Tree a -> a 
treeValue (Leaf)    = //this is where i need nil 
treeValue (Node n left right) = n 

test = breadthFirst (Node 1 (Node 2 (Node 4 Leaf Leaf) Leaf) (Node 3 Leaf (Node 5 Leaf Leaf))) 

main = 
    do putStrLn $ show $ test 

Answer 1

तो इस मामले में मेरी समाधान Maybe और mapMaybe उपयोग करने के लिए किया जाएगा। बस इसे डाल करने के लिए आप treeValue

treeValue       :: Tree a -> Maybe a 
treeValue (Leaf)    = Nothing 
treeValue (Node n left right) = Just n 

को फिर map उपयोग करते हुए इस गठबंधन करने के लिए करने के बजाय, mapMaybe का उपयोग करें (Data.Maybe से) को बदल देंगे, जो स्वत: Just दूर पट्टी और इसे अनदेखा अगर यह Nothing है जाएगा।

mapMaybe treeValue xs 

वोला!

data Maybe a = Just a | Nothing 

यह एक Nullable प्रकार के होने का नैतिक बराबर है:

Maybe कह "कुछ एक मूल्य नहीं हो सकता" और सिर्फ इस तरह परिभाषित किया गया है की हास्केल का तरीका है। हास्केल सिर्फ आपको इस तथ्य को स्वीकार करता है कि आपको उस मामले को संभालना होगा जहां यह "शून्य" है। जब आपको उनकी आवश्यकता होती है, Data.Maybe में बहुत से उपयोगी फ़ंक्शन हैं, जैसे mapMaybe उपलब्ध।

Answer 2

हास्केल में, प्रकारों में डिफ़ॉल्ट रूप से "खाली" या nil मान नहीं होता है। जब आपके पास Integer का प्रकार है, उदाहरण के लिए, आप हमेशा में वास्तविक संख्या है और nil, null या None जैसी कुछ भी नहीं है।

ज्यादातर समय, यह व्यवहार अच्छा है। जब आप उनकी अपेक्षा नहीं करते हैं तो आप कभी भी शून्य सूचक अपवादों में भाग नहीं ले सकते हैं, क्योंकि जब आप उनकी अपेक्षा नहीं करते हैं तो आपके पास नल नहीं हो सकता है। हालांकि, कभी-कभी हमें वास्तव में Nothing किसी प्रकार का मान होना चाहिए; आपका पेड़ समारोह एक आदर्श उदाहरण है: यदि हमें पेड़ में कोई परिणाम नहीं मिलता है, तो हमें किसी भी तरह से संकेत देना होगा।

की तरह यह सिर्फ एक प्रकार में लपेट के लिए है एक "अशक्त" मान जोड़ने के लिए सबसे स्पष्ट रास्ता:

data Nullable a = Null | NotNull a 

इसलिए यदि आप एक Integer जो भी Null हो सकता है चाहते हैं, तो आप सिर्फ एक Nullable Integer का उपयोग । आप आसानी से इस प्रकार को जोड़ सकते हैं; इसके बारे में कुछ खास नहीं है।

सौभाग्य से, हास्केल मानक पुस्तकालय, पहले से ही इस तरह की एक प्रकार है सिर्फ एक भिन्न नाम के साथ:

treeValue :: Tree a -> Maybe a 
treeValue (Node value _ _) = Just value 
treeValue Leaf    = Nothing 

आप:

data Maybe a = Nothing | Just a 

आप निम्नानुसार अपने पेड़ समारोह में इस प्रकार का उपयोग कर सकते पैटर्न-मिलान द्वारा Maybe में लिपटे मान का उपयोग कर सकते हैं। तो अगर आप [Maybe a] की एक सूची है और आप एक [String] बाहर निकलने के लिए चाहते हैं, आप ऐसा कर सकता है:

showMaybe (Just a) = show a 
showMaybe Nothing = "" 

myList = map showMaybe listOfMaybes 

अंत में, Data.Maybe मॉड्यूल में परिभाषित उपयोगी कार्यों का एक समूह है। उदाहरण के लिए, mapMaybe है जो एक सूची को मानचित्र करता है और सभी Nothing मानों को बाहर निकाल देता है। उदाहरण के लिए, शायद यह है कि आप अपने _breadthFirst फ़ंक्शन के लिए उपयोग करना चाहते हैं।

Answer 3

इस मामले में, आप बस map के बजाय एक सूची समझ का उपयोग कर सकते हैं और treeValue से छुटकारा पाने:

_breadthFirst xs = [n | Node n _ _ <- xs] ++ ... 

यह काम करता है क्योंकि एक सूची समझ में <- के बाएं हाथ की ओर एक पैटर्न का उपयोग कर आइटम को छोड़ देता है वह पैटर्न से मेल नहीं खाता है।

Answer 4

यह फ़ंक्शन treeValue :: Tree a -> a कुल फ़ंक्शन नहीं हो सकता है, क्योंकि सभी Tree a मानों में वास्तव में आपके पास वापस आने के लिए a नहीं है! Leaf खाली सूची [] के समान है, जो अभी भी [a] टाइप है लेकिन वास्तव में a नहीं है।

मानक पुस्तकालय से head समारोह प्रकार [a] -> a है, और यह भी समय के सभी काम नहीं कर सकते हैं:

*Main> head [] 
*** Exception: Prelude.head: empty list 

आप treeValue लिख सकता है इसी तरह व्यवहार करने के लिए:

treeValue :: Tree a -> a 
treeValue Leaf = error "empty tree" 
treeValue (Node n _ _) = n 

लेकिन यह वास्तव में आपकी मदद नहीं करेगा, क्योंकि अब map treeValue xsLeaf मानों में से कोई एक त्रुटि फेंक देगा ।

अनुभवी हास्केलर्स आमतौर पर head का उपयोग करने से बचने की कोशिश करते हैं और इस तरह के कार्यों के लिए इस तरह के कार्यों का उपयोग करते हैं। निश्चित रूप से, किसी भी [a] या Tree a से a प्राप्त करने का कोई तरीका नहीं है, लेकिन शायद आपको इसकी आवश्यकता नहीं है। आपके मामले में, तुम सच में एक सूची Tree की से एक सूची a की पाने के लिए कोशिश कर रहे हैं, और आप खुश हैं Leaf बस अपनी सूची में कुछ भी नहीं योगदान करने के लिए के लिए के बजाय एक त्रुटि फेंक देते हैं। लेकिन treeValue :: Tree a -> a आपको इसे बनाने में मदद नहीं करता है। यह आपकी समस्या का समाधान करने में आपकी सहायता के लिए गलत फ़ंक्शन है।

एक ऐसा फ़ंक्शन जो आपको जो कुछ भी करने में मदद करता है वह Tree a -> Maybe a होगा, जैसा कि कुछ अन्य उत्तरों में बहुत अच्छी तरह से समझाया गया है। इससे आपको बाद में यह तय करने की अनुमति मिलती है कि "लापता" मान के बारे में क्या करना है।जब आप Maybe a का उपयोग करने के लिए जाते हैं, तो वास्तव में कुछ और करने के लिए नहीं है, तो आप error पर कॉल कर सकते हैं (या fromJust का उपयोग करें जो ठीक है), या आप तय कर सकते हैं कि और क्या करना है। लेकिन treeValue जो कि किसी भी से a वापस करने में सक्षम होने का दावा करता है और फिर error पर कॉल करता है, जब यह किसी कॉलर से इनकार नहीं कर सकता है कि a कोई क्या नहीं है तो क्या करना है।