I trasformatori applicativi sono davvero superflui?

Question

C'è un gran parlare di Applicativenon necessitano di una propria classe di trasformatore, come questo:

class AppTrans t where 
    liftA :: Applicative f => f a -> t f a 

Ma posso definire trasformatori applicative che non sembrano essere composizioni di applicativi! Ad esempio sideeffectful flussi:

data MStream f a = MStream (f (a, MStream f a)) 

sollevamento esegue solo l'effetto collaterale ad ogni passo:

instance AppTrans MStream where 
    liftA action = MStream $ (,) <$> action <*> pure (liftA action) 

E se f è un applicativo, quindi MStream f è così:

instance Functor f => Functor (MStream f) where 
    fmap fun (MStream stream) = MStream $ (\(a, as) -> (fun a, fmap fun as)) <$> stream 

instance Applicative f => Applicative (MStream f) where 
    pure = liftA . pure 
    MStream fstream <*> MStream astream = MStream 
     $ (\(f, fs) (a, as) -> (f a, fs <*> as)) <$> fstream <*> astream 

So che per qualsiasi scopo pratico, f dovrebbe essere una monade:

joinS :: Monad m => MStream m a -> m [a] 
joinS (MStream stream) = do 
    (a, as) <- stream 
    aslist <- joinS as 
    return $ a : aslist 

Ma mentre c'è un'istanza Monad per MStream m, è inefficiente. (O anche errato?) L'istanza Applicative è effettivamente utile!

Ora di notare che i flussi usuali nascono come casi particolari per il funtore identità:

import Data.Functor.Identity 
type Stream a = MStream Identity a 

Ma la composizione di Stream e f non è MStream f! Piuttosto, Compose Stream f a è isomorfo a Stream (f a).

Mi piacerebbe sapere se MStream è una composizione di due applicazioni qualsiasi.

Edit:

mi piacerebbe offrire un punto di vista teorico categoria. Un trasformatore è un endofuncore "bello" t nella categoria C di funtori applicativi (vale a dire fasci monoidali con forza), insieme a una trasformazione naturale liftA dall'identità su C a t. La domanda più generale è ora quali esistono trasformatori utili che non sono della forma "comporre con g" (dove g è un applicativo). La mia richiesta è che MStream sia uno di questi.

Answer 1

Ottima domanda! Credo che ci siano due diverse parti di questa domanda:

1. Composizione applicativi o monadi esistenti in quelli più complessi.
2. Costruzione di tutti gli applicativi/monadi da un determinato set iniziale.

annuncio 1: I trasformatori di Monad sono essenziali per la combinazione di monadi. Monadi don't compose directly.Sembra che ci debba essere un po 'di informazioni aggiuntive fornite dai trasformatori di Monade che indicano come ogni monade può essere composta con altre monadi (ma potrebbe essere che questa informazione sia già in qualche modo presente, vedi Is there a monad that doesn't have a corresponding monad transformer?).

D'altra parte, gli compongono direttamente, vedere Data.Functor.Compose. Questo è il motivo per cui non sono necessari trasformatori applicativi per la composizione. Sono anche chiusi sotto product (ma non coproduct).

Ad esempio, avere infinite streamsdata Stream a = Cons a (Stream a) e un altro applicativo g, sia Stream (g a) e g (Stream a) sono applicativi.

Ma anche se Stream è anche una monade (join prende la diagonale di un flusso 2-dimensionale), la composizione con un altro monade m non sarà, né Stream (m a) né m (Stream a) sarà sempre una monade.

Inoltre come possiamo vedere, sono entrambi diverso dal vostro MStream g (che è molto vicino a ListT done right), quindi:

annuncio 2 .: possono tutti applicativi essere costruito da un dato insieme di primitive? Apparentemente no. Un problema è la costruzione di tipi di dati di somma: se f e g sono applicativi, Either (f a) (g a) non sarà, poiché non sappiamo come comporre Right h <*> Left x.

Un'altra primitiva di costruzione sta prendendo un punto fisso, come nell'esempio MStream. Qui potremmo tentare di generalizzare la costruzione attraverso la definizione di qualcosa come

newtype Fix1 f a = Fix1 { unFix1 :: f (Fix1 f) a } 

instance (Functor (f (Fix1 f))) => Functor (Fix1 f) where 
    fmap f (Fix1 a) = Fix1 (fmap f a) 

instance (Applicative (f (Fix1 f))) => Applicative (Fix1 f) where 
    pure k = Fix1 (pure k) 
    (Fix1 f) <*> (Fix1 x) = Fix1 (f <*> x) 

(che richiede non-così-bello UndecidableInstances) e poi

data MStream' f g a = MStream (f (a, g a)) 

type MStream f = Fix1 (MStream' f)