（a、a）はなぜファンクタではないのですか？

Question

可能性の重複：
Making (a, a) a Functor

私はクイックソートの次の実装を書いた：

import Data.List (partition) 

quicksort [] = [] 

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

その後、私はfmapにを適用することにより、quicksortには、2つの再帰呼び出しを省略したいですリストのペア：

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

明らかに、(a, a)はファンクタではありません。何故ですか？

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

しかし、GHCiのは、私の試みを好きではなかった：私は1つを提供しようとした

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

誰も私にそのエラーを説明してもらえますか？私は様々な "修正"を試みましたが、それらのどれも働いていませんでした。

(a, a)をFunctorのインスタンスにすることはできますか？あるいは、表現力が十分でないタイプのシステムですか？

Answer 1

Maybe aと[a]がファンクタでないのと同じ方法で、ファンクタになるのは(a,a)ではないことに気づくことが重要です。代わりに、ファンクタはMaybeと[]です。

種類の概念を完全に説明するには、「種類の種類」のようなものが必要です。具体的なタイプはいずれも*です。 型コンストラクタのようにMaybeまたは[]は型を取り、別の型を返します。したがって、型は* -> *です。

(,)（ペアのコンストラクタ）の種類は何ですか？最初のスロットと2番目のスロットの2種類が必要です。種類は* -> * -> *です。あなたの質問への短い答えはノーあるので

あなただけがファンクタに(,)を作ることができない、種類* -> *のもののうち、ファンクタを作ることができます。

ただし、タイプをラップすることで制限を回避できます。例

newtype Pair a = P (a,a) 

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

についてのnewtypeラッパーは、コンパイラによって離れて最適化されますので、これは、最初にやろうとしていたものよりも、それ以上に高価ではありません - それはほんの少しより冗長です。