7

重複の可能性：
（a、a）をファンクターにする

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

import Data.List (partition)

quicksort [] = []

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

次に、リストペアにquicksort適用して、への2つの再帰呼び出しを省略したいと思いました。fmap

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

しかし、どうやら、(a, a)ファンクターではありません。何故ですか？私は1つを提供しようとしました：

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ですか？それとも、型システムは十分に表現力がありませんか？

4

1 に答える 1

14

(a,a)がファンクターでないのと同じように、Maybe aそれがファンクターではないことを理解することが重要[a]です。代わりに、関手はMaybeと[]です。

完全な説明には、「型の型」のような種類の概念を導入する必要があります。具体的な型には kind があり*ます。orのような型コンストラクタは、型を取り、別の型を返すため、 kind を持ちます。Maybe[]* -> *

(,)(ペアのコンストラクター)の種類は何ですか? 最初のスロット用と 2 番目のスロット用の 2 つの型が必要なので、 kind があり* -> * -> *ます。

種類のものからのみファンクターを作成できる* -> *ため、質問に対する短い答えはno(,)です。ファンクターにすることはできません。

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

newtype Pair a = P (a,a)

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

newtype ラッパーはコンパイラーによって最適化されて取り除かれます。そのため、これは最初にやろうとしていたことよりもコストがかかるわけではなく、少し冗長になります。

于 2012-10-06T11:53:07.460 に答える