Istanza applicativa per (Monad m, Monoid o) => m o?

Question

Ci scusiamo per il terribile titolo. Sto cercando di creare un'istanza di Applicative per un Monad che avvolge un tipo che è un Monoid.

instance (Monad m, Monoid o) => Applicative (m o) where 
    pure x = return mempty 
    xm <*> ym = do 
     x <- xm 
     y <- ym 
     return $ x `mappend` y 

Questo non funziona; GCHi si lamenta con:

Mi rendo conto che ciò che ho scritto sopra potrebbe non avere senso. Ecco il contesto: sto cercando di utilizzare l'astrazione compos come descritto nel documento A pattern for almost compositional functions. Prendendo questo albero (utilizzando la versione GADT di compos; Ho semplificato un sacco):

data Tree :: * -> * where 
    Var :: String -> Expr 
    Abs :: [String] -> Expr -> Expr 
    App :: Expr -> [Expr] -> Expr 

class Compos t where 
    compos :: Applicative f => (forall a. t a -> f (t a)) -> t c -> f (t c) 

instance Compos Tree where 
    compos f t = 
     case t of 
      Abs ps e -> pure Abs <*> pure ps <*> f e 
      App e es -> pure App <*> f e <*> traverse f es 
      _ -> pure t 

ho intenzione di scrivere un sacco di funzioni che scendono l'albero e restituire un elenco di errori o dire una insieme di stringhe mentre anche richiedendo stato come va giù (come l'ambiente di legame), come:

composFoldM :: (Compos t, Monad m, Monoid o) => (forall a. t a -> m o) -> t c -> m o 
composFoldM f = ??? 

checkNames :: (Tree a) -> State (Set Name) [Error] 
checkNames e = 
    case e of 
     Var n -> do 
      env <- get 
      -- check that n is in the current environment 
      return $ if Set.member n env then [] else [NameError n] 
     Abs ps e' -> do 
      env <- get 
      -- add the abstractions to the current environment 
      put $ insertManySet ps env 
      checkNames e' 
     _ -> composFoldM checkNames e 

data Error = NameError Name 
insertManySet xs s = Set.union s (Set.fromList xs) 

credo questi dovrebbero poter essere estratta via facendo composFoldM uso compos per la struttura (Monad m, Monoid o) => m o. Quindi, per utilizzarlo con la versione GADT Applicative di compos trovata a pagina 575/576 di the paper. Penso di aver bisogno di creare un'istanza Applicative di questa struttura. Come lo farei? O sto scendendo completamente dalla strada sbagliata?

Answer 1

Si desidera l'applicativo Constant da Data.Functor.Constant nel pacchetto transformers, che è possibile trovare here.

Questa Applicative ha il seguente esempio:

instance (Monoid a) => Applicative (Constant a) where 
    pure _ = Constant mempty 
    Constant x <*> Constant y = Constant (x `mappend` y) 

È quindi possibile comporre Constant con qualsiasi altro applicativo utilizzando Compose da Data.Functor.Compose (anche nel pacchetto transformers), che potete trovare here.

Compose ha questa Applicative esempio:

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

È quindi possibile Compose tua Constant applicativa con qualsiasi altro Applicative (come State) per mantenere sia uno stato e un running Monoid riscontro.

Più in generale, si consiglia di leggere il documento The Essence of the Iterator Pattern, che illustra questi modelli in modo più dettagliato.