E 'possibile implementare `(Applicativo m) => Applicativo (StatoT s m)`?

Question

Attualmente sto lavorando su Data.Fresh e Control.Monad.Trans.Fresh, che risp. definire un'interfaccia per generare nuove variabili e un trasformatore monad che implementa questa interfaccia.

Inizialmente ho pensato che sarebbe stato possibile implementare l'istanza Applicative per il mio FreshT v m con l'unico requisito che esista Applicative m. Tuttavia, mi sono bloccato e mi è sembrato di dover richiedere Monad m. Non fidandosi mia Haskell-fu, ho poi girato al pacchetto trasformatori, e sono rimasto sorpreso da ciò che ho trovato in Control.Monad.Trans.State.Lazy e .Strict:

instance (Functor m, Monad m) => Applicative (StateT s m) where 
    pure = return 
    (<*>) = ap 

Quindi ecco la mia domanda: è possibile creare un'istanza con la semantica equivalenti con la testa dell'istanza seguente?

instance (Applicative m) => Applicative (StateT s m) where 

Answer 1

consideri che si hanno due funzioni:

f :: s -> m (s, a -> b) 
g :: s -> m (s, a) 

e si desidera creare una funzione h = StateT f <*> StateF g

h :: s -> m (s, b) 

Da quanto sopra si hanno un s è possibile passare a f in modo da avere:

f' :: m (s, a -> b) 
g :: s -> m (s, a) 

Tuttavia per ottenere s su f' è necessaria la Monade (qualsiasi cosa si farebbe con l'applicativo sarebbe ancora in forma di m s in modo da non essere in grado di applicare il valore a g).

È possibile giocare con le definizioni e utilizzare free monad ma per il collasso di stato è necessario join.

Answer 2

Sebbene, come indicato nella risposta precedente, questa istanza non può essere definito in generale, è opportuno notare che, quando f è Applicative e s è un Monoid, StateT s f è anche Applicative, dal momento che può essere considerata come una composizione di funtori applicative:

StateT s f = Reader s `Compose` f `Compose` Writer s 

Answer 3

Weaker variante di un trasformatore Applicative

Anche se non è possibile definire un trasformatore applicativo per StateT, E 'possibile definire una variante più debole che funzioni. Invece di avere s -> m (a, s), dove lo stato decide l'effetto successivo (quindi m deve essere una monade), possiamo usare m (s -> (a, s)), o equivalentemente m (State s a).

import Control.Applicative 
import Control.Monad 
import Control.Monad.State 
import Control.Monad.Trans 

newtype StateTA s m a = StateTA (m (State s a)) 

Questo è strettamente più debole di StateT.Ogni StateTA può essere trasformato StateT (ma non viceversa):

toStateTA :: Applicative m => StateTA s m a -> StateT s m a 
toStateTA (StateTA k) = StateT $ \s -> flip runState s <$> k 

Definizione Functor e Applicative è solo questione di operazioni di State sollevamento nella sottostante m:

instance (Functor m) => Functor (StateTA s m) where 
    fmap f (StateTA k) = StateTA $ liftM f <$> k 
instance (Applicative m) => Applicative (StateTA s m) where 
    pure = StateTA . pure . return 
    (StateTA f) <*> (StateTA k) = StateTA $ ap <$> f <*> k  

E possiamo definire una variante applicativa di lift:

lift :: (Applicative m) => m a -> StateTA s m a 
lift = StateTA . fmap return 

---

Aggiornamento: In realtà quanto sopra non è necessario, in quanto la composizione di due funtori applicativi è sempre un funtore applicativo (a differenza delle monadi). Il nostro StateTA è isomorfo a Compose m (State s), che è automaticamente Applicative:

instance (Applicative f, Applicative g) => Applicative (Compose f g) where 
    pure x = Compose (pure (pure x)) 
    Compose f <*> Compose x = Compose ((<*>) <$> f <*> x) 

Quindi potremmo scrivere semplicemente

{-# LANGUAGE GeneralizedNewtypeDeriving #-} 
import Control.Applicative 
import Control.Monad.State 
import Data.Functor.Compose 

newtype StateTA s m a = StateTA (Compose m (State s) a) 
    deriving (Functor, Applicative)