क्या फ़ंक्चर अद्वितीय हैं?

Question

मैं सोच रहा था कि Functor हास्केल में उदाहरण फ़ैक्टर कानूनों द्वारा निर्धारित (विशिष्ट रूप से) हैं।

ghc कम से कम "रन-ऑफ-द-मिल" डेटा प्रकारों के लिए Functor उदाहरण प्राप्त कर सकते हैं, ऐसा लगता है कि वे कम से कम विभिन्न मामलों में अद्वितीय होना चाहिए।

सुविधा के लिए, Functor परिभाषा और functor कानून हैं:

class Functor f where 
    fmap :: (a -> b) -> f a -> f b 

fmap id = id 
fmap (g . h) = (fmap g) . (fmap h) 

सवाल:

• एक धारणा से शुरू map की परिभाषा प्राप्त कर सकते हैं कि यह data List a = Nil | Cons a (List a) के लिए एक उदाहरण है Functor ? यदि हां, तो ऐसा करने के लिए क्या धारणाएं की जानी चाहिए?

• क्या कोई हैस्केल डेटा प्रकार है जिसमें एक से अधिक Functor उदाहरण हैं जो मज़ेदार कानूनों को पूरा करते हैं?

• ghcfunctor उदाहरण कब प्राप्त कर सकता है और यह कब नहीं हो सकता है?

• क्या यह सब निर्भर करता है कि हम समानता को कैसे परिभाषित करते हैं? Functor कानूनों की समानता के संदर्भ में कानून व्यक्त किए जाते हैं, फिर भी हमें Functors की आवश्यकता नहीं है Eq उदाहरण हैं। तो क्या यहां कुछ विकल्प है?

समानता के बारे में, निश्चित रूप से मैं क्या "निर्माता समानता" जो हमें कारण है कि [a,a,a] किसी भी प्रकार की a के किसी भी मूल्य के लिए "बराबर" [a,a,a] भले ही a नहीं है की अनुमति देता है फोन की एक धारणा है (==) इसके लिए परिभाषित किया गया। समानता के सभी अन्य (उपयोगी) विचार शायद इस समकक्ष संबंध हैं। लेकिन मुझे संदेह है कि Functor कानूनों में समानता एक "तर्कसंगत समानता" संबंध से अधिक है और आवेदन विशिष्ट हो सकती है। इस पर कोई विचार?

Answer 1

देखें ब्रेंट Yorgey के Typeclassopedia:

कुछ अन्य प्रकार के वर्गों हम सामना करेंगे के विपरीत, एक दिया प्रकार functor के सबसे कम एक वैध उदाहरण है। can be provenfree theorem के माध्यम से fmap के प्रकार के लिए। वास्तव में, GHC can automatically derive कई डेटा प्रकारों के लिए फंक्टर उदाहरण।

Answer 2

"जब GHC एक functor उदाहरण निकाले जाते हैं और जब यह नहीं कर सकते हैं कर सकते हैं?"

जब हमारे पास जानबूझकर परिपत्र डेटा संरचनाएं होती हैं। प्रकार प्रणाली हमें मजबूर परिपत्र के हमारे इरादे को व्यक्त करने की अनुमति नहीं देती है। तो, ghc एक उदाहरण प्राप्त कर सकता है, समान जिसे हम चाहते हैं, लेकिन समान नहीं।

---

परिपत्र डेटा संरचनाओं शायद ही इस मामले में जहां functor एक अलग तरीके से लागू किया जाना चाहिए रहे हैं। लेकिन फिर फिर, यह वही अर्थपूर्ण होगा।

data HalfEdge a = HalfEdge { label :: a , companion :: HalfEdge a } 

instance Functor HalfEdge where 
    fmap f (HalfEdge a (HalfEdge b _)) = fix $ HalfEdge (f a) . HalfEdge (f b) 

---

संपादित करें:

HalfEdges संरचनाओं कि एक ग्राफ है, जहां आप दोनों छोर के लिए एक संदर्भ हो सकता है में किनारों अनिर्दिष्ट का प्रतिनिधित्व करते हैं (कंप्यूटर ग्राफिक्स, 3 डी meshes ... में जाना जाता है) कर रहे हैं। आम तौर पर वे पड़ोसी हाफएजेस, नोड्स और चेहरे के लिए अधिक संदर्भ संग्रहीत करते हैं।

newEdge :: a -> a -> HalfEdge a 
newEdge a b = fix $ HalfEdge a . HalfEdge b 

शब्दार्थ, वहाँ कोई fix $ HalfEdge 0 . HalfEdge 1 . HalfEdge 2 है, क्योंकि किनारों हमेशा ठीक दो आधा किनारों से बाहर बना रहे हैं।

---

संपादित करें 2:

Haskell समुदाय में, बोली डेटा संरचना इस तरह के लिए जाना जाता है "गाँठ मिलाकर"। यह उन डेटा संरचनाओं के बारे में है जो अर्थात् अनंत हैं क्योंकि वे चक्र हैं। वे केवल सीमित स्मृति का उपभोग करते हैं। उदाहरण:

twos = fmap (+1) ones 
twos = fix ((+1)(head ones) :) 

अगर हम (पहले n के तत्वों) पार twos और अभी भी उस सूची के शुरू करने के लिए एक संदर्भ है, इन कार्यान्वयन की गति में मतभेद है (: ones = 1:ones को देखते हुए, हम twos के इन शब्दार्थ बराबर कार्यान्वयन होगा हर बार बनाम 1 + 1 का मूल्यांकन करें) और स्मृति खपत (ओ (एन) बनाम ओ (1))।