Warum ist (a, a) kein Funktor?

Question

Mögliche Duplizieren:
Making (a, a) a Functor

Ich schrieb die folgende Implementierung von Quicksort:

import Data.List (partition) 

quicksort [] = [] 

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

Dann habe ich durch die Anwendung fmap, um die zwei rekursive Aufrufe zu quicksort abkürzen wollte das Listenpaar:

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

Aber anscheinend ist (a, a) kein Funktor. Warum das? Ich habe versucht, eine schaffen:

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

Aber GHCI nicht mein Versuch nicht mochte:

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

Könnte jemand diesen Fehler zu mir erklären? Ich habe verschiedene "Fixes" ausprobiert, aber keiner von ihnen hat funktioniert.

Ist es möglich, (a, a) eine Instanz von Functor zu machen? Oder ist das Typensystem nicht ausdrucksvoll genug?

Answer 1

Es ist wichtig zu erkennen, dass es nicht (a,a) ist, die der Funktor wäre, in der gleichen Weise, dass und [a] keine Funktoren sind. Stattdessen sind die Funktoren Maybe und [].

Eine vollständige Erklärung erfordert die Einführung des Konzepts von Arten, die wie "Arten von Typen" sind. Jede konkrete Art hat Art *. Ein Typ Konstruktor wie Maybe oder [] nimmt einen Typ und gibt einen anderen Typ zurück, so hat es Art * -> *.

Was ist die Art von (,) (der Konstruktor für Paare)? Es benötigt zwei Typen, einen für den ersten und einen für den zweiten Steckplatz, also hat er die Art * -> * -> *.

Sie können nur einen Funktor machen aus Dingen der Art * -> *, so die kurze Antwort auf Ihre Frage ist kein, Sie nicht (,) in eine Funktors machen kann.

Sie können die Einschränkung jedoch umgehen, indem Sie den Typ umbrechen. Zum Beispiel

newtype Pair a = P (a,a) 

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

Die newtype Wrapper wird vom Compiler optimiert entfernt werden, so ist dies nicht teurer als das, was Sie wollten ursprünglich tun - es ist nur ein wenig ausführlicher.