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.