Software Engineering Lecture s02-1

Functor

あるデータ構造X が型aを要素として含むとする。すると、

    data X a = ...

の用に定義されているはずである。

この型 a の部分を関数で別な型 b に変換したい。

   x : X a
   f : a -> b

の時に、

   x' = fmap f x

として、

  x' : X b

を得たい。

X が普通のオブジェクトであれば、型aに対する要素を取り出して、関数作用させて、それを格納した型Xのオブジェクトを作れば良い。

     x.setSome ( f x.getSome )

しかし、Haskell では X は、さらに別な Y a を含むかもしれないし、リストの用に再帰的に定義されているかもしれない。

つまり、型変数 a に値を含むデータ構造でも、変更する対象は一つとは限らない。

Functor の型は、型 class を使って以下のように定義される。

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

この型は、

   :t fmap

で確認できる。

f a は、型 a に依存した型になる。

Funcotr はデータ構造X a の中身の一つに対して関数 f を適用する。

    instance Functor MyList where
            fmap _ Nil = Nil
            fmap f (Cons h t)  = Cons (f h) ( fmap f t )

instance Functor (MyList a) ではないのは何故か?

数字のリストを文字のリストに変更したかったら、

    let numList = Cons 1 ( Cons 2 Nil )
    fmap show numList

とする。

identity function

   
   id : a -> a
   id x = x

に対しては、

   fmap id x = x

であるべきだろう。fmap は、そのように実装されて欲しい。

関数の合成 f . g に関しては、

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

であるべきだろう。つまり、何かの型a を含むデータ構造xの型a の部分に関数f を作用させる操作なら、

　データ構造xに対してfmap f x は関数f を作用させるように振る舞って欲しい

この二つを Functor Law と呼ぶ。

Haskell の functor では、これを強制することはしない。

MyList と Haskell 内蔵の List が Functor Law を満たすことを確認する。

また、それがFunctor Law を満たすことを文章で示せ。

Functor law では、id に対しては、

   fmap id x = x

なので、実装は一つしかあり得ない。

Functor は一般的に unique つまり、二つの Functor fmap fmap' があれば、

   fmap f = fmap' f

になる。これは、Free Theorem から証明される。