सवाल हास्केल: एक फोल्डबल का एक उदाहरण जो फंक्टर नहीं है (या ट्रैवर्सबल नहीं है)?


Foldable उदाहरण कुछ प्रकार के कंटेनर होने की संभावना है, और ऐसा होने की संभावना है Functor भी। वास्तव में, इस कहते हैं

Foldable प्रकार भी एक कंटेनर है (हालांकि कक्षा तकनीकी रूप से आवश्यक नहीं है Functorदिलचस्प, Foldableएस सब हैं Functorरों)।

तो क्या एक उदाहरण है Foldable जो स्वाभाविक रूप से नहीं है Functor या ए Traversable? (जो शायद हास्केल विकी पेज चूक गया :-))


44
2017-12-02 16:06


मूल




जवाब:


यहां एक पूरी तरह से पैरामीट्रिक उदाहरण है:

data Weird a = Weird a (a -> a)

instance Foldable Weird where
  foldMap f (Weird a b) = f $ b a

Weird नहीं है कोई Functor इसलिये a एक नकारात्मक स्थिति में होता है।


50
2017-12-02 16:41



ओह अच्छा! इसके बारे में भी सोचा नहीं था। आश्चर्य है कि अगर कोई है Foldable मानक-ईश पुस्तकालयों में उदाहरण जो असफल हो जाते हैं Functor contravariance के कारण? - C. A. McCann
मुझे लगता है कि आप इसे कुछ एक्सटेंशन के साथ कर सकते हैं और समानार्थी शब्द टाइप कर सकते हैं। - PyRulez
कैसा रहेगा instance Functor Weird where fmap fn (Weird a aa) = Weird (fn (aa a)) id? - Nikita Volkov
@NikitaVolkov अच्छा एक! लेकिन यह मज़ेदार कानूनों को पूरा नहीं करता है। fmap id == id - Sjoerd Visscher
@SjoerdVisscher निर्भर करता है। तकनीकी रूप से बोल रहा हूं Free monad कानूनों को संतुष्ट नहीं करता w.r.t. निश्चित समानता और इसी तरह से pipesकेवल उचित कानूनों को पूरा करें observe चश्मे। तो निश्चित समानता सबसे समझदार / उपयोगी / प्राकृतिक नहीं हो सकती है (उद्धरण प्राप्त करें उदा। जिसके लिए निश्चित समानता आपके द्वारा उपयोग की जाने वाली भाषा का एक कष्टप्रद आर्टिफैक्ट बन जाती है)। अब आपका Weird बहुत कुछ दिखता है Coyoneda। और आपका foldMap एक बहुत ही समान और विशिष्ट अर्थशास्त्र है: यह व्यवहार करता है Weird एक तत्व तत्व कंटेनर के रूप में और हमेशा उस संग्रहीत समारोह को लागू करता है। - user3237465


यहां एक आसान उदाहरण है: Data.Set.Setअपने आप को देखो।

यदि आप विशेष प्रकार के प्रकार की जांच करते हैं तो इसका कारण स्पष्ट होना चाहिए fold तथा map कार्यों के लिए परिभाषित किया गया Set:

foldr :: (a -> b -> b) -> b -> Set a -> b

map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b

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

दूसरी तरफ फोल्डिंग, हमेशा पेड़ को सारांश मूल्य उत्पन्न करने के लिए नष्ट कर देती है, इसलिए गुना के मध्यवर्ती परिणामों को सॉर्ट करने की आवश्यकता नहीं है। यहां तक ​​कि अगर गुना वास्तव में एक नया निर्माण कर रहा है Set, संतुष्ट करने की ज़िम्मेदारी Ord बाधा को पारित संचय समारोह पर बाधा है, न कि गुना।

वही शायद किसी भी कंटेनर प्रकार पर लागू होगा जो पूरी तरह से पैरामीट्रिक नहीं है। और की उपयोगिता दी Data.Set, यह टिप्पणी आपको "रोचक" के बारे में उद्धृत करती है Foldableमुझे लगता है कि थोड़ा संदिग्ध लगता है!


42
2017-12-02 16:16



