bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

HaskellドリルⅣ 型クラスとしてのファンクタ

1.圏論

ファンクタという用語は、日本語では関手という。少し奇妙な名前だが、最も抽象的な数学である圏論で用いられる用語で、カテゴリ間の写像を表す時に用いる。ここでは、圏論の話を少しして、Haskellで用いられているファンクタの概念がどのようなものであるかを理解する。

圏論の分野で使われる圏(カテゴリ)は、次のようなものである。
圏とは、
対象(Object):\(A,B,C,...\)
射(Morphism):\(f,g,h,...\)
射の合成(Composition):\( \circ \)
からなり、以下の条件をすべて満たすものである。
1)任意の射\(f\)に対して、ドメイン(Domain) \({\rm dom}(f)\)、コドメイン(Codomain) \({\rm co d}(f)\)という二つの対象が備わっている。\({\rm dom}(f)=A\)で\({\rm co d}(f)=B\)のとき、\(f:A \rightarrow B\)と表す。
2)射\(f:A \rightarrow B\), \(g:B \rightarrow C\)が存在するならば、合成射(Composite) \(g \circ f:A \rightarrow C\)も存在する。
3)任意の射\(f:A \rightarrow B\), \(g:B \rightarrow C\), \(h:C \rightarrow D\)に対して結合律(Associative Law) \((h \circ g) \circ f\)=\(h \circ (g \circ f)\)が成り立つ。
4)任意の対象\(A\)に対して、恒等射(Identity) \(id_A:A \rightarrow A\)が存在し、任意の射\(f:A \rightarrow B\)に対して単位律(Identity Law) \(f \circ id_A = id_B \circ f = f\)が成り立つ。

2.圏の例

例1:対象を1から始まる自然数とする。射は倍数にする関数\(f(x)=2x\)と自信に写像する関数\(id(x)=x\)する。射の合成は、\(f \circ f = f(f(x))\)とする。以上のように定義すると、
f:id:bitterharvest:20141228065806p:plain
条件1は上図に示すように、ドメインは\(\mathbb{N} \)、コドメインは\(2 \mathbb{N} \)となる。
条件2の合成射は上図に示すように、\( (f \circ f)(x)=4x\)となり存在する。
条件3の結合律は上図より\( (f \circ (f \circ f))(x)=8x\), \( ( (f \circ f) \circ f))(x)=8x\)より、\( (f \circ (f \circ f))(x)=( (f \circ f) \circ f))(x)\)となる。
条件4の単位律も成り立つことは明らかである。
従って、上で定義された対象、射、射の合成で構成されたものは圏である。

例2:対象を\(n\)で始まる自然数の数列とする。但し、\(n\)は1から無限までとする。例えば、\(n\)が5の時は、数列は[5,6..]である。射を数列のそれぞれの要素を2倍にする関数\(fmap([n,n+1..])=[2n,2(n+1)..]\)と自分自身に写像する関数\(id([n,n+1..])=[n,n+1..]\)とする。例えば、3で始まる数列[3,4..]に対して、倍にする関数を施すと、[6,8..]となる。射の合成は\(fmap \circ fmap = fmap(fmap([n,n+1..]))\)とする。このように定めると例1と同じように条件1から4までが満たされ、これも圏であることが分かる。

例3:例1は基本的には倍数にする関数が一つしかなかったが、\(n\)倍する関数\(f_n(x)=nx\)、但し、\(n\)は1から無限大まで、を用意する。これによって、無限の射が存在することとなる。合成関数を\(f_n \circ f_m = f_n (f_m (x)) = nmx\)と定める。これにより構成されるものも、条件の1から4を満たすので、圏であることが分かる。(分かりにくければ、関数の数を有限、例えば、2倍、3倍、5倍、にすれば感触がつかめると思う。)

例4:同様に例3でのそれぞれの要素を2倍にする関数を、\(n\)倍する関数で置き換えると、無限の射で構成された圏となる。

