एक हे लागू हास्केल

Question

में द्विआधारी खोज के पेड़ के लिए (लॉग एन) Foldable.elem

पर विचार करें द्विआधारी पेड़ों के लिए निम्नलिखित परिभाषा:

data Tree a = Nil | Node (Tree a) a (Tree a) 

Foldable उदाहरण में परिभाषित किया जा सकता है:

instance Foldable Tree where 
    foldr _ z Nil = z 
    foldr f z (Node l d r) = foldr f (f d (foldr f z l)) r 

लेकिन समस्या यह है कि elem फ़ंक्शन O(log n) के बजाय O(n) में चलता है। जब मैं एक कस्टम elem लागू करने के लिए प्रयास करें:

elem x Nil = False 
elem x (Node l d r) 
    | x == d = True 
    | x < d = elem x l 
    | otherwise = elem x r 

मैं Could not deduce (Ord a) arising from a use of ‘<’ मिलता है। इस समस्या को कैसे ठीक किया जा सकता है?

Answer 1

आप, Foldable वर्ग के लिए इस elem विधि का उपयोग नहीं कर सकते हैं के बाद से Foldable एपीआई केवल एक Eq उदाहरण के साथ किसी भी प्रकार का कोई भी तत्व के लिए खोज करने के लिए सक्षम होने के लिए अपने उदाहरणों में से सभी के लिए elem कार्यान्वयन की आवश्यकता है। "elem जो सभी Eq के लिए पॉलिमॉर्फिक है" Foldable टाइपक्लास के डिजाइन में एक जानबूझकर विकल्प था।

आपका elem समारोह, बहुत ही उपयोगी है, जबकि, नहीं Foldable typeclass के लिए elem विधि के साथ संगत है, क्योंकि यह typeclass की इच्छाओं के लिए पर्याप्त सामान्य नहीं है। आपके प्रकार के लिए elem फ़ंक्शन निर्यात करने का सबसे अच्छा तरीका टाइपक्लास के बाहर एक अलग फ़ंक्शन को परिभाषित करना होगा।