An example of a type with kind * -> * which cannot be an instance of Functor

Question

I'm very much a Haskell novice, so apologies if the answer is obvious, but I'm working through the Typeclassopedia in an effort to better understand categories. When doing the exercises for the section on Functors, I came across this problem:

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

My first thought was to define some kind of infinitely recursing definition of fmap, but wouldn't that essentially be the same as if undefined was used in the definition?

If someone could explain the answer it would be greatly appreciated.

Thanks!

Source of original exercise here, section 3: http://www.haskell.org/haskellwiki/Typeclassopedia#Introduction

Answer 1

A simple example is

data K a = K (a -> Int)

Here's what ghci tells us is we try to automatically derive a Functor instance for K:

Prelude> :set -XDeriveFunctor
Prelude> data K a = K (a -> Int)
Prelude> :k K
K :: * -> *
Prelude> data K a = K (a -> Int) deriving Functor

<interactive>:14:34:
    Can't make a derived instance of `Functor K':
      Constructor `K' must not use the type variable in a function argument
    In the data type declaration for `K'

The problem is that the standard Functor class actually represents covariant functors (fmap lifts its argument to f a -> f b), but there is no way you can compose a -> b and a -> Int to get a function of type b -> Int (see Ramon's answer). However, it's possible to define a type class for contravariant functors:

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

and make K an instance of it:

instance Contravariant K where
    contramap f (K g) = K (g . f)

For more on covariance/contravariance in Haskell, see here.

Edit: Here's also a nice comment on this topic from Chris Smith on Reddit.

Answer 2

To expand on my (short) comment and on Mikhail's answer:

Given (-> Int), you'd expect fmap to look as such:

(a -> Int) -> (a -> b) -> (b -> Int)

or:

(a -> Int) -> (a -> b) -> b -> Int

It is easy to prove that from the three arguments (a -> Int), (a -> b), b there is no possible way to reach Int (without undefined), thus from (a -> Int), (a -> b) there is no way to reach (b -> Int). Conclusion: no Functor instance exists for (-> Int).