Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why is (a, a) not a functor? [duplicate]

Possible Duplicate:
Making (a, a) a Functor

I wrote the following implementation of quicksort:

import Data.List (partition)

quicksort [] = []

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

Then I wanted to abbreviate 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) is not a functor. Why is that? I tried to provide one:

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

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

Could anyone explain that error to me? I tried various "fixes", but none of them worked.

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

like image 718
fredoverflow Avatar asked Oct 06 '12 11:10

fredoverflow


1 Answers

It's important to realise that it's not (a,a) that would be the functor, in the same way that Maybe a and [a] aren't functors. Instead, the functors are Maybe and [].

A full explanation requires introducing the concept of kinds, which are like "types of types". Any concrete type has kind *. A type constructor like Maybe or [] takes a type and returns another type, so it has kind * -> *.

What's the kind of (,) (the constructor for pairs)? It needs two types, one for the first slot and one for the second slot, so it has kind * -> * -> *.

You can only make a functor out of things of kind * -> *, so the short answer to your question is no, you can't make (,) into a functor.

However, you can get around the limitation by wrapping the type. For example

newtype Pair a = P (a,a)

instance Functor Pair where
    fmap f (P (x,y)) = P (f x, f y)

The newtype wrapper will be optimized away by the compiler, so this isn't any more expensive than what you were trying to do originally - it's just a little more verbose.

like image 128
Chris Taylor Avatar answered Sep 27 '22 15:09

Chris Taylor