एसोसिएटेड प्रकार और कंटेनर तत्व

Question

मुझे लगता है कि मैंने इसे किसी समय पर हास्केल-कैफे पर पूछा होगा, लेकिन अगर मैं अब जवाब पा सकता हूं तो शापित हो गया ... इसलिए मैं इसे फिर से पूछ रहा हूं, इसलिए उम्मीद है कि भविष्य में मैं कर सकता हूं उत्तर उत्तर मिला!

पैरास्केट्रिक पॉलिमॉर्फिज्म से निपटने पर हास्केल शानदार है। लेकिन मुसीबत यह है कि सब कुछ पैरामीट्रिक नहीं है। एक मामूली उदाहरण के रूप में, मान लें कि हम डेटा के पहले तत्व को कंटेनर से बाहर ले जाना चाहते हैं। एक पैरामीट्रिक प्रकार के लिए, कि तुच्छ है:

 
class HasFirst c where 
    first :: c x -> Maybe x 

instance HasFirst [] where 
    first [] = Nothing 
    first (x:_) = Just x 

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

एसोसिएटेड प्रकार एक साफ रास्ता पूरी तरह से इन समस्याओं को ठीक करने के लिए प्रदान करते हैं:

 
class HasFirst c where 
    type Element c :: * 
    first :: c -> Maybe (Element c) 

instance HasFirst [x] where 
    type Element [x] = x 
    first [] = Nothing 
    first (x:_) = Just x 

instance HasFirst ByteString where 
    type Element ByteString = Word8 
    first b = b ! 0 

instance Ord x => HasFirst (Set x) where 
    type Element (Set x) = x 
    first s = findMin s 

हम अब एक नई समस्या है, लेकिन। Functor इतना है कि यह सभी कंटेनर प्रकार के लिए काम करता है "ठीक" करने की कोशिश कर विचार करें:

 
class Functor f where 
    type Element f :: * 
    fmap :: (Functor f2) => (Element f -> Element f2) -> f -> f2 

यह सब पर काम नहीं करता। यह कहता है कि यदि हमारे पास f के तत्व प्रकार f2 के तत्व प्रकार से कोई फ़ंक्शन है, तो हम f को f2 में बदल सकते हैं। अब तक सब ठीक है। हालांकि, स्पष्ट रूप से कोई रास्ता है कि f और f2समान प्रकार के कंटेनर हैं!

के तहत मौजूदा Functor परिभाषा, हम

 
fmap :: (x -> y) -> [x] -> [y] 
fmap :: (x -> y) -> Seq x -> Seq y 
fmap :: (x -> y) -> IO x -> IO y 

है लेकिन हम नहींfmap :: (x -> y) -> IO x -> [y] है। यह काफी असंभव है। लेकिन उपरोक्त वर्ग परिभाषा इसे अनुमति देता है।

क्या कोई जानता है कि टाइप सिस्टम को कैसे समझाया जाए, मैं वास्तव में का मतलब था?

संपादित

एक कंटेनर प्रकार से एक तत्व प्रकार गणना करने के लिए एक तरह से परिभाषित करते हुए ऊपर काम करता है। क्या होता है यदि आप इसे दूसरी तरफ करने की कोशिश करते हैं? किसी तत्व प्रकार से कंटेनर प्रकार की गणना करने के लिए फ़ंक्शन को परिभाषित करें? क्या यह किसी भी काम से बाहर काम करता है?

Answer 1

ठीक है, समस्या यह है कि यह स्पष्ट नहीं है कि संशोधित Functor का अर्थ क्या है। उदाहरण के लिए, ByteString पर विचार करें। ByteString को प्रत्येक Word8 तत्व को उसी प्रकार के साथ के तत्व के साथ प्रतिस्थापित करके केवल मैप किया जा सकता है। लेकिन Functorपैरामीट्रिक मैप्टेबल संरचनाओं के लिए है। यहां मैपिंग के वास्तव में दो विरोधी विचार हैं:

• कठोर मैपिंग (यानी।अपने प्रकार)
• पैरामीट्रिक मानचित्रण बदले बिना एक संरचना के प्रत्येक तत्व बदलने (यानी किसी भी प्रकार के लिए एक संरचना के प्रत्येक तत्व बदलने)

तो, इस मामले में, आप प्रकार व्यवस्था करने के लिए व्याख्या नहीं कर सकते क्या आपका मतलब था, क्योंकि यह ज्यादा समझ में नहीं आता है। हालांकि, आप बदल सकते हैं तुम क्या मतलब है :)

कठोर मानचित्रण प्रकार परिवारों के साथ व्यक्त करने के लिए आसान है:

class RigidMap f where 
    type Element f :: * 
    rigidMap :: (Element f -> Element f) -> f -> f 

जहाँ तक पैरामीट्रिक मानचित्रण के रूप में, वहाँ यह करने के लिए कई तरीके हैं। सबसे आसान तरीका वर्तमान Functor को बनाए रखना होगा। साथ में, इन कक्षाओं में ByteString, [], Seq जैसी संरचनाएं शामिल हैं, और इसी तरह। हालांकि, Ord मूल्यों पर बाधा के कारण, वे सभी Set और Map पर गिर जाते हैं। सौभाग्य से, constraint kinds विस्तार GHC 7.4 में आ रहा है हमें इस समस्या को ठीक कर सकते हैं:

