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).

Answer 3

I also had trouble with this one, and I found Ramon and Mikhail's answers informative -- thanks! I'm putting this in an answer rather than a comment because 500 chars is too short, and for code formatting.

I was having trouble understanding what was covariant about (a -> Int) and came up with this counterexample showing data K a = K (a -> Int) can be made an instance of Functor (disproving Ramon's proof)

data K a = K (a -> Int)
instance Functor K where
  fmap g (K f) = K (const 0)

If it compiles, it must be correct, right? ;-) I spent some time trying other permutations. Flopping the function around just made it easier:

-- "o" for "output"
-- The fmapped (1st) type is a function output so we're OK.
data K0 o = K0 (Int -> o)
instance Functor K0 where
  fmap :: (oa -> ob) -> (K0 oa) -> (K0 ob)
  fmap g (K0 f) = K0 (g . f)

Turning the Int into a type variable reduced it to Section 3.2 exercise 1 part 2:

-- The fmapped (2nd) type argument is an output
data K1 a b = K1 (a -> b)
instance Functor (K1 a) where
  fmap :: (b1 -> b2) -> K1 a b1 -> K1 a b2
  fmap g (K1 f) = K1 (g . f)

Forcing the fmapped type to be an argument of the function was the key... just like Mikhail's answer said, but now I understand it ;-)

-- The fmapped (2nd) type argument is an input
data K2 a b = K2 (b -> a) 
instance Functor (K2 o) where
  fmap :: (ia -> ib) -> (K2 o ia) -> (K2 o ib)
  -- Can't get our hands on a value of type o
  fmap g (K2 f) = K2 (const (undefined :: o))
  -- Nor one of type ia
  fmap g (K2 f) = K2 (const (f (undefined :: ia)))