Haskell Language
ファンクタ
サーチ…
前書き
Functor
は、共変にマップされるf :: * -> *
型のクラスです。関数をデータ構造体にマッピングすると、構造体自体を変更せずに構造体のすべての要素に関数が適用されます。
備考
Functorは、ある価値のためのコンテナ、または計算コンテキストと考えることができます。例はMaybe a
または[a]
。 Typeclassopediaの記事は、 Functorsの背後にある概念を書き上げています。
実際のFunctorとみなされるためには、次の2つの法律を遵守しなければなりません。
身元
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
にプラグインして、再帰スキームの標準的な動物園で使用できるタイプを取得します。
名 | データ型 | ファンクタキットを使用する |
---|---|---|
値のペア | data Pair a = Pair aa | type Pair = I :*: I |
2×2グリッド | type Grid a = Pair (Pair a) | type Grid = Pair :.: Pair |
自然数 | data Nat = Zero | Succ Nat | type Nat = Fix (K () :+: I) |
リスト | data List a = Nil | Cons a (List a) | type List a = Fix (K () :+: K a :*: I) |
バイナリツリー | data Tree a = Leaf | Node (Tree a) a (Tree a) | type Tree a = Fix (K () :+: I :*: K a :*: I) |
ローズの木 | data Rose a = Rose a (List (Rose a)) | type Rose a = Fix (K a :*: List :.: I) |
データ型を設計するためのこの「キット」アプローチは、 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