When a generic type would not be a monad?

Question

Haskell allows to define a new type around another one, thus creating a "type with context". Hence, one may differentiate (Int, Int) in cases such as data Time = Time (Int, Int) --(h:m) and data Coord = Coord (Int, Int) --(x,y). These new types will have related functions knowing that the wrapped "base" type is effectively an Int.

One step further, is to create "generic" types, by using "type parameters" in the data clause, as in the famous monad: data Maybe t = Nothing | Just t. These kind of generic types are going to be used by wide range of functions, and for addressing many different needs, namely: exception: Maybe, global state: State, input/output: IO, nondeterminism: [], environment: Reader, logger: Writer. Here arises the convenience of having two functions: return :: a -> m a for building a context around type a, and (>>=) :: m a -> (a -> m b) -> m b for automatically having a function m a -> m b based on an previous a -> m b. This is summarized by the monad class:

class Monad m where
        return :: a -> m a
        (>>=)  :: m a -> (a -> m b) -> m b

so that new generic types have to define what means return and >>= for them to be an instance of Monad.

It seems to me that this is going to happen for every generic type, so the concrete questions are:

1. Every generic type data MyThing t = ... must be and instance of Monad?
2. At least in general, is it convenient that Every generic type data MyThing t = ... is an instance of Monad?
3. Is any case where a generic type data MyThing t = ... must not be an instance of Monad? (apart from trivial cases). Why?
4. Is it interesting that even a concrete context type, data Time = Time (Int, Int), is a Monad?

Examples, corrections and edits of the above explanation are welcome and desired.

Thanks.

Answer 1

To give an example that's totally not a monad, consider

data Shower a = Shower (a -> String)

What this is is a bit of the opposite (actually, the dual) of a functor: a contravariant functor.

contramap :: Contravariant f => (a -> b) -> f b -> f a

contramap f (Shower q) = Shower (q . f)

Compare this to

fmap f (Identity x)  = Identity (f $ x)

A contravariant functor can not be a (nontrivial) monad, nor something analogue. To see why, you need to consider what a monad is, actually (i.e. in category theory): it's a kind of monoid of endofunctors. It has to be endo, because the crucial operation join :: m (m a) -> m a means applying the m twice leaves you in the same category. For, if you were to fmap a function A -> B over either of the sides, you would go in the same direction:

fmap f        :: m A     -> m B
fmap (fmap f) :: m (m A) -> m (m B)

(The same goes for comonads, which are also (covariant, not contravariant) functors. Here, the operation is duplicate :: w a -> w (w a), which goes the other way around but still has to stay in the same category.)

For contravariant functors, this does not work! The reason being,

contramap f             :: q B     -> q A
contramap (contramap f) :: q (q A) -> q (q B)

i.e. if you iterate the functor it keeps flipping between contravariant and covariant. It can thus not form any such thing as a monoid structure.

Answer 2

Here's something that's not a Monad---it's not even a Functor.

-- from Data.Monoid
newtype Endo a = Endo { appEndo :: a -> a }

In particular, Endo's type parameter a shows up in both contravariant and covariant positions---this type cannot be a Functor or Contravariant functor---it would need to be both.

Of course, if you just generalize it slightly you get the Reader monad

newtype Reader r a = Reader { runReader :: r -> a }

since we've now separated out the uses of the type parameter such that one is covariant and one is contravariant.

---

Having shown that Endo can't be a Functor or Contravariant because it would have to be both, are there any data types which are both? There's an easy trick argument that shows that (1) there are and (2) they're always using phantom parameters.

We'll use a nullary data type (the void package provides one, but it's easy to re-implement). The interesting thing about nullary data types is that you can use one to produce absurd, the function that takes an impossible argument and returns whatever.

data Void = Void Void     -- there are no values of Void 
                          -- ... unless there are values of Void

absurd :: Void -> a
absurd (Void v) = absurd v

Which then, combined with Functor and Contravariant gives us a very interesting function

contramap absurd :: Contravariant f => f a    -> f Void
fmap      absurd :: Functor       f => f Void -> f a

fmap absurd . contramap absurd 
  :: (Contravariant f, Functor f) => f a -> f b

In other words, it lets us write a kind of functor-based coerce, which is impossible if f actually contained any values of type a, thus we know that such an f must use a as a phantom parameter.

data Constant b a = Constant { runConstant :: b }

coerceConstant :: Constant a -> Constant b
coerceConstant = Constant . runConstant

instance Functor (Constant b) where
  fmap _ = coerceConstant

instance Contravariant (Constant b) where
  contramap _ = coerceConstant

which even gives us a way to implement a very boring Monad

instance Monoid b => Monad (Constant b) where
  return _ = Constant mempty
  c >>= _ = coerceConstant c

Answer 3

The concept of parameterized types is simply more general than the special case of types with just one paramter that happen to behave like monads.

So, no, not every type with kind (*->*) must be a monad and it is also not convenient.

An example:

data HomogenousTriple a = T a a a

Why and how should this be a Monad?