class RFunctor f where 
    type Element f a :: Constraint 
    type Element f a =() -- default empty constraint 
    fmap :: (Element f a, Element f b) => (a -> b) -> f a -> f b 

यहाँ, हम कह रहे हैं कि हर मामले में एक संबद्ध typeclass बाधा होना चाहिए। उदाहरण के लिए, सेट उदाहरण में Element Set a = Ord a होगा, यह इंगित करने के लिए कि Set एस केवल तभी बनाया जा सकता है जब Ord उदाहरण प्रकार के लिए उपलब्ध हो। => के बाएं हाथ पर दिखाई देने वाली कुछ भी स्वीकार की जाती है। हम हमारे पिछले उदाहरणों परिभाषित कर सकते हैं बिल्कुल के रूप में वे थे, लेकिन हम भी Set और Map कर सकते हैं:

instance RFunctor Set where 
    type Element Set a = Ord a 
    fmap = Set.map 

instance RFunctor Map where 
    type Element Map a = Ord a 
    fmap = Map.map 

हालांकि, यह बहुत कठोर मानचित्रण और प्रतिबंधित पैरामीट्रिक मानचित्रण के लिए दो अलग-अलग इंटरफेस का उपयोग करने के लिए कष्टप्रद है। वास्तव में, बाद में पूर्व का सामान्यीकरण नहीं है? Set के बीच अंतर पर विचार करें, जिसमें केवल Ord, और ByteString के उदाहरण शामिल हो सकते हैं, जिनमें केवल Word8 s हो सकता है। निश्चित रूप से हम इसे एक और बाधा के रूप में व्यक्त कर सकते हैं?

class Mappable f where 
    type Element f :: * 
    type Result f a r :: Constraint 
    map :: (Result f a r) => (Element f -> a) -> f -> r 

विचार यहाँ:

हम एक ही चाल (यानी पूरी संरचना के लिए उदाहरणों देने के लिए और तत्व प्रकार का पर्दाफाश करने के एक प्रकार परिवार का उपयोग करें), और परिचय एक नया जुड़े बाधा परिवार HasFirst करने के लिए किया लागू यह है कि Result f a r मूल्य प्रकार (जैसे Ord a) पर आवश्यक बाधाओं को व्यक्त करता है, और भी परिणामस्वरूप कंटेनर प्रकार को बाधित करता है, हालांकि इसकी आवश्यकता होती है; संभवतः, यह सुनिश्चित करने के लिए कि a एस के समान-प्रकार के कंटेनर का प्रकार है। उदाहरण के लिए, Result [a] b r संभवतः r[b] है, और Result ByteString b r की आवश्यकता होगी bWord8 है, और rByteString है।

टाइप परिवार पहले से ही हमें "हमें" व्यक्त करने की आवश्यकता है: एक प्रकार की समानता बाधा। हम (a ~ b) => ... कह सकते हैं कि a और b एक ही प्रकार के हैं। हम निश्चित रूप से बाध्य परिवार परिभाषाओं में इसका उपयोग कर सकते हैं। तो, हमारे पास सबकुछ है जो हमें चाहिए; उदाहरणों पर:

instance Mappable [a] where 
    type Element [a] = a 
    type Result [a] b r = r ~ [b] 
    -- The type in this case works out as: 
    -- map :: (r ~ [b]) => (a -> b) -> [a] -> r 
    -- which simplifies to: 
    -- map :: (a -> b) -> [a] -> [b] 
    map = Prelude.map 

instance Mappable ByteString where 
    type Element ByteString = Word8 
    type Result ByteString a r = (a ~ Word8, r ~ ByteString) 
    -- The type is: 
    -- map :: (b ~ Word8, r ~ ByteString) => (Word8 -> b) -> ByteString -> r 
    -- which simplifies to: 
    -- map :: (Word8 -> Word8) -> ByteString -> ByteString 
    map = ByteString.map 

instance (Ord a) => Mappable (Set a) where 
    type Element (Set a) = a 
    type Result (Set a) b r = (Ord b, r ~ Set b) 
    -- The type is: 
    -- map :: (Ord a, Ord b, r ~ Set b) => (a -> b) -> Set a -> r 
    -- (note the (Ord a) constraint from the instance head) 
    -- which simplifies to: 
    -- map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b 
    map = Set.map 

बिल्कुल सही! हम किसी भी प्रकार के कंटेनर के लिए उदाहरण परिभाषित कर सकते हैं जो हम चाहते हैं, कठोर, पैरामीट्रिक या पैरामीट्रिक-लेकिन-प्रतिबंधित, और प्रकार पूरी तरह से काम करते हैं।

अस्वीकरण: मैंने अभी तक जीएचसी 7.4 की कोशिश नहीं की है, इसलिए मुझे नहीं पता कि इनमें से कोई वास्तव में संकलित या काम करता है, लेकिन मुझे लगता है कि मूल विचार ध्वनि हैं।

Answer 2

आप constraint kinds चाहते हैं, ghc 7.4 में उपलब्ध है।