प्रकार के साथ टाइपक्लास के उदाहरणों के लिए पैरामीटर बाधाएं टाइप करें * -> *

Question

मान लीजिए कि मेरे पास Heap a प्रकार है जहां Heap प्रकार * -> * प्रकार का प्रकार है। ढेर पर कई बुनियादी परिचालनों को a प्रकार Ord प्रकार वर्ग का उदाहरण होने की आवश्यकता होती है।

data Heap a = ... 

findMin :: Ord a => Heap a -> a 
deleteMin :: Ord a => Heap a -> Heap a 

मैं (यह findMin और deleteMin कार्यों के माध्यम से व्यक्त करने के लिए आसान हो जाएगा) जैसे ही a प्रकार पैरामीटर Ord प्रकार वर्ग का एक उदाहरण है Foldable प्रकार वर्ग का एक उदाहरण के रूप में मेरे Heap प्रकार की घोषणा करना चाहते हैं।

संबंध इस तरह की easely व्यक्त किया जा सकता है जब हम प्रकार कक्षाएं उस तरह * के प्रकार की आवश्यकता होती है, के साथ काम कर Show की तरह: Foldable की घोषणा के साथ

instance Show a => Show (Heap a) where 
    show h = ... 

लेकिन मैं समस्याओं:

instance Foldable Heap where 
    -- Ouch, there is no `a` type parameter to put the constraint on! 
    foldr f z h = ... 

क्या इस तरह की घोषणा घोषणा में a टाइप पैरामीटर पर बाधा डालना संभव है?

Answer 1

सामान्य रूप से, नहीं, जब टाइप कन्स्ट्रक्टर को उदाहरण दिया जाता है, तो इसके प्रकारों को बाधित करने का कोई तरीका नहीं है। ज्यादातर यह एक अच्छी बात है, क्योंकि यह सुनिश्चित करता है कि उदा। Functor उदाहरण वास्तव में उनके तत्व प्रकार के बारे में अज्ञेयवादी हैं, जो अच्छे और अनुमानित व्यवहार को अच्छे और अनुमानित रखने में मदद करता है।

कभी-कभी इसकी बजाय परेशानी होती है, और सबसे आम उदाहरण वास्तव में एक क्रमबद्ध डेटा संरचना के लिए Ord बाधा की आवश्यकता होती है जो अन्यथा एक अच्छा, अच्छी तरह से व्यवहार किया जा सकता है।

कुछ प्रयोगात्मक तकनीकें हैं जिनमें बाधाएं जैसे सामान शामिल हैं, लेकिन आपके विशिष्ट मामले में पहले से ही एक व्यवहार्य समाधान है। यदि आप Foldable की परिभाषा को देखते हैं, तो यह कहता है कि केवल foldMap या foldr लागू करने की आवश्यकता है, इसलिए हम उन पर विचार करेंगे। नोट प्रकार:

foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m 
foldr :: (Foldable t) => (a -> b -> b) -> b -> t a -> b 

दोनों मामलों में, एक Foldable उदाहरण के साथ प्रकार केवल कार्य करने के लिए एक तर्क के रूप में एक बार दिखाई देता है,। इस वजह से, आप एक Ord बाधा के साथ use GADTs कर सकते हैं:

data Heap a where 
    Heap :: (Ord a) => ... 

ऐसा करने से, आप एक Ord उदाहरण किसी भी समय आप बनाने एक Heap मूल्य, यहां तक ​​कि एक खाली ढेर की आवश्यकता होगी; लेकिन जब आप Heap मान प्राप्त करते हैं, तो उस पर मिलान करने वाला पैटर्न Ord उदाहरण वापस दायरे में लाएगा - यहां तक ​​कि Foldable उदाहरण के अंदर भी!

ध्यान दें कि यह कई अन्य स्थितियों में मदद नहीं करता है:

fmap :: (Functor f) => (a -> b) -> f a -> f b 

यहाँ हम a पर एक Ord उदाहरण मिल सकता है, लेकिन हम भी b के लिए एक आवश्यकता होगी, जो संभव नहीं है।

return :: (Monad m) => a -> m a 

यहां हमें Ord उदाहरण भी प्रदान करने की आवश्यकता है।

Answer 2

हैकेज पर keys लाइब्रेरी पर एक नज़र डालें। जांचें कि क्या इसकी FoldableWithKey टाइप क्लास आपको चाहिए।