मैं हैकेल में बाइनरी ट्री सर्च एल्गोरिदम को लागू करने की कोशिश कर रहा हूं।

data BinTree k d = 
   Branch (BinTree k d) (BinTree k d) k d 
  | Leaf k d 
  | Empty
  deriving (Eq, Show)

डेटा संरचना है जिसका उपयोग मैं अपने बाइनरी पेड़ को पकड़ने के लिए कर रहा हूं। समस्या यह है कि मुझे नहीं पता कि अगर हमें मूल्य नहीं मिल रहा है तो क्या वापस करना है। मेरे पास अब तक मेरे खोज फ़ंक्शन के लिए यही है:

lkp :: (Monad m, Ord k) => BinTree k d -> k -> m d
lkp (Leaf a b) x
  | a == x = return(b)
lkp (Branch lSub rSub a b) x
  | a < x = lkp rSub x
  | a > x = lkp lSub x
  | a == x = return(b)

मैं परीक्षणों में देख सकता हूं कि परीक्षण [] के वापसी मूल्य की अपेक्षा करता है, फिर भी मैं यह नहीं समझ सकता कि हम इस खाली मूल्य को कैसे वापस करते हैं। यह उन परीक्षणों में से एक का एक उदाहरण है:

testCase "3 in Leaf 5 500 ([]))[1 mark]"
    (lkp (Leaf 5 500) 3 @?= [] ) 
4
user14774406 6 पद 2020, 17:15

1 उत्तर

सबसे बढ़िया उत्तर

इसलिए हम "शून्य" या "खाली" मान वापस करने का एक तरीका याद करते हैं।

सौभाग्य से, हास्केल बेस लाइब्रेरी (प्रस्तावना) मोनाडप्लस वर्ग। मोनाडप्लस मोनाड का एक विशिष्ट संस्करण है, जो नियमित मोनाड इंटरफ़ेस को mzero और mplus के साथ बढ़ाता है, जो अनिवार्य रूप से एक मोनोइड जैसी संरचना प्रदान करता है। सिद्धांत यहां हास्केल विकी पर

MonadPlus का प्रयोग करके, lkp के लिए कूट इस प्रकार लिखा जा सकता है:

import Control.Monad

data BinTree k d = 
       Branch (BinTree k d) (BinTree k d) k d 
    |  Leaf k d 
    |  Empty
  deriving (Eq, Show)

lkp :: (MonadPlus m, Ord k) => BinTree k d -> k -> m d
lkp (Branch lSub rSub a b) x
  | a < x      =  lkp rSub x
  | a > x      =  lkp lSub x
  | otherwise  =  return b
lkp (Leaf a b) x  =  if (a == x)  then  (return b)  else  mzero
lkp Empty      _  =  mzero

नोट:: मैं एक नकली “गैर-विस्तृत पैटर्न” चेतावनी को शांत करने के लिए समानता परीक्षण के बजाय otherwise कीवर्ड का उपयोग कर रहा हूं।

ghci के तहत परीक्षण:

 λ> 
 λ> :load q65169028.hs
[1 of 1] Compiling Main             ( q65169028.hs, interpreted )
Ok, one module loaded.
 λ> 
 λ> tr1 = Branch (Leaf 1 2) (Branch (Leaf 5 6) (Branch (Leaf 9 10) (Leaf 17 18) 13 14) 7 8) 3 4
 λ> 
 λ> (lkp tr1 7) :: [Int]
[8]
 λ> 
 λ> (lkp tr1 8) :: [Int]
[]
 λ> 
 λ> (lkp tr1 17) :: [Int]
[18]
 λ> 

हम दुभाषिया को हमारे MonadPlus उदाहरण के रूप में सूचियों को चुनने के लिए बाध्य करना चाहते हैं, इसलिए प्रत्येक पंक्ति के अंत में :: [Int] हस्ताक्षर टाइप करें।

यदि यह बहुत बोझिल लगता है, तो यह हमेशा संभव है कि विशेषज्ञ lkp आगे इस तरह से कार्य करें:

llkp :: Ord k => BinTree k d -> k -> [d]
llkp tr x = lkp tr x
1
jpmarinier 6 पद 2020, 22:00