Why is (a, a) not a functor?

Question

Possible duplicate:
Creating (a, a) Functor

I wrote the following quicksort implementation:

import Data.List (partition) quicksort [] = [] quicksort (x:xs) = let (smaller, notSmaller) = partition (< x) xs in quicksort smaller ++ x : quicksort notSmaller 

Then I would like to shorten the two recursive calls to quicksort by applying fmap to the list pair:

 quicksort (x:xs) = let (smaller, notSmaller) = fmap quicksort $ partition (< x) xs in smaller ++ x : notSmaller 

But, apparently, (a, a) not a functor. Why is this? I tried to provide one:

 instance Functor (a, a) where fmap f (x, y) = (fx, fy) 

But ghci did not like my attempt:

 Kind mis-match The first argument of `Functor' should have kind `* -> *', but `(a, a)' has kind `*' In the instance declaration for `Functor (a, a)' 

Can someone explain this error to me? I tried various “fixes”, but none of them worked.

Is it possible to make (a, a) instance of Functor ? Or is the type system not expressive enough?

Answer 1

It is important to understand that it is not (a,a) that would be a functor, in the same way that Maybe a and [a] are not functors. Instead, Maybe and [] functors.

A full explanation requires the introduction of the concept of species, which are similar to "type types". Any particular type has the form * . A type constructor of type Maybe or [] takes a type and returns another type, so it has the form * -> * .

What type (,) (constructor for pairs)? This requires two types: one for the first slot and the second for the second slot, so it has the form * -> * -> * .

You can only make a functor from things like * -> * , so the short answer to your question is no, you cannot do (,) in a functor.

However, you can get around the restriction by wrapping the type. for instance

 newtype Pair a = P (a,a) instance Functor Pair where fmap f (P (x,y)) = P (fx, fy) 

The newtype shell will be optimized by the compiler, so it will not be more expensive than what you tried to do initially - it is just a little more detailed.