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

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.