Travers olabilen, her zaman bir monad ile keyfi bir monadın kompozisyonu mu?

Question

İki tane Monad'ım m ve n ve n geçiş yapılabilirse, mutlaka bir bileşik m -over-n monad'ım var mı? Doğal olarak

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 

, bu tip kontroller ve ben kontrol birkaç durumlar için çalışmalarını inanıyoruz (List üzerinde Okuyucu, Devlet List üzerinden) -:

Daha biçimsel olarak, aşağıda aklımda ne var olarak, kompoze 'monad' monad yasalarını tatmin - ama bu Traversable biri üzerinden herhangi bir monad katman için genel tarifi ise ben emin değilim.

Answer 1

Hayır, her zaman bir monad değil. İki monadın monad operasyonları vedağıtım kanunu ile ilgili olarak, örneğin Wikipedia numaralı telefondan açıklanan ek uyumluluk koşullarına ihtiyacınız vardır. ; Üzere [x]> SX gönderme x -

Your previous question

birimi ile, X uyumluluğu koşullar, yani

S = m = [] yerine edildiği bir örnek verir

T = n = (->) Bool

, veya eşdeğer Teksas = X x x, ünitesi X ile -> TX gönderme x (x, x).

Vikipedi sayfasında sağ alt diyagram kompozisyon S beri gidip gelmez -> TS -> ST xs :: [a](xs,xs) ve daha sonra xs çekilen tüm çiftleri Kartezyen ürüne gönderir; Sağ haritası S ise -> ST sadece çift xs yılında x için (x,x) oluşan "diyagonal" için xs gönderir. Önerilen monadın birim yasalardan birini tatmin etmemesine neden olan aynı sorundur.

Answer 2

Birkaç ek açıklamalar, Reid Barton's general answer ve somut soru daha açık arasındaki bağlantıyı yapmak için. Bu durumda

, gerçekten join açısından sizin Monad örneğini çalışmak için işe yarar:

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

uygun yerlere compose/getCompose reintroducing ve m >>= f = join (fmap f m) kullanarak, bu gerçekten olduğunu doğrulayabilir Tanımınıza eşdeğerdir (prebind'un bu denklemde fmap f olduğunu unutmayın).

Bu tanım

rahat şemalar ile yasaları doğrulamak mümkün kılar.

 

    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 

genel dikdörtgen monad yasası: Burada join . return = id yani (fmap join . join . fmap sequence) . (return . return) = id için biridir

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

mutlaka kareler arasında her iki yönde aynı parçalar yok sayarak, gördüğümüz iki sağdaki o aynı yasaya kareler tutar. (Tabii ki, bu "kareler" ve "dikdörtgenler" diye adlandırmak biraz saçma, ama sahip oldukları tüm id yanları göz önüne alındığında, sınırlı ASCII sanat becerilerime daha iyi uyuyor.) Ilk kare olsa da, ... Reid Barton bahseder Vikipedi sayfasında sağ alt diyagramıdır sequence . return = fmap return e

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

tutarlar ... ve daha o tuttuğunu öne süren verildiği gibi Reid Barton ait olmayan cevap gösterir. Biz join . fmap return = id yasaya aynı stratejiyi uygularsanız

, sağ üst diyagram, sequence . fmap return = return, gelirse - ki (derhal sonucu) sadece olduğu gibi, ancak, kendi başına bir sorun olmadığını Traversable kimlik yasası. Son olarak, join . fmap join = join . join kanunu ile aynı şeyi yapmak diğer iki diyagramı yapar - sequence . fmap join = join . fmap sequence . sequence ve sequence . join = join . sequence . fmap sequence - bahar ileriye.

---

Dipnotlar: steno için

1. Açıklama: rreturn olduğunu ssequence ve j olduğunu join olduğunu. Fonksiyon kısaltmalarından sonra gelen büyük harfler ve sayılar, ilgili monadı ve 'un sokulmuş veya değiştirilmiş katmanını - s'da sona erdirir, yani başlangıçta başlangıçtaki iç katmanı ifade eder. dış katmanın her zaman bir T olduğunu biliyoruz. Katmanlar sıfırdan başlayarak aşağıdan yukarıya doğru numaralandırılır. Kompozisyon, birinci fonksiyonun altındaki ikinci fonksiyon için kısayol yazılarak gösterilir.