为什么(a,a)不是算子？

Question

可能重复:
制作(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),这将是该函子,以同样的方式,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包装器将被编译器优化掉,所以这并不比你原本想做的更昂贵 - 它只是更冗长一点.