为什么（a，a）不是算子？ [重复]

Question

可能重复： Making (a, a) a Functor

我编写了以下quicksort实现：

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

重要的是要意识到(a,a)不是functor，就像Maybe a和[a]不是仿函数一样。相反，算子是Maybe和[]。

完整的解释需要引入种类的概念，就像“类型的类型”。任何具体类型都有类型*。像Maybe或[]这样的类型构造函数接受一个类型并返回另一个类型，因此它具有类型* -> *。

什么是(,)（成对的构造函数）？它需要两种类型，一种用于第一个插槽，另一种用于第二个插槽，因此它具有良好的* -> * -> *。

你只能用善良的* -> *制作一个仿函数，所以对你的问题的简短答案是否定的，你不能把(,)变成一个仿函数。

但是，您可以通过包装类型来绕过限制。例如

newtype Pair a = P (a,a)

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

newtype包装器将被编译器优化掉，所以这并不比你原本想做的更贵 - 它只是更冗长一点。