¿Por qué (a, a) no es un funtor?

Question

Duplicar posible:
Making (a, a) a Functor

me escribió la siguiente implementación de la clasificación rápida:

import Data.List (partition) 

quicksort [] = [] 

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

luego quería para abreviar las dos llamadas recursivas a quicksort aplicando fmap a el par de lista:

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

Pero aparentemente, (a, a) no es un funtor. ¿Porqué es eso? He intentado proporcionar una:

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

Pero ghci no me gustaba mi intento:

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

Podría alguien explicar que el error a mí? Intenté varias "correcciones", pero ninguna de ellas funcionó.

¿Es posible hacer (a, a) una instancia de Functor? ¿O el sistema de tipo no es lo suficientemente expresivo?

Answer 1

Es importante darse cuenta de que no es (a,a) que sería el funtor, de la misma manera que Maybe a y [a] no son funtores. En cambio, los funtores son Maybe y [].

Una explicación completa requiere la introducción del concepto de tipos, que son como "tipos de tipos". Cualquier tipo concreto tiene el tipo *. Un tipo constructor como Maybe o [] toma un tipo y devuelve otro tipo, por lo que tiene tipo * -> *.

¿Cuál es el tipo de (,) (el constructor de pares)? Necesita dos tipos, uno para la primera ranura y otro para la segunda ranura, por lo que tiene el tipo * -> * -> *.

Sólo se puede hacer un funtor de cosas del tipo * -> *, por lo que la respuesta corta a tu pregunta es sin, no se puede hacer (,) en un funtor.

Sin embargo, puede sortear la limitación al ajustar el tipo. Por ejemplo

newtype Pair a = P (a,a) 

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

La envoltura newtype será optimizado de distancia por el compilador, así que esto no es más caro que lo que estaba tratando de hacer un principio - es sólo un poco más detallado.