I'd like to propose a more systematic approach to answering this question, and also to show examples that do not use any special tricks like the "bottom" values or infinite data types or anything like that.

## When do type constructors fail to have type class instances?

In general, there are two reasons why a type constructor could fail to have an instance of a certain type class:

- Cannot implement the type signatures of the required methods from the type class.
- Can implement the type signatures but cannot satisfy the required laws.

Examples of the first kind are easier than those of the second kind because for the first kind, we just need to check whether one can implement a function with a given type signature, while for the second kind, we are required to prove that no implementation could possibly satisfy the laws.

## Specific examples

This is a contrafunctor, not a functor, with respect to the type parameter `a`

, because `a`

in a contravariant position. It is impossible to implement a function with type signature `(a -> b) -> F z a -> F z b`

.

**A type constructor that is not a lawful functor** even though the type signature of `fmap`

can be implemented:

`data Q a = Q(a -> Int, a) fmap :: (a -> b) -> Q a -> Q b fmap f (Q(g, x)) = Q(\_ -> g x, f x) -- this fails the functor laws! `

The curious aspect of this example is that we *can* implement `fmap`

of the correct type even though `F`

cannot possibly be a functor because it uses `a`

in a contravariant position. So this implementation of `fmap`

shown above is misleading - even though it has the correct type signature (I believe this is the only possible implementation of that type signature), the functor laws are not satisfied. For example, `fmap id`

≠ `id`

, because `let (Q(f,_)) = fmap id (Q(read,"123")) in f "456"`

is `123`

, but `let (Q(f,_)) = id (Q(read,"123")) in f "456"`

is `456`

.

In fact, `F`

is only a profunctor, - it is neither a functor nor a contrafunctor.

**A lawful functor that is not applicative** because the type signature of `pure`

cannot be implemented: take the Writer monad `(a, w)`

and remove the constraint that `w`

should be a monoid. It is then impossible to construct a value of type `(a, w)`

out of `a`

.

**A functor that is not applicative** because the type signature of `<*>`

cannot be implemented: `data F a = Either (Int -> a) (String -> a)`

.

**A functor that is not lawful applicative** even though the type class methods can be implemented:

`data P a = P ((a -> Int) -> Maybe a) `

The type constructor `P`

is a functor because it uses `a`

only in covariant positions.

`instance Functor P where fmap :: (a -> b) -> P a -> P b fmap fab (P pa) = P (\q -> fmap fab $ pa (q . fab)) `

The only possible implementation of the type signature of `<*>`

is a function that always returns `Nothing`

:

` (<*>) :: P (a -> b) -> P a -> P b (P pfab) <*> (P pa) = \_ -> Nothing -- fails the laws! `

But this implementation does not satisfy the identity law for applicative functors.

**A functor that is **`Applicative`

but not a `Monad`

because the type signature of `bind`

cannot be implemented.

I do not know any such examples!

**A functor that is **`Applicative`

but not a `Monad`

because laws cannot be satisfied even though the type signature of `bind`

can be implemented.

This example has generated quite a bit of discussion, so it is safe to say that proving this example correct is not easy. But several people have verified this independently by different methods. See Is `data PoE a = Empty | Pair a a` a monad? for additional discussion.

` data B a = Maybe (a, a) deriving Functor instance Applicative B where pure x = Just (x, x) b1 <*> b2 = case (b1, b2) of (Just (x1, y1), Just (x2, y2)) -> Just((x1, x2), (y1, y2)) _ -> Nothing `

It is somewhat cumbersome to prove that there is no lawful `Monad`

instance. The reason for the non-monadic behavior is that there is no natural way of implementing `bind`

when a function `f :: a -> B b`

could return `Nothing`

or `Just`

for different values of `a`

.

It is perhaps clearer to consider `Maybe (a, a, a)`

, which is also not a monad, and to try implementing `join`

for that. One will find that there is no intuitively reasonable way of implementing `join`

.

` join :: Maybe (Maybe (a, a, a), Maybe (a, a, a), Maybe (a, a, a)) -> Maybe (a, a, a) join Nothing = Nothing join Just (Nothing, Just (x1,x2,x3), Just (y1,y2,y3)) = ??? join Just (Just (x1,x2,x3), Nothing, Just (y1,y2,y3)) = ??? -- etc. `

In the cases indicated by `???`

, it seems clear that we cannot produce `Just (z1, z2, z3)`

in any reasonable and symmetric manner out of six different values of type `a`

. We could certainly choose some arbitrary subset of these six values, -- for instance, always take the first nonempty `Maybe`

- but this would not satisfy the laws of the monad. Returning `Nothing`

will also not satisfy the laws.

**A tree-like data structure that is not a monad** even though it has associativity for `bind`

- but fails the identity laws.

The usual tree-like monad (or "a tree with functor-shaped branches") is defined as

` data Tr f a = Leaf a | Branch (f (Tr f a)) `

This is a free monad over the functor `f`

. The shape of the data is a tree where each branch point is a "functor-ful" of subtrees. The standard binary tree would be obtained with `type f a = (a, a)`

.

If we modify this data structure by making also the leaves in the shape of the functor `f`

, we obtain what I call a "semimonad" - it has `bind`

that satisfies the naturality and the associativity laws, but its `pure`

method fails one of the identity laws. "Semimonads are semigroups in the category of endofunctors, what's the problem?" This is the type class `Bind`

.

For simplicity, I define the `join`

method instead of `bind`

:

` data Trs f a = Leaf (f a) | Branch (f (Trs f a)) join :: Trs f (Trs f a) -> Trs f a join (Leaf ftrs) = Branch ftrs join (Branch ftrstrs) = Branch (fmap @f join ftrstrs) `

The branch grafting is standard, but the leaf grafting is non-standard and produces a `Branch`

. This is not a problem for the associativity law but breaks one of the identity laws.

## When do polynomial types have monad instances?

Neither of the functors `Maybe (a, a)`

and `Maybe (a, a, a)`

can be given a lawful `Monad`

instance, although they are obviously `Applicative`

.

These functors have no tricks - no `Void`

or `bottom`

anywhere, no tricky laziness/strictness, no infinite structures, and no type class constraints. The `Applicative`

instance is completely standard. The functions `return`

and `bind`

can be implemented for these functors but will not satisfy the laws of the monad. In other words, these functors are not monads because a specific structure is missing (but it is not easy to understand what exactly is missing). As an example, a small change in the functor can make it into a monad: `data Maybe a = Nothing | Just a`

is a monad. Another similar functor `data P12 a = Either a (a, a)`

is also a monad.

### Constructions for polynomial monads

In general, here are some constructions that produce lawful `Monad`

s out of polynomial types. In all these constructions, `M`

is a monad:

`type M a = Either c (w, a)`

where `w`

is any monoid `type M a = m (Either c (w, a))`

where `m`

is any monad and `w`

is any monoid `type M a = (m1 a, m2 a)`

where `m1`

and `m2`

are any monads `type M a = Either a (m a)`

where `m`

is any monad

The first construction is `WriterT w (Either c)`

, the second construction is `WriterT w (EitherT c m)`

. The third construction is a component-wise product of monads: `pure @M`

is defined as the component-wise product of `pure @m1`

and `pure @m2`

, and `join @M`

is defined by omitting cross-product data (e.g. `m1 (m1 a, m2 a)`

is mapped to `m1 (m1 a)`

by omitting the second part of the tuple):

` join :: (m1 (m1 a, m2 a), m2 (m1 a, m2 a)) -> (m1 a, m2 a) join (m1x, m2x) = (join @m1 (fmap fst m1x), join @m2 (fmap snd m2x)) `

The fourth construction is defined as

` data M m a = Either a (m a) instance Monad m => Monad M m where pure x = Left x join :: Either (M m a) (m (M m a)) -> M m a join (Left mma) = mma join (Right me) = Right $ join @m $ fmap @m squash me where squash :: M m a -> m a squash (Left x) = pure @m x squash (Right ma) = ma `

I have checked that all four constructions produce lawful monads.

I *conjecture* that there are no other constructions for polynomial monads. For example, the functor `Maybe (Either (a, a) (a, a, a, a))`

is not obtained through any of these constructions and so is not monadic. However, `Either (a, a) (a, a, a)`

is monadic because it is isomorphic to the product of three monads `a`

, `a`

, and `Maybe a`

. Also, `Either (a,a) (a,a,a,a)`

is monadic because it is isomorphic to the product of `a`

and `Either a (a, a, a)`

.

The four constructions shown above will allow us to obtain any sum of any number of products of any number of `a`

's, for example `Either (Either (a, a) (a, a, a, a)) (a, a, a, a, a))`

and so on. All such type constructors will have (at least one) `Monad`

instance.

It remains to be seen, of course, what use cases might exist for such monads. Another issue is that the `Monad`

instances derived via constructions 1-4 are in general not unique. For example, the type constructor `type F a = Either a (a, a)`

can be given a `Monad`

instance in two ways: by construction 4 using the monad `(a, a)`

, and by construction 3 using the type isomorphism `Either a (a, a) = (a, Maybe a)`

. Again, finding use cases for these implementations is not immediately obvious.

A question remains - given an arbitrary polynomial data type, how to recognize whether it has a `Monad`

instance. I do not know how to prove that there are no other constructions for polynomial monads. I don't think any theory exists so far to answer this question.