3.関手

圏が分かったところで、関手の説明に移る。関手は二つの圏があった時に、一つの圏の構造を他の圏に移す写像と考えられる。関手の定義は次のようになっている。

圏\(\mathcal{C}\)から圏\(\mathcal{D}\)への関手\(F:\mathcal{C} \rightarrow \mathcal{D}\)とは \(\mathcal{C}\)の各対象\(A\)に\(\mathcal{D}\)の対象\(F(A)\)を対応付け, \(\mathcal{C}\)の各射\(f:A→B\)に\(\mathcal{D}\)の射\(F(f):F(A)→F(B)\)を 対応付ける2つの関数の組であり,以下の条件を満たすものである。
1)任意の\(\mathcal{C}\)の射\(f:A→B\), \(g:B→C\)に対して\(F(g∘f)=F(g)∘F(f)\)
2)任意の\(\mathcal{C}\)の対象\(A\)に対して\(F(id_A)=Id_{F(A)}\)
上記の関係を示したのが、下図である。
f:id:bitterharvest:20141228093336p:plain

4.関手の例

それでは、関手の例を挙げておく。

例5:例1で構成される圏\(\mathcal{C}\)から例2で構成される圏\(\mathcal{D}\)への写像\(F:\mathcal{C} \rightarrow \mathcal{D}\)を次のように定める。\(F\)は、圏\(\mathcal{C}\)の対象\(A\)を圏\(\mathcal{D}\)の対象「\(A\)から始まる数列」に写像する。また、\(F\)は、圏\(\mathcal{C}\)の射[倍にする関数\(f\)」を圏\(\mathcal{D}\)の射[それぞれの要素を倍にする関数\(fmap\)」に写像する。さらに、\(F\)は圏\(\mathcal{C}\)の恒等関数\(id\)を圏\(\mathcal{D}\)の恒等関数\(Id\)に写像すると定める。\(F\)は条件1と2を満たすので、圏\(\mathcal{C}\)から圏\(\mathcal{D}\)への関手となる。

例6:同様に、例3と例4にも写像\(F\)を定めると、\(F\)は関手となる。

5.Haskellでのファンクタ

Haskellのファンクタの原理に基づいたものである。まず、ファンクタの定義を観察する。

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

関手は、対象と射をある圏から他の圏に写像する。対象間の写像は\(F(A)\)で、射間の写像は\(F(f)\)である。Haskellではこれらの写像を次のように定義する。\(F(A)\)はFunctorの右側にある(f :: * -> *)である。また、\(F(f)\)はfmapで、fはfmapの最初の入力(a -> b)である。

例5で説明すると、関手は、ある自然数を、その自然数で始まる数列に写像し、自然数を倍にする関数を要素を倍にする関数に写像することとなる。

ファンクタの中で最も頻繁に利用されるのはリスト[ ]である。下の図を用いて説明する。
f:id:bitterharvest:20141213072206p:plain

この図では文字の圏と文字列の圏が用意されている。

文字の圏では、対象はアルファベットである。射は大文字への変換と恒等写像である。射の合成は単に文字を並べることである。この構成で、圏の条件1から4までが満たされていることは容易にわかることと思う。

文字列の圏は、対象はアルファベットで構成された文字列である。射は構成している文字をすべて大文字に変換する写像と恒等写像である。射の合成は文字列をつなげることである。同様に、この構成で、圏の条件1から4までが満たされていることは容易にわかることと思う。

文字の圏から文字列の圏への写像は、
対象に対しては、「一つあるいは並んでいる文字を、同じ並びの文字で構成されている文字列」に対応させる。
射に対しては、「大文字への変換を、文字列の中の文字をすべて大文字に変換する」に対応させる。されに、恒等関数同士を対応させる。
このように定めると、関手の条件1、2を満たすので、この写像は関手となる。

そこで、関手を[ ]とし、fmapをmap toCapitalにすれば、上図の文字から文字列への変換はファンクタを用いて実現できることになる。実際にプログラムを実行して確かめてみる。

大文字への変換は次のようになる。

toCapital :: Char -> Char
toCapital a 
  | a `elem` small = getCapital' a pair
  | otherwise = a 
  where
    small = ['a'..'z']
    capital = ['A'..'Z']
    pair = zip small capital
    getCapital' :: Char -> [(Char, Char)] -> Char
    getCapital' _ [] = error "A capital letter does not exist."
    getCapital' a' ((ySmall, yCapital):ys)
      | a' == ySmall = yCapital
      | otherwise = getCapital' a' ys

また、fmap'(ここではPreludeのfmapとの衝突をつけるためfmap'とする。)を次のようにする。

fmap' = map toCapital

文字の並びを文字列に変換する(対象に対する)ファンクタは[ ]なので、文字の列'T','h','i','s',' ','i', 's', ' ', 'a',' ','b','o','o','k','.'は['T','h','i','s',' ','i', 's', ' ', 'a',' ','b','o','o','k','.']によって文字列に変換される。
文字列に対して、構成要素を大文字に変換する関数はfmap'であるので、これを実行すると次のようになる。

Prelude> :load "Functor.hs"
[1 of 1] Compiling Main             ( Functor.hs, interpreted )
Ok, modules loaded: Main.
*Main> fmap' ['T','h','i','s',' ','i', 's', ' ', 'a',' ','b','o','o','k','.']
"THIS IS A BOOK."

上記で得た文字列は、文字の列に対して、大文字への変換を行い、即ち、'T','H','I','S',' ','I', 'S', ' ', 'A',' ','B','O','O','K','を得て、これを文字列['T','H','I','S',' ','I', 'S', ' ', 'A',' ','B','O','O','K',']に変換して得たものと同じである。