यह वास्तव में एक उदाहरण है Foldable जिसे एक नहीं बनाया जा सकता है Functor। हालांकि, ऐसा लगता है कि हास्केल की टाइप सिस्टम "Set केवल समझ में आता है Ord प्रकार, और कुछ बनाने के लिए Functor केवल एक को परिभाषित करने की जरूरत है fmap किस प्रकार के बारे में अंतर्निहित कुछ के कारण, अन्य प्रकार के रूप में परिभाषित किए गए अर्थों के लिए Set तथा Functor प्रतिनिधित्व करते हैं। उदाहरण के लिए धन्यवाद, वैसे भी। :-) - Prateek
@Prateek: हाँ और नहीं। पूरी तरह से पैरामीट्रिक होने के नाते क्या बहुत निहित है Functor का प्रतिनिधित्व करता है। उस ने कहा, मानक हास्केल (वास्तव में जीएचसी द्वारा समर्थित पूर्ण प्रकार की प्रणाली सहित) से अधिक अभिव्यक्तिपूर्ण प्रकार प्रणाली "कुछ प्रकार के वर्गों पर पूरी तरह से पैरामीट्रिक" व्यक्त कर सकती है, जो यहां वांछित होगी। - C. A. McCann
@Prateek: एक और गणितीय भावना में, Functor केवल सभी प्रकार के फ़ैक्टरों को शामिल करता है, सभी हास्केल प्रकारों की श्रेणी से स्वयं की एक उचित उपश्रेणी पर। यह उन मकानों को व्यक्त नहीं कर सकता जो केवल उपश्रेणियों पर काम करते हैं, या अन्य चीजें जो अन्यथा समझ में आती हैं। उस ने कहा, Sjoerd विस्चर का उदाहरण मेरे से अधिक दिलचस्प और अधिक गूढ़ रहता है। :] - C. A. McCann
अगर हम साथ रहना चाहते हैं Set सामान केवल के लिए काम कर रहा है Ord प्रकार (भले ही गणित में सेटों में ऐसी कोई बाधा नहीं है), हमें उसी अपूर्णता को सहन करने के लिए तैयार होना चाहिए Functor भी। - Prateek
मुझे यकीन है कि Set स्वाभाविक रूप से आवश्यकता नहीं है Ord हर समय, केवल तभी जब आप "निरीक्षण" कर रहे हैं जैसे लंबाई की जांच करके, इसे एक स्ट्रिंग के रूप में प्रदर्शित करना, या न्यूनतम / अधिकतम तत्व आदि प्राप्त करना। तो अगर आपको अनुमति है Set कुछ परिस्थितियों में (उदा (+) <$> set) नहि हे Ord, और उसके बाद यह केवल घनत्व है और जब भी ऐसा होता है तो उसे फिर से व्यवस्थित करें Ord बाधा (इसलिए हाँ यह मानक हास्केल में नहीं किया जा सकता है, लेकिन मैं सैद्धांतिक / गणित दृष्टिकोण से अधिक सोच रहा हूं)। तो आप हो सकता है Set सच हो Functor, और यहां तक ​​कि एक Applicative और ए Monad। - semicolon


पढ़ना सुंदर तह  मुझे एहसास हुआ कि कोई भी Foldable एक बनाया जा सकता है Functor इसे लपेटकर

data Store f a b = Store (f a) (a -> b)

एक साधारण स्मार्ट नियंत्रक के साथ:

store :: f a -> Store f a a
store x = Store x id

(यह सिर्फ एक संस्करण है दुकान कॉमोनैड डेटा प्रकार।)

अब हम परिभाषित कर सकते हैं

instance Functor (Store f a) where
    fmap f (Store x g)   = Store x (f . g)

instance (F.Foldable f) => F.Foldable (Store f a) where
    foldr f z (Store x g)    = F.foldr (f . g) z x

इस तरह, हम दोनों बना सकते हैं Data.Set.Set और स्जोर्ड विस्चर का Weird एक मजेदार (हालांकि, चूंकि संरचना इसके मूल्यों को याद नहीं करती है, इसलिए बार-बार इसे घुमाकर बहुत अक्षम हो सकता है, अगर हम जिस फ़ंक्शन में उपयोग करते हैं fmap जटिल है।)


अद्यतन करें: यह एक संरचना का एक उदाहरण भी प्रदान करता है जो एक मज़ेदार, फोल्ड करने योग्य नहीं है लेकिन ट्रैवर्सबल है। बनाना Store ट्रैवर्सबल, हमें बनाना होगा (->) r traversable। तो हमें इसे लागू करने की आवश्यकता होगी

sequenceA :: Applicative f => (r -> (f a)) -> f (r -> a)

चलो ले लो Either b के लिये f। फिर हमें लागू करने की आवश्यकता होगी

sequenceA' :: (r -> Either b a) -> Either b (r -> a)

जाहिर है, ऐसा कोई फ़ंक्शन नहीं है (आप इसके साथ सत्यापित कर सकते हैं Djinn)। तो हम न तो महसूस कर सकते हैं sequenceA


22
2017-10-15 13:21



स्टोर डेटा प्रकार बिल्कुल किसी भी प्रकार के कन्स्ट्रक्टर पर फ्री फ़ैक्टर है, जिसे कोयोनोनिया भी कहा जाता है (hackage.haskell.org/package/kan-extensions-4.2.3/docs/...)। - Kris Nuttycombe
@KrisNuttycombe बिल्कुल नहीं। Coyoneda अस्तित्व में रूप से मात्राबद्ध है Store नहीं है। - Carl