Haskell Language
ファンクタ

前書き

備考

fmap id == id

fmap (f . g) = (fmap f) . (fmap g)

Functorの共通インスタンス

多分

Maybe存在しない値を含むFunctorがあります。

instance Functor Maybe where
    fmap f Nothing = Nothing
    fmap f (Just x) = Just (f x)

MaybeさんのインスタンスFunctorに包まれた値に関数を適用するJust 。計算が以前に失敗した場合（ Maybe値がNothingなので）、関数を適用する値はないので、 fmapはノーオペレーションです。

> fmap (+ 3) (Just 3)
Just 6
> fmap length (Just "mousetrap")
Just 9
> fmap sqrt Nothing
Nothing

このインスタンスのファンクタの法則を、等式推論を使って調べることができます。アイデンティティ法の場合、

fmap id Nothing
Nothing  -- definition of fmap
id Nothing  -- definition of id

fmap id (Just x)
Just (id x)  -- definition of fmap
Just x  -- definition of id
id (Just x)  -- definition of id

組成法については、

(fmap f . fmap g) Nothing
fmap f (fmap g Nothing)  -- definition of (.)
fmap f Nothing  -- definition of fmap
Nothing  -- definition of fmap
fmap (f . g) Nothing  -- because Nothing = fmap f Nothing, for all f

(fmap f . fmap g) (Just x)
fmap f (fmap g (Just x))  -- definition of (.)
fmap f (Just (g x))  -- definition of fmap
Just (f (g x))  -- definition of fmap
Just ((f . g) x)  -- definition of (.)
fmap (f . g) (Just x)  -- definition of fmap

リスト

リストインスタンスFunctor代わりに、リスト内のすべての値に関数を適用します。

instance Functor [] where
    fmap f [] = []
    fmap f (x:xs) = f x : fmap f xs

代わりに、リスト内包として書くこともできます： fmap f xs = [fx | x <- xs] 。

この例は、 fmap generalisesがmapことを示していmap 。 fmapは任意のFunctor mapで動作するのに対して、 mapはリストに対してのみ動作します。

アイデンティティ法は誘導によって保持されることが示されている：

-- base case
fmap id []
[]  -- definition of fmap
id []  -- definition of id

-- inductive step
fmap id (x:xs)
id x : fmap id xs  -- definition of fmap
x : fmap id xs  -- definition of id
x : id xs  -- by the inductive hypothesis
x : xs  -- definition of id
id (x : xs)  -- definition of id

同様に、組成法則：

-- base case
(fmap f . fmap g) []
fmap f (fmap g [])  -- definition of (.)
fmap f []  -- definition of fmap
[]  -- definition of fmap
fmap (f . g) []  -- because [] = fmap f [], for all f

-- inductive step
(fmap f . fmap g) (x:xs)
fmap f (fmap g (x:xs))  -- definition of (.)
fmap f (g x : fmap g xs)  -- definition of fmap
f (g x) : fmap f (fmap g xs)  -- definition of fmap
(f . g) x : fmap f (fmap g xs)  -- definition of (.)
(f . g) x : fmap (f . g) xs  -- by the inductive hypothesis
fmap (f . g) xs  -- definition of fmap

関数

すべてのFunctorがコンテナのように見えるわけではありません。関数のFunctorのインスタンスは、別の関数の戻り値に関数を適用します。

instance Functor ((->) r) where
    fmap f g = \x -> f (g x)

この定義はfmap = (.)相当することに注意してください。だから、 fmapは関数の構成を一般化します。

もう一度アイデンティティ法をチェックしてください：

fmap id g
\x -> id (g x)  -- definition of fmap
\x -> g x  -- definition of id
g  -- eta-reduction
id g  -- definition of id

および組成法：