例7:それでは、次に、例5のファンクタを考える。(対象に対する)ファンクタは\(n\)が与えられた時\(n\)で始まる数列を作るので、次のようになる。

toSequence n = [n, (n+1) ..]

また、2倍する関数を次のように定める。

f2 = (*2)

これよりmapに入力される関数はf2となる。

これにより、5から、この数で始まる数列を得て、構成要素を2倍にするプログラムは次のようになる。

Prelude> :load "Functor.hs"
[1 of 1] Compiling Main             ( Functor.hs, interpreted )
Ok, modules loaded: Main.
*Main> take 10 $ map f2 $ toSequence 5
[10,12,14,16,18,20,22,24,26,28]

例8:さらに進んで、例6のファンクタを考えることにする。ここでは、倍数がたくさん出てくるが、取りあえず、2倍と3倍を用意し、次のように定める。

f2 = (*2)
f3 = (*3)

先と同じように、2倍して3倍する数列を求めることにする。ここでは、射に対するファンクタの条件の一つである\(F(f \circ g)=F(f) \circ F(g)\)を観察する。

まず、最初に\(F(f) \circ F(g)\)、即ち、(map f3 (map f2))で計算する。

Prelude> :load "Functor.hs"
[1 of 1] Compiling Main             ( Functor.hs, interpreted )
Ok, modules loaded: Main.
*Main> take 10 $ map f3 $ map f2 $ toSequence 5
[30,36,42,48,54,60,66,72,78,84]

次に、\(F(f \circ g)\)、即ち、map (f3.f2)を求める。結果は次のようになる。

Prelude> :load "Functor.hs"
[1 of 1] Compiling Main             ( Functor.hs, interpreted )
Ok, modules loaded: Main.
*Main> take 10 $ map (f3.f2) $ toSequence 5
[30,36,42,48,54,60,66,72,78,84]

これから、\(F(f \circ g)=F(f) \circ F(g)\)が確認された。

6.ファンクタのインスタンス

