2012-10-06 36 views
6

संभव डुप्लिकेट:
Making (a, a) a Functorक्यों (ए, ए) एक मजेदार नहीं है?

मैं quicksort के निम्नलिखित कार्यान्वयन लिखा है:

import Data.List (partition) 

quicksort [] = [] 

quicksort (x:xs) = 
    let (smaller, notSmaller) = partition (< x) xs 
    in quicksort smaller ++ x : quicksort notSmaller 

तब मैं quicksort करने के लिए दो पुनरावर्ती कॉल संक्षिप्त करना चाहता था fmap लगाने से सूची जोड़ी:

quicksort (x:xs) = 
    let (smaller, notSmaller) = fmap quicksort $ partition (< x) xs 
    in smaller ++ x : notSmaller 

लेकिन जाहिर है, (a, a) एक मजेदार नहीं है। ऐसा क्यों है? मैं एक प्रदान करने की कोशिश:

instance Functor (a, a) where 
    fmap f (x, y) = (f x, f y) 

लेकिन GHCi मेरी प्रयास पसंद नहीं आया:

Kind mis-match 
The first argument of `Functor' should have kind `* -> *', 
but `(a, a)' has kind `*' 
In the instance declaration for `Functor (a, a)' 

किसी को भी मुझे लगता है कि त्रुटि समझा सकते हैं? मैंने विभिन्न "फिक्स" की कोशिश की, लेकिन उनमें से कोई भी काम नहीं किया।

क्या (a, a)Functor का एक उदाहरण बनाना संभव है? या टाइप सिस्टम पर्याप्त अभिव्यक्तिपूर्ण नहीं है?

उत्तर

14

यह एहसास है कि यह (a,a) कि functor होगा नहीं है, उसी तरह से है कि Maybe a और [a] functors नहीं हैं महत्वपूर्ण है। इसके बजाए, मकान Maybe और [] हैं।

एक पूर्ण स्पष्टीकरण के लिए प्रकार की अवधारणा को शुरू करने की आवश्यकता है, जो "प्रकार के प्रकार" की तरह हैं। किसी भी ठोस प्रकार के प्रकार * है। प्रकार कन्स्ट्रक्टरMaybe या [] एक प्रकार लेता है और दूसरा प्रकार देता है, इसलिए इसमें * -> * है।

(,) (जोड़े के लिए निर्माता) का प्रकार क्या है? इसे दो प्रकार की जरूरत है, पहले स्लॉट के लिए एक और दूसरा स्लॉट के लिए, इसलिए इसमें * -> * -> * है।

आप केवल तरह * -> * की बातों से बाहर एक functor कर सकते हैं, तो आपके प्रश्न का संक्षिप्त उत्तर कोई है, तो आप एक functor में (,) नहीं कर सकता।

हालांकि, आप प्रकार को लपेटकर सीमा के चारों ओर प्राप्त कर सकते हैं। उदाहरण

newtype Pair a = P (a,a) 

instance Functor Pair where 
    fmap f (P (x,y)) = P (f x, f y) 

लिए newtype आवरण संकलक द्वारा दूर अनुकूलित किया जाएगा, तो यह किसी भी अधिक क्या आप मूल रूप से करने के लिए कोशिश कर रहे थे की तुलना में महंगा नहीं है - यह सिर्फ एक छोटे से अधिक वर्बोज़ है।

+0

आह, मैंने कोशिश की कि एक प्रकार (= ए, ए) टाइप करें और यह काम नहीं करता है। – fredoverflow

+0

@FredOverflow 'type' सी ++ में' typedef' के समान है; यह एक नया प्रकार नहीं बनाता है, केवल एक उपनाम (इसलिए इससे कोई फर्क नहीं पड़ता)। – qox