haskell - (Monad m, Monoid o) => m o? 的应用实例

Question

对不起这个可怕的标题。我正在尝试创建 Applicative 的实例对于 Monad包装类型为 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

这不起作用； 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)'

我意识到我上面写的可能没有意义。这是上下文:我正在尝试使用 compos论文中描述的抽象 A pattern for almost compositional functions .采用这棵树(使用 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

我将编写很多函数，它们会下降树并返回一个说错误列表或一组字符串，同时还需要它下降时的状态(例如绑定(bind)环境)，例如:

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结构体。所以要将它与 GADT Applicative 一起使用 compos 的版本见 the paper 第 575/576 页.我想我需要制作一个 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 ，其中更详细地讨论了这些模式。