haskell - 为什么 (a, a) 不是函子？

Question

可能的重复：
使 (a, a) 成为函子

我编写了以下快速排序的实现：

import Data.List (partition)

quicksort [] = []

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

然后我想quicksort通过应用于fmap列表对来缩写两个递归调用：

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 不喜欢我的尝试：

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

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.