Sind Applikationstransformatoren wirklich überflüssig?

Question

Es gibt über Applicativenicht einen eigenen Transformator Klasse benötigen, wie dies eine Menge Diskussion:

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

Aber ich kann applicative Transformatoren definieren, die Zusammensetzungen von applicatives zu sein scheinen nicht! Zum Beispiel sideeffectful Ströme:

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

Lifting führt nur die Nebenwirkung bei jedem Schritt:

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

Und wenn f ein applicative ist, dann MStream f ist auch:

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 

Ich weiß, dass für alle praktischen Zwecke f sollte eine Monade sein:

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

Aber während es eine Monad Instanz für MStream m ist, es ist ineffizient. (Oder sogar falsch?) Die Applicative Instanz ist tatsächlich nützlich!

Nun beachten Sie, dass übliche Ströme als Sonderfälle für die Identität Funktors entstehen:

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

Aber die Zusammensetzung von Stream und f nicht MStream f ist! Eher ist Compose Stream f a isomorph zu Stream (f a).

Ich würde gerne wissen, ob MStream eine Zusammensetzung von zwei Anwendungen ist.

Edit:

Ich möchte eine Kategorie theoretische Sicht bieten. Ein Transformator ist ein "netter" Endofaktor t in der Kategorie C von anwendungsbezogenen Funktoren (d. H. Laxe monoidale Funktoren mit Festigkeit) zusammen mit einer natürlichen Transformation liftA von der Identität auf bis t. Die allgemeinere Frage ist nun, welche nützlichen Transformatoren existieren, die nicht die Form "compose with g" haben (wobei g ein Anwendungsfall ist). Meine Behauptung ist, dass MStream einer von ihnen ist.

Answer 1

Große Frage! Ich glaube, es gibt zwei verschiedene Teile dieser Frage:

1. Composing bestehende applicatives oder Monaden zu komplexeren.
2. Konstruieren aller Applikative/Monaden aus einer gegebenen Startmenge.

Anzeige 1 .: Für die Kombination von Monaden sind Monad-Transformatoren unerlässlich. Monaden don't compose directly.Es scheint, dass es ein zusätzliches bisschen Information geben muss, die von Monaden-Transformatoren bereitgestellt wird, die erzählen, wie jede Monade mit anderen Monaden zusammengesetzt werden kann (aber es könnte sein, dass diese Information bereits irgendwie vorhanden ist, siehe Is there a monad that doesn't have a corresponding monad transformer?).

Auf der anderen Seite, Applicates komponieren direkt, siehe Data.Functor.Compose. Aus diesem Grund brauchen Sie keine anwendbaren Transformatoren für die Zusammensetzung. Sie sind auch geschlossen unter product (aber nicht coproduct).

beispielsweise mit infinite streamsdata Stream a = Cons a (Stream a) und einem anderen applicative g, sowohl Stream (g a) und g (Stream a) applicatives sind.

Aber obwohl Stream ist auch eine Monade (join nimmt die Diagonale eines 2-dimensionalen Strom), seine Zusammensetzung mit einem anderen Monade m werden nicht, weder Stream (m a) noch m (Stream a) wird immer eine Monade sein.

Außerdem, wie wir sehen können, sind sie verschieden sowohl von Ihrem MStream g (die ListT done right ganz in der Nähe ist), deshalb:

Ad 2 .: Können alle applicatives aus einem gegebenen Satz von Grundelementen aufgebaut sein? Offensichtlich nicht. Ein Problem besteht darin, Summen-Datentypen zu konstruieren: Wenn f und g Anwendungen sind, wird Either (f a) (g a) nicht sein, da wir nicht wissen, wie man Right h <*> Left x verfasst.

Ein anderes Konstruktionselement nimmt einen festen Punkt, wie in Ihrem MStream Beispiel. Hier könnten wir versuchen, den Bau zu verallgemeinern, indem man so etwas wie

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) 

definieren (das erfordert nicht so schöne UndecidableInstances) und dann

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

type MStream f = Fix1 (MStream' f)