ファンクタは型クラスである。文字から文字列への変換や、自然数\(n\)から\(n\)で始まる数列への変換がファンクタであることを観察した。Haskellでこれらをファンクタにするためには、これらを型としなければならない。上記で述べたもの一つ一つを型にするには、あまりにも具体的すぎるので、上記のすべてに共通するような型を導入する。文字から文字列への変換も自然数から数列の変換も、変換先は列、即ち、リストであるので、リストという型を用意することとする。幸い、Haskellでは次のように用意されている。

Prelude> :info []
data [] a = [] | a : [a]

また、リスト[ ]はファンクタのインスタンスとして、次のように用意されている。定義を見ると、fmapがmapとなっていることが分かる。これは、今までに観察してきたことである。

instance Functor [] where
  fmap = map

この定義により、例8、例9で使ったmapをfmapに変えることができる。以下に示す。

*Main> take 10 $ fmap f3 $ fmap f2 $ toSequence 5
[30,36,42,48,54,60,66,72,78,84]
*Main> take 10 $ fmap (f3.f2) $ toSequence 5
[30,36,42,48,54,60,66,72,78,84]

7.問題

それでは問題を解くことにしよう。

ファンクタを詳しく観察するとどのようなインスタンスが用意されてるかが分かる。

Prelude> :info Functor
class Functor (f :: * -> *) where
  fmap :: (a -> b) -> f a -> f b
  (GHC.Base.<$) :: a -> f b -> f a
  	-- Defined in ‘GHC.Base’
instance Functor Maybe -- Defined in ‘Data.Maybe’
instance Functor (Either a) -- Defined in ‘Data.Either’
instance Functor [] -- Defined in ‘GHC.Base’
instance Functor IO -- Defined in ‘GHC.Base’
instance Functor ((->) r) -- Defined in ‘GHC.Base・f
instance Functor ((,) a) -- Defined in ‘GHC.Base’

問題1:Maybeは次のような型として定義されている。

data Maybe a = Nothing | Just a 

型Maybeはaが値を有していないときはNothingであり、値を有しているときJust aである。Justの使用例は以下のとおりである。

Prelude> Just (3 + 5)
Just 8
Prelude> Just ("bo" ++ "ok")
Just "book"
Prelude> Just (sqrt 2)
Just 1.4142135623730951
Prelude> Just (3 + sqrt 2)
Just 4.414213562373095 

Maybeをファンクタのインスタンスとしなさい(例えば、fmap (*2) (Just 3) = Just 6となる)。

問題2:ファンクタのインスタンスMaybeにおいて、fmapで施す関数を(*2)とした時、これを用いた例を示しなさい。

問題3:ファンクタのインスタンスMaybeにおいて、fmapで施す関数を(++s)とした時、これを用いた例を示しなさい。

問題4:ファンクタのインスタンスMaybeにおいて、fmapで施す関数を(\x -> x * x)とした時、これを用いた例を示しなさい。

問題5:Eitherは次のような型として定義されている。

Prelude> :info Either
data Either a b = Left a | Right b

Eitherをファンクタのインスタンスとしなさい。但し、ファンクタによって影響を受けるのはRight bの方であり、Right f(b)となる。Left aは影響を受けない。

問題6:ファンクタのインスタンスEitherにおいて、fmapで施す関数を(*2)とした時、これを用いた例を示しなさい。

問題7:ファンクタのインスタンスEitherにおいて、fmapで施す関数を(++s)とした時、これを用いた例を示しなさい。

問題8:ファンクタのインスタンスEitherにおいて、fmapで施す関数を(\x -> x * x)とした時、これを用いた例を示しなさい。

問題9:ペア(,)をファンクタのインスタンスとしなさい。但し、ファンクタによって影響を受けるのは右側の要素で(_,b)のとき(_,f(b))となる。左側の要素は影響を受けない。

問題10:ファンクタのインスタンス(,)において、fmapで施す関数を(*2)とした時、これを用いた例を示しなさい。