haskell - ¿Son los transformadores aplicativos realmente superfluos?

stream typeclass

Question

Se habla mucho de que Applicative no necesita su propia clase de transformador, como esta:

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

¡Pero puedo definir transformadores aplicativos que no parecen ser composiciones de aplicativos! Por ejemplo, corrientes de efectos secundarios :

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

La elevación solo realiza el efecto secundario en cada paso:

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

Y si f es un aplicativo, entonces MStream f también:

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

Sé que para cualquier propósito práctico, f debería ser una mónada:

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

Pero si bien hay una instancia de MStream m para MStream m , es ineficiente. (¿O incluso incorrecto?) ¡La instancia del Applicative es realmente útil!

Ahora note que las corrientes habituales surgen como casos especiales para el functor de identidad:

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

Pero la composición de Stream f no es MStream f ! Por el contrario, Compose Stream fa es isomorfo de Stream (fa) .

Me gustaría saber si MStream es una composición de dos aplicativos.

Editar:

Me gustaría ofrecer un punto de vista teórico de la categoría. Un transformador es un endofunctor t "agradable" en la categoría C de los funtores aplicativos (es decir, los funtores monoidales laxos con fuerza), junto con una transformación natural liftA de la identidad en C a t . La pregunta más general es ahora qué transformadores útiles existen que no tienen la forma "componer con g " (donde g es un aplicativo). Mi reclamo es que MStream es uno de ellos.

Answer 1

Gran pregunta Creo que hay dos partes diferentes de esta pregunta:

1. Componer los aplicativos o mónadas existentes en otros más complejos.
2. Construyendo todos los aplicativos / mónadas de un conjunto de inicio dado.

Anuncio 1: los transformadores de mónada son esenciales para combinar mónadas. Las mónadas no componen directamente . Parece que debe haber un poco de información adicional proporcionada por los transformadores de mónada que indica cómo se puede componer cada mónada con otras mónadas (pero podría ser que esta información ya esté presente de alguna manera, ver ¿Existe una mónada que no tenga una ¿Transformador de mónada correspondiente? ).

Por otro lado, los aplicativos se componen directamente , vea Data.Functor.Compose . Es por esto que no se necesitan transformadores aplicativos para la composición. También están cerrados bajo el product (pero no coproduct ).

Por ejemplo, tener data Stream a = Cons a (Stream a) flujos infinitos data Stream a = Cons a (Stream a) y otro aplicativo g , tanto Stream (ga) como g (Stream a) son aplicativos.

Pero a pesar de que Stream también es una mónada (la join toma la diagonal de un flujo bidimensional), su composición con otra mónada m no será, ni Stream (ma) ni m (Stream a) siempre serán una mónada.

Además, como podemos ver, ambos son diferentes de su MStream g (que está muy cerca de ListT hecho correctamente ), por lo tanto:

Anuncio 2: ¿Se pueden construir todos los aplicativos a partir de un conjunto dado de primitivas? Aparentemente no. Un problema es la construcción de tipos de datos de suma: si f y g son aplicativos, Either (fa) (ga) no lo será, ya que no sabemos cómo componer Right h <*> Left x .

Otra primitiva construcción está tomando un punto fijo, como en tu ejemplo de MStream . Aquí podríamos intentar generalizar la construcción definiendo algo como

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)

(lo que requiere No-tan-agradable UndecidableInstances ) y luego

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

type MStream f = Fix1 (MStream'' f)