適用實例

Question

對不起，可怕的標題。我正在嘗試爲Monad包裝一個類型爲Monoid的Applicative實例。

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

這是行不通的; GCHi抱怨：

Kind mis-match 
The first argument of `Applicative' should have kind `* -> *', 
but `m o' has kind `*' 
In the instance declaration for `Applicative (m o)' 

我意識到我上面寫的東西可能沒有任何意義。以下是上下文：我試圖使用A pattern for almost compositional functions紙中所述的compos抽象。以這棵樹（使用compos的GADT版本;我已經簡化了很多）：

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 

我會寫很多，其下降的樹的功能和返回錯誤說或列表串，同時也需要國家，因爲它出現故障（如綁定環境），如集：

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) 

我想這些應該都能夠通過使composFoldM使用compos爲(Monad m, Monoid o) => m o結構中抽象出來。因此，請使用the paper的第575/576頁上的compos的GADT Applicative版本。我想我需要製作一個Applicative這個結構的實例。我將如何做到這一點？或者我完全走錯了路？

Answer 1

您希望Constant適用於Data.Functor.Constant的transformers包，其中您可以找到here。

這Applicative有以下實例：

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

然後，您可以編寫Constant使用Compose從Data.Functor.Compose（也在transformers包）任何其他應用性，你可以找到here。

Compose有這個Applicative實例：

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

然後，您可以Compose您Constant應用性與任何其他Applicative（如State），以保持雙方的一些狀態和運行Monoid相符。

更一般地，您應該閱讀紙張The Essence of the Iterator Pattern，其中更詳細地討論了這些模式。