क्या एक मनमाना मोनैड की संरचना हमेशा एक मोनड के साथ एक ट्रैवर्सबल है?

Question

यदि मेरे पास दो monads m और n हैं, और n ट्रैवर्सबल है, तो क्या मेरे पास एक समग्र m -over- n मोनड है?

अधिक औपचारिक रूप से, यहाँ मेरे मन में है:

import Control.Monad 
import Data.Functor.Compose 

prebind :: (Monad m, Monad n) => 
     m (n a) -> (a -> m (n b)) -> m (n (m (n b))) 
mnx `prebind` f = do nx <- mnx 
        return $ do x <- nx 
           return $ f x 

instance (Monad m, Monad n, Traversable n) => Monad (Compose m n) where 
    return = Compose . return . return 
    Compose mnmnx >>= f = Compose $ do nmnx <- mnmnx `prebind` (getCompose . f) 
            nnx <- sequence nmnx 
            return $ join nnx 

स्वाभाविक रूप से

, इस प्रकार के-जांच करता है, और मैं कुछ मामलों है कि मैं जाँच के लिए काम करता है विश्वास करते हैं (सूची से अधिक रीडर, राज्य सूची के ऊपर) - जैसा कि, 'मोनैड' बना हुआ मोनैड कानूनों को पूरा करता है - लेकिन मुझे यकीन नहीं है कि यह सामान्य नुस्खा है जो एक ट्रैवर्सबल पर किसी भी मोनैड को लेयर करने के लिए है।

Answer 1

नहीं, यह हमेशा एक मोनड नहीं होता है। Wikipedia पर उदाहरण के लिए वर्णित अनुसार, आपको दो monads के मोनड ऑपरेशंस और वितरण कानून sequence :: n (m a) -> m (n a) से संबंधित अतिरिक्त संगतता स्थितियों की आवश्यकता है। ;> SX के लिए [x] भेजने एक्स -

Your previous question एक उदाहरण है, जिसमें संगतता शर्तों को पूरा नहीं कर रहे हैं, अर्थात्

एस = m = [] एक्स देता है, यूनिट के साथ

टी = n = (->) Bool, या समकक्ष TX = X × X, इकाई एक्स के साथ -> TX x (x, x) भेज रहा है।

विकिपीडिया पृष्ठ पर निचले दाएं आरेख लिए निकल नहीं करता है, रचना एस के बाद से -> टीएस -> अनुसूचित जनजाति xs :: [a](xs,xs) के लिए और फिर xs से तैयार सभी जोड़ों की कार्तीय उत्पाद के लिए भेजता है; जबकि दाएं हाथ का नक्शा एस -> एसटी xs को "विकर्ण" में भेजता है जिसमें xxs में जोड़े गए हैं। यह वही समस्या है जिसने आपके प्रस्तावित मोनड को यूनिट कानूनों में से एक को संतुष्ट नहीं किया है।

Answer 2

Reid Barton's general answer और आपके ठोस प्रश्न के बीच कनेक्शन को और अधिक स्पष्ट बनाने के लिए कुछ अतिरिक्त टिप्पणियां।

इस मामले में, यह वास्तव में बंद का भुगतान करती है join के संदर्भ में अपने Monad उदाहरण बाहर काम करने के:

join' :: m (n (m (n b))) -> m (n b) 
join' = fmap join . join . fmap sequence 

उपयुक्त स्थानों में compose/getCompose में पुनः और m >>= f = join (fmap f m) का उपयोग करके आप सत्यापित कर सकते हैं कि यह वास्तव में है आपकी परिभाषा के समतुल्य (ध्यान दें कि उस समीकरण में fmap f पर आपकी prebind मात्रा है)।

यह परिभाषा आरेखों के साथ कानूनों को सत्यापित करने में सहज बनाती है।

 

    MT id  MT id MT id MT 
    ---->  ---->  ----> 
rT2 | | rT1 | | rT1 | | id 
rM3 V V rM3 V V  V V 
    ---->  ---->  ----> 
MTMT sM2 MMTT jM2 MTT jT0 MT 

समग्र आयत इकाई कानून है:: यहाँ join . return = id यानी (fmap join . join . fmap sequence) . (return . return) = id के लिए एक है

 
M id M 
    ---->  
rM1 | | id 
    V V 
    ---->  
MM jM0 M 

भागों जरूरी है कि एक ही वर्ग में दोनों तरीके हैं की अनदेखी कर, हम देखते हैं कि दो सबसे दायां वर्ग एक ही कानून के लिए राशि। (यह निश्चित रूप से इन "वर्गों" और "आयताकारों" को कॉल करने के लिए थोड़ा मूर्ख है, उनके पास id पक्ष हैं, लेकिन यह मेरे सीमित ASCII कला कौशल को बेहतर बनाता है।) पहले वर्ग है, हालांकि, sequence . return = fmap return, जो विकिपीडिया पृष्ठ रीड बार्टन का उल्लेख में निचले दाहिने चित्र है के बराबर है ...

 
M id M 
    ---->  
rT1 | | rT0 
    V V 
    ---->  
TM sM1 MT 

... और यह नहीं है एक दिया है कि, धारण के रूप में रीड बार्टन की जवाब दिखाता है।

यदि हम join . fmap return = id कानून के लिए समान रणनीति लागू करते हैं, तो ऊपरी दाएं आरेख, sequence . fmap return = return दिखाता है - हालांकि, यह स्वयं में और कोई समस्या नहीं है, क्योंकि यह केवल (तत्काल परिणाम) है Traversable का पहचान कानून। अंत में, join . fmap join = join . join कानून के साथ एक ही काम करने से अन्य दो आरेख - sequence . fmap join = join . fmap sequence . sequence और sequence . join = join . sequence . fmap sequence - वसंत आगे बढ़ते हैं।

---

फुटनोट:

आशुलिपि के लिए

1. लीजेंड: rreturn है, ssequence और j है join है। s के मामले में, वह यह है कि क्या शुरू में भीतरी परत को संदर्भित करता है इस के रूप में - अपर केस अक्षर और अंक समारोह संक्षिप्त रूपों के बाद शामिल इकाई और स्थिति इसकी शुरुआत की या परिवर्तित परत पर समाप्त होता है को स्पष्ट मामला हम जानते हैं कि बाहरी परत हमेशा T है। शून्य से शुरू होने वाली परतों को नीचे से ऊपर तक गिना जाता है। संरचना को पहले चरण के नीचे दूसरे समारोह के लिए शॉर्टेंड लिखकर इंगित किया जाता है।