haskell - ¿Es posible implementar `(Applicative m)=> Applicative(StateT sm)`?

monad-transformers state-monad

Question

Actualmente estoy trabajando en Data.Fresh y Control.Monad.Trans.Fresh , que resp. define una interfaz para generar nuevas variables y un transformador de mónada que implementa esta interfaz.

Inicialmente pensé que sería posible implementar la instancia de Applicative para mi FreshT vm con el único requisito de que exista Applicative m . Sin embargo, me quedé atascado y parecía que necesitaba requerir Monad m . Sin confiar en mi Haskell-fu, me volví hacia el paquete de transformadores y me sorprendió lo que encontré en Control.Monad.Trans.State.Lazy y .Strict :

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

Así que aquí está mi pregunta: ¿es posible crear una instancia con semántica equivalente con el siguiente encabezado de instancia?

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

Answer 1

Variante más débil de un transformador Applicative

Aunque no es posible definir un transformador aplicativo para StateT , es posible definir una variante más débil que funcione. En lugar de tener s -> m (a, s) , donde el estado decide el siguiente efecto (por lo tanto, m debe ser una mónada), podemos usar m (s -> (a, s)) , o equivalentemente m (State sa) .

import Control.Applicative
import Control.Monad
import Control.Monad.State
import Control.Monad.Trans
newtype StateTA s m a = StateTA (m (State s a))

Esto es estrictamente más débil que StateT . Cada StateTA se puede convertir en StateT (pero no al revés):

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

Definir el Functor y el Applicative es solo una cuestión de elevar las operaciones del State a la m subyacente:

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 

Y podemos definir una variante de lift aplicativa:

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

Actualización: en realidad, lo anterior no es necesario, ya que la composición de dos funtores aplicativos es siempre un funtor aplicativo (a diferencia de las mónadas). Nuestro StateTA es isomorfo para StateTA Compose m (State s) , que es automáticamente Applicative :

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

Por lo tanto podríamos escribir solo

{-# 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)

Answer 2

Aunque, como se señaló en la respuesta anterior, esta instancia no se puede definir en general, vale la pena señalar que, cuando f es Applicative StateT sf es un StateT sf , StateT sf también es Applicative , ya que puede considerarse como una composición de funtores aplicativos. :

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

Answer 3

Considera que tienes dos funciones:

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

Y desea crear una función h = StateT f <*> StateF g

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

De lo anterior tiene una s que puede pasar a f por lo que tiene:

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

Sin embargo, para obtener s fuera de f'' necesitas la mónada (lo que harías con el aplicativo todavía estaría en forma de ms por lo que no podrías aplicar el valor a g ).

Puedes jugar con las definiciones y usar la mónada gratuita, pero para el colapso del estado al que necesitas join .