(fmap f . fmap g) h
fmap f (fmap g h)  -- definition of (.)
fmap f (\x -> g (h x))  -- definition of fmap
\y -> f ((\x -> g (h x)) y)  -- definition of fmap
\y -> f (g (h y))  -- beta-reduction
\y -> (f . g) (h y)  -- definition of (.)
fmap (f . g) h  -- definition of fmap

ファンクタとクラスのクラス定義

class Functor f where
    fmap :: (a -> b) -> f a -> f b

それを見る一つの方法は、 fmap が値の関数をコンテキストf値の関数に持ち上げることです。

Functorの正しいインスタンスは、 Functor 法則を満たす必要があります 。ただし、これらはコンパイラによって強制されません。

fmap id = id                    -- identity
fmap f . fmap g = fmap (f . g)  -- composition

<$>と呼ばれるfmapはよく使われるインフィックスエイリアスがあります。

infixl 4 <$>
(<$>) :: Functor f => (a -> b) -> f a -> f b
(<$>) = fmap

Functorのすべての要素を単一の値に置き換える

Data.Functorモジュールには、ファンクタに含まれるすべての値を無視して、すべてを単一の定数値に置き換えた2つのData.Functor <$および$>含まれています。

infixl 4 <$, $>

<$ :: Functor f => a -> f b -> f a
(<$) = fmap . const

$> :: Functor f => f a -> b -> f b
($>) = flip (<$)

voidは計算の戻り値を無視します。

void :: Functor f => f a -> f ()
void = (() <$)

多項式ファンクタ

より小さなものから大きなFunctorを構築するためのタイプコンビネータの有用なセットがあります。これらはFunctorサンプルインスタンスとして有益であり、汎用ファンクタの大きなクラスを表すために使用できるため、汎用プログラミングのテクニックとしても役立ちます。

アイデンティティファンクタ

アイデンティティファンクタは単に引数を囲みます。それは、SKI計算からのIコンビネータのタイプレベルの実装です。

newtype I a = I a

instance Functor I where
    fmap f (I x) = I (f x)

Iの名の下に、見つけることができますIdentityで、 Data.Functor.Identityのモジュール 。

定数ファンクタ

定数ファンクタは、定数値のみを含む第2引数を無視します。これは、SKI計算のKコンビネータであるconstタイプレベルのアナログです。

newtype K c a = K c

K caはa値が含まれていないことに注意してください。 K ()はProxyと同形です。これは、 Kのfmapの実装が全くマッピングをしないことを意味します。

instance Functor (K c) where
    fmap _ (K c) = K c

Kは、 Data.Functor.Const 。のConstとして知られています。

この例の残りのファンクタは、小さなファンクタをより大きなファクタに結合します。

ファンクター製品

ファンクタ製品は、一対のファンクタを取り、それらをパックする。これはタプルに似ていますが、 (,) :: * -> * -> *はtypes * 、 (:*:) :: (* -> *) -> (* -> *) -> (* -> *)はfunctors * -> *動作します。

infixl 7 :*:
data (f :*: g) a = f a :*: g a

instance (Functor f, Functor g) => Functor (f :*: g) where
    fmap f (fx :*: gy) = fmap f fx :*: fmap f gy

このタイプは、 Data.Functor.Productモジュールの Productという名前でData.Functor.Productます 。

ファンクター副産物

ちょうどのように:*:は(,)似てい:+:は、 Eitherファンクタレベルのアナログです。

infixl 6 :+:
data (f :+: g) a = InL (f a) | InR (g a)

instance (Functor f, Functor g) => Functor (f :+: g) where
    fmap f (InL fx) = InL (fmap f fx)
    fmap f (InR gy) = InR (fmap f gy)

:+:は、 Data.Functor.Sumモジュールの Sumという名前で見つけることができます 。

Functorの構成

最後に、 :.: 、タイプレベル(.)に機能し、あるファンクタの出力を取り出し、別のファンクタの入力につなぎます。

infixr 9 :.:
newtype (f :.: g) a = Cmp (f (g a))

instance (Functor f, Functor g) => Functor (f :.: g) where
    fmap f (Cmp fgx) = Cmp (fmap (fmap f) fgx)

Compose型は、 Data.Functor.Compose

ジェネリックプログラミングのための多項式ファンクタ

I 、 K 、 :*: 、 :+:および:.:は、特定のクラスの単純なデータ型のビルディングブロックとして考えることができます。これらのコンビネータで構築されたデータ型は自動的にFunctorインスタンスなので、 固定点と組み合わせると特に効果的になります。このキットを使用して、テンプレートタイプを作成し、 Iを使用して再帰的ポイントをマークしてからFixにプラグインして、再帰スキームの標準的な動物園で使用できるタイプを取得します。

データ型を設計するためのこの「キット」アプローチは、 generics-sopなどの汎用プログラミングライブラリの背後にあるアイデアです。上記のようなキットを使用して汎用操作を記述し、次にタイプクラスを使用して汎用データ型を汎用表現との間で変換することです。

class Generic a where
    type Rep a  -- a generic representation built using a kit
    to :: a -> Rep a
    from :: Rep a -> a

カテゴリ理論におけるFunctors

Functorは、カテゴリ理論では、カテゴリ間の構造維持マップ（「準同型性」）として定義されています。具体的には、（すべての）オブジェクトはオブジェクトにマッピングされ、（すべての）矢印は矢印にマッピングされ、カテゴリの法則が保持されます。

オブジェクトがHaskell型であり、morphismsがHaskell関数であるカテゴリは、 Haskと呼ばれます。だから、HaskへHaskからファンクタは、種類にタイプのマッピングおよび機能への機能のマッピングで構成されます。

このカテゴリの理論的概念がHaskellのプログラミング構築者Functor与える関係はむしろ直接的なものです。型から型へのマッピングは、型f :: * -> *の形式をとり、関数から関数へのマッピングは、関数fmap :: (a -> b) -> (fa -> fb) 。それらをクラスにまとめると、

class Functor (f :: * -> *) where
    fmap :: (a -> b) -> f a -> f b

fmapは、関数（モーフィズムの一種） :: a -> b a- :: a -> bをとり、それを別の関数:: fa -> fbに写像する演算です。 Functorインスタンスは確かに数学的ファンクタであると仮定されていますが（プログラマに任せておいてください）、 Haskのカテゴリ構造を保持しています。

fmap (id {- :: a -> a -})  ==  id {- :: f a -> f a -}
fmap (h . g)               ==  fmap h . fmap g

fmapは関数:: a -> bをHaskのサブカテゴリに持ち上げて、アイデンティティの矢印の存在と合成の結合性の両方を保持します。

Functorクラスは、 Haskの エンド・ファンクタのみをエンコードします。しかし、数学では、ファンクタは任意のカテゴリ間でマッピングできます。このコンセプトをより忠実にエンコードすると、次のようになります。

class Category c where
    id  :: c i i
    (.) :: c j k -> c i j -> c i k

class (Category c1, Category c2) => CFunctor c1 c2 f where
    cfmap :: c1 a b -> c2 (f a) (f b)

標準Functorクラスは、このクラスの特別なケースで、ソースカテゴリとターゲットカテゴリが両方ともHaskである場合です。例えば、

instance Category (->) where        -- Hask
    id    = \x -> x
    f . g = \x -> f (g x)

instance CFunctor (->) (->) [] where
    cfmap = fmap

ファンクターの導出

DeriveFunctor言語拡張により、GHCはFunctorインスタンスを自動的に生成することができます。

{-# LANGUAGE DeriveFunctor #-}

data List a = Nil | Cons a (List a) deriving Functor

-- instance Functor List where            -- automatically defined
--   fmap f Nil = Nil
--   fmap f (Cons x xs) = Cons (f x) (fmap f xs)

map :: (a -> b) -> List a -> List b
map = fmap