関連するタイプとコンテナの要素

Question

ハスケル・カフェでこれを尋ねたことがあるかもしれませんが、答えが見つかると駄目です...私はここにもう一度聞いています。 答えを見つけよう！

ハスケルはfantasticパラメトリック多形を扱っています。しかし問題は、すべてがパラメトリックではないということです。簡単な例として、データの最初の要素をコンテナからフェッチしたいとします。パラメトリックタイプの場合、それは簡単です：

 
class HasFirst c where 
    first :: c x -> Maybe x 

instance HasFirst [] where 
    first [] = Nothing 
    first (x:_) = Just x 

今すぐ試してみて、ByteStringのインスタンスを作成します。できません。その型は要素型について言及していない。また、Ord制約が必要なため、Setのインスタンスを記述することはできませんが、クラスの先頭には要素タイプが記述されていないため、制約できません。しかし、我々は今、新たな問題を抱えている

 
class HasFirst c where 
    type Element c :: * 
    first :: c -> Maybe (Element c) 

instance HasFirst [x] where 
    type Element [x] = x 
    first [] = Nothing 
    first (x:_) = Just x 

instance HasFirst ByteString where 
    type Element ByteString = Word8 
    first b = b ! 0 

instance Ord x => HasFirst (Set x) where 
    type Element (Set x) = x 
    first s = findMin s 

：

関連の種類は完全にこれらの問題を解決するためにきちんとした方法を提供します。それは、すべてのコンテナタイプのために働くようにFunctor「修正」しようとして考えてみましょう：

 
class Functor f where 
    type Element f :: * 
    fmap :: (Functor f2) => (Element f -> Element f2) -> f -> f2 

これがすべてでは動作しません。要素タイプがfから要素タイプがf2までの関数がある場合、fをf2に変換することができます。ここまでは順調ですね。しかし、明らかにはありませんfとf2はと同じ種類のコンテナです！既存のFunctor定義の下で

、我々は

 
fmap :: (x -> y) -> [x] -> [y] 
fmap :: (x -> y) -> Seq x -> Seq y 
fmap :: (x -> y) -> IO x -> IO y 

を持っている。しかし、我々ははないはfmap :: (x -> y) -> IO x -> [y]を持っています。それは全く不可能です。しかし、上記のクラス定義はそれを可能にします。

誰でも私が実際にを意味するタイプシステムに説明する方法を知っていますか？

編集

容器型から要素タイプを計算する方法を定義することによって、上記の作品。あなたはそれを逆にしようとするとどうなりますか？要素型からコンテナ型を計算する関数を定義しますか？それはどんなことでも楽になりますか？

Answer 1

問題は、修正されたFunctorが意味するものが明確ではないということです。たとえば、ByteStringと考えてください。 ByteStringは、Word8の各要素を同じタイプののに置き換えることによってのみマップすることができます。しかし、Functorはのパラメトリックのためのものです。実際にここにマッピングするという2つの相反する概念があります。

• リジッドマッピング
• パラメトリックマッピング（すなわち任意の型に構造体の各要素を変換）

だから）その型を変更することなく、構造体の各要素を変換する、この場合には、あなたはどのような種類のシステムに説明することはできませんあなたが意味するのは、あまり意味がないからです。ただし、

リジッドマッピングはタイプの家族と表現するのは簡単です:)あなたは何を意味するか変更することができます。

class RigidMap f where 
    type Element f :: * 
    rigidMap :: (Element f -> Element f) -> f -> f 

限りパラメトリックマッピングとして、それを行うには複数の方法があります。最も簡単な方法は、現在のFunctorをそのまま使用することです。一緒に、これらのクラスはByteString、[]、Seqのような構造をカバーします。ただし、値がOrdであるため、すべてがSetおよびMapになります。幸いなことに、GHC 7.4に来てconstraint kinds拡張子は私たちがこの問題を解決することができます：ここで

class RFunctor f where 
    type Element f a :: Constraint 
    type Element f a =() -- default empty constraint 
    fmap :: (Element f a, Element f b) => (a -> b) -> f a -> f b 

、我々はすべてのインスタンスが関連付けられている型クラス制約を持つべきであると言っています。たとえば、インスタンスがタイプに使用可能な場合にのみ、を構築できることを示すために、SetインスタンスにはElement Set a = Ord aが含まれます。 =>の左手に表示されるものはすべて許可されます。私たちは、彼らがいたとおりに、当社の以前のインスタンスを定義することができますが、我々はまた、SetとMapを行うことができます。

instance RFunctor Set where 
    type Element Set a = Ord a 
    fmap = Set.map 

instance RFunctor Map where 
    type Element Map a = Ord a 
    fmap = Map.map 

しかし、それは剛性のマッピングおよび制限付きパラメトリックマッピングするための2つの別々のインタフェースを使用するために持っているかなり迷惑なんです。実際、後者は前者の一般化ではないのですか？ OrdとByteStringのインスタンスのみを含むことができるSetの違いを考えてみましょう。Word8を含むことができます。確かにそれをもう一つの制約として表現できますか？

class Mappable f where 
    type Element f :: * 
    type Result f a r :: Constraint 
    map :: (Result f a r) => (Element f -> a) -> f -> r 

ここでの考え方：私たちは、同じトリック（すなわち全体の構造のためのインスタンスを与え、要素の型を公開するタイプのファミリを使用）HasFirstに行われ、新しい関連する制約の家族を紹介適用

Result f a rは値タイプ（たとえばOrd a）に必要な制約を表し、でもは必要なコンテナタイプを制約します。おそらく、それがaの同じ種類のコンテナのタイプを有することを保証するためである。例えば、Result [a] b rは、おそらくrが[b]であり、Result ByteString b rがbであり、Word8であり、rがByteStringであることを必要とすると考えられます。

タイプファミリーは、ここでは「タイプ」と表現する必要があるタイプを提供しています。 (a ~ b) => ...と言うと、aとbは同じタイプです。もちろん、制約ファミリ定義でこれを使用することもできます。だから、私たちは必要なものすべてを持っています。インスタンス：

instance Mappable [a] where 
    type Element [a] = a 
    type Result [a] b r = r ~ [b] 
    -- The type in this case works out as: 
    -- map :: (r ~ [b]) => (a -> b) -> [a] -> r 
    -- which simplifies to: 
    -- map :: (a -> b) -> [a] -> [b] 
    map = Prelude.map 

instance Mappable ByteString where 
    type Element ByteString = Word8 
    type Result ByteString a r = (a ~ Word8, r ~ ByteString) 
    -- The type is: 
    -- map :: (b ~ Word8, r ~ ByteString) => (Word8 -> b) -> ByteString -> r 
    -- which simplifies to: 
    -- map :: (Word8 -> Word8) -> ByteString -> ByteString 
    map = ByteString.map 

instance (Ord a) => Mappable (Set a) where 
    type Element (Set a) = a 
    type Result (Set a) b r = (Ord b, r ~ Set b) 
    -- The type is: 
    -- map :: (Ord a, Ord b, r ~ Set b) => (a -> b) -> Set a -> r 
    -- (note the (Ord a) constraint from the instance head) 
    -- which simplifies to: 
    -- map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b 
    map = Set.map 

パーフェクト！我々は、剛性、パラメトリック、またはパラメトリックだが制限された任意のタイプのコンテナのインスタンスを定義することができ、タイプは完全に機能する。

免責事項：私はまだGHC 7.4を試していないので、これが実際にコンパイルされているかどうかわかりませんが、基本的な考え方は健全だと思います。

Answer 2

希望するconstraint kinds、ghc 7.4で利用可能です。