Defining a monad in Haskell

I am currently reading Kan Extensions for Program Optimisation and in the first page of the paper the author defines given M a monad the following monad

type C a = ∀z . (a → M z ) → M z
instance Monad C where
  return a = λc → c a
  m >>= k = λc → m (λa → k a c)

So I've tried to play a bit with it using M=Maybe hence writing the following code

type C a = forall z . (a -> Maybe z) -> Maybe z

instance Monad C where
  return a = \c -> c a
  m >>= k = \c -> m $ \a -> k a c

But it doesn't compile and outputs

Main.hs:22:10: error: • The type synonym ‘C’ should have 1 argument, but has been given none

Which I am unable to interpret. What is wrong here ? (I've done some category theory but I've just started learning Haskell).


  • As noted in the comments, you need a newtype. type aliases are just programmer conveniences and aren't distinct entities, and you want to implement a typeclass, so you need a distinct entity. You can write the newtype like so.

    newtype C a = C (forall z . (a -> Maybe z) -> Maybe z)

    Though I would recommend including an accessor, because we'll need it for marshaling in a moment.

    newtype C a = C { unC :: forall z . (a -> Maybe z) -> Maybe z }

    (If you're following along at home, you need {-# LANGUAGE RankNTypes #-} to be able to do this forall syntax. It's a compiler extension that enables that particular fancier type)

    To be clear, we're not going to write a Monad instance for forall z. (a -> Maybe z) -> Maybe z. That type doesn't belong to us. We're going to write a Monad instance for C a, a new type we just made up which happens to be isomorphic to forall z. (a -> Maybe z) -> Maybe z in a nice way.

    Now Monad depends on Functor and Applicative, so we'll start there.

    Functor is derive-able, so we could just write deriving (Functor), but it's also good practice to know how to write these out.

    instance Functor C where
        fmap f (C a) = C $ \k -> a (k . f)

    Now Applicative. It's very common to implement Applicative in terms of a corresponding Monad instance, so we'll do just that here.

    instance Applicative C where
        pure = return
        (<*>) = ap

    (Note: ap comes from the Control.Monad module, so you'll want to import that as well)

    This always works, provided you write the Monad instance so as not to call pure or <*>.

    Now the Monad. It's pretty much exactly what you wrote, except with some C and unC marshaling to make the type checker happy.

    instance Monad C where
        return a = C (\c -> c a)
        m >>= k = C (\c -> unC m $ \a -> unC (k a) c)

    Finally, note that we never actually used Maybe or any of its properties here. Not only do we not care what that M is, we don't even need it to be a Functor. So we can parameterize by that as well.

    {-# LANGUAGE RankNTypes #-}
    import Control.Monad
    newtype C m a = C { unC :: forall z . (a -> m z) -> m z }
    instance Functor (C m) where
        fmap f (C a) = C $ \k -> a (k . f)
    instance Applicative (C m) where
        pure = return
        (<*>) = ap
    instance Monad (C m) where
        return a = C (\c -> c a)
        m >>= k = C (\c -> unC m $ \a -> unC (k a) c)

    Now C Maybe is identical to the C type you were just working with, but we can put anything of kind * -> * in place of the m. Anything, not just Functors. Go wild.