왜 (a, a)가 펑터가 아닌가?

Question

가능한 중복은 :에 fmap을 적용하여

import Data.List (partition) quicksort [] = [] quicksort (x:xs) = let (smaller, notSmaller) = partition (< x) xs in quicksort smaller ++ x : quicksort notSmaller 

가 그럼 난 quicksort에 두 개의 재귀 호출을 생략하고 싶었 :
Making (a, a) a Functor

나는 퀵 다음과 같은 구현을 썼다 목록 쌍 :

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

Maybe a 및 [a]은 펑터가 아닌 것과 같은 방식으로 펑터가 될 (a,a)이 아니라는 것을 알아야합니다. 대신, 펑터는 Maybe 및 []입니다.

종류의 개념을 완전히 설명하려면 "유형 유형"과 유사해야합니다. 콘크리트 유형은 *입니다. Maybe 또는 [] 같은 타입 생성자는 형식을 취하고 다른 형식을 반환하는, 그래서 종류 * -> *있다.

(,)의 종류 (쌍의 생성자)는 무엇입니까? 이 두 종류의 첫 번째 슬롯에 대해 하나의 상기 제 2 슬롯에 대해 하나를 필요로하므로 종류 * -> * -> *있다. 귀하의 질문에 짧은 대답이 더그래서

당신은 당신이 펑터에 (,)을 할 수 없습니다, 종류 * -> *의 일에서 펑터를 만들 수 있습니다.

그러나 유형을 포장하여 제한을 해결 얻을 수 있습니다. 예를

newtype Pair a = P (a,a) 

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

에 대한 newtype은 랩퍼는 컴파일러에 의해 멀리 최적화 될 것이다, 그래서 이것은 원래 일을하려고 한 것보다 더 비용이 - 그냥 좀 더 자세한입니다.