Make Data Type of Kind * -> * That's Not a Functor

Question

Brent Yorgey's Typeclassopedia gives the following exercise:

Give an example of a type of kind * -> * which cannot be made an instance of Functor (without using undefined).

Please tell me what "cannot be made an instance of Functor" means.

Also, I'd appreciate an example, but perhaps as a spoiler so that you can, please, guide me to the answer.

Answer 1

Let's talk about variances.

Here's the basic notion. Consider the type A -> B. What I want you to imagine is that such a type is similar to "having a B" and also "owing an A". In fact, if you pay back your A you immediately receive your B. Functions are kind of like escrow in that way.

The notion of "having" and "owing" can extend to other types. For instance, the simplest container

newtype Box a = Box a

behaves like this: if you "have" a Box a then you also "have" an a. We consider types which have kind * -> * and "have" their argument to be (covariant) functors and we can instantiate them to Functor

instance Functor Box where fmap f (Box a) = Box (f a)

What happens if we consider the type of predicates over a type, like

newtype Pred a = Pred (a -> Bool)

in this case, if we "have" a Pred a, we actually "owe" an a. This arises from the a being on the left side of the (->) arrow. Where fmap of Functor is defined by passing the function into the container and applying it to all the places where we "have" our inner type, we can't do the same for Pred a since we don't "have" and as.

Instead, we'll do this

class Contravariant f where
  contramap :: (a -> b) -> (f b -> f a)

Now that contramap is like a "flipped" fmap? It will allow us to apply the function to the places where we "own" a b in Pred b in order to receive a Pred a. We might call contramap "barter" because it encodes the idea that if you know how to get bs from as then you can turn a debt of bs into a debt of as.

Let's see how it works

instance Contravariant Pred where
  contramap f (Pred p) = Pred (\a -> p (f a))

we just run our trade using f prior to passing it on into the predicate function. Wonderful!

So now we have covariant and contravariant types. Technically, these are known as covariant and contravariant "functors". I'll also state immediately that almost always a contravariant functor is not also covariant. This, thus, answers your question: there exist a bunch of contravariant functors which are not able to be instantiated to Functor. Pred is one of them.

There are tricky types which are both contravariant and covariant functors, though. In particular, the constant functors:

data Z a = Z -- phantom a!

instance Functor       Z where fmap      _ Z = Z
instance Contravariant Z where contramap _ Z = Z

In fact, you can essentially prove that anything which is both Contravariant and Functor has a phantom parameter.

isPhantom :: (Functor f, Contravariant f) => f a -> f b   -- coerce?!
isPhantom = contramap (const ()) . fmap (const ())        -- not really...

On the other hand, what happens with a type like

-- from Data.Monoid
newtype Endo a = Endo (a -> a)

In Endo a we both owe and receive an a. Does that mean we're debt free? Well, no, it just means that Endo wants to be both covariant and contravariant and does not have a phantom parameter. The result: Endo is invariant and can instantiate neither Functor nor Contravariant.

Answer 2

A type t of kind * -> * can be made an instance of Functor if and only if it is possible to implement a law-abiding instance of the Functor class for it. So that means you have to implement the Functor class, and your fmap has to obey the Functor laws:

fmap id x == x
fmap f (fmap g x) == fmap (f . g) x

So basically, to solve this, you have to name some type of your choice and prove that there's no lawful implementation of fmap for it.

Let's start with a non-example, to set the tone. (->) :: * -> * -> * is the function type constructor, as seen in function types like String -> Int :: *. In Haskell, you can partially apply type constructors, so you can have types like (->) r :: * -> *. This type is a Functor:

instance Functor ((->) r) where
    fmap f g = f . g

Intuitively, the Functor instance here allows you to apply f :: a -> b to the return value of a function g :: r -> a "before" (so to speak) you apply g to some x :: r. So for example, if this is the function that returns the length of its argument:

length :: [a] -> Int

...then this is the function that returns twice the length of its argument:

twiceTheLength :: [a] -> Int
twiceTheLength = fmap (*2) length

Useful fact: the Reader monad is just a newtype for (->):

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

instance Functor (Reader r) where
    fmap f (Reader g) = Reader (f . g)

instance Applicative (Reader r) where
    pure a = Reader (const a)
    Reader f <*> Reader a = Reader $ \r -> f r (a r)

instance Monad (Reader r) where
    return = pure
    Reader f >>= g = Reader $ \r -> runReader g (f r) r

Now that we have that non-example out of the way, here's a type that can't be made into a Functor:

type Redaer a r = Redaer { runRedaer :: r -> a } 

-- Not gonna work!
instance Functor (Redaer a) where
    fmap f (Redaer g) = ...

Yep, all I did is spell the name backwards, and more importantly, flip the order of the type parameters. I'll let you try and figure out why this type can't be made an instance of Functor.