bitterharvest’s diary

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

関手ー一般化

6.3 一般化

Maybeを利用して関手を説明したが、その他にもいろいろな関手を考えることができる。それらは(Maybeで説明した)fmapの実装が異なるだけだ。Javaを知っている人であればインターフェースを用いて実装したらと考えるだろう。Haskellにもオブジェクト指向と同じ概念のものが用意されている。Haskellでは、関手はクラスで一般化し、個々の実体はそのインスタンスで表現できる。

それでは実際に示してみよう。次のようになる。

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

上記のプログラムで、fが関手である。Haskellでは型コンストラクタとなる。
なお、GHCでの定義を見ると次のようになっている。

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

f aとf bがカッコでくくられていないが、これをカーリー化すると(f a -> f b)になるので、表現は異なるが内容は同じである。

これを用いると、Maybeはクラスをインスタンス化し、次のように実装できる。

data Maybe a = Nothing | Just a deriving (Eq, Show, Read)
instance Functor Maybe where
  fmap _ Nothing = Nothing
  fmap f x = Just (f x)

これまで、fmap f Nothing = Nothingと書いてきたが、どのようなfが来たとしてもNothingを出力するので、ここではfの代わりに_を用いた。
プログラムを実行してみよう(実装されているMaybeとぶつかるようであれば、Maybe’, Just’, Nothing’のように’をつけて実装し、実行して欲しい)。

*Main> fmap (+3) (Just 5)
Just 8
*Main> fmap (+3) Nothing
Nothing

それではリストはどうであろうか。Maybeを参考にしながら実装しよう。

data List a = Nil | Cons a (List a) deriving (Eq, Show, Read)
instance Functor List where
  fmap _ Nil = Nil
  fmap f (Cons h t) = Cons (f h) (fmap f t)

上のプログラムで、Cons h tと書いたが、hはリストの最初の要素、tはこれを取り除いたリストである。

プログラムを実行してみよう。

*Main> fmap (+3) (Cons 3 (Cons 4 (Cons 5 Nil)))
Cons 6 (Cons 7 (Cons 8 Nil))

Haskellが用意しているFunctorのインスタンスを調べてみよう(厳密にはGHCが用意しているインスタンス)。

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

上記に示すような結果を得たことと思う。
ところで下から2行目に見慣れないものがある。((->) r)なのだが、これはリーダーと呼ばれる。それではこのリーダーについて説明しよう。

Haskellでは、関数は\(a \rightarrow b\)と記述される。\(a\)が入力で\(b\)が出力である。ところで、\( \rightarrow \)を\(+\)や\(\times\)などと同じように中置関数と考えると、これを前置関数に変えることで\( (\rightarrow) \ a \ b \)と表すことができる。

そこで、\( (\rightarrow) \ a \ b \)は、\(a\)を\(b\)に変換してくれる型コンストラクタと解釈することが可能となる。従って、

type Reader a = (->) a

と表すことが可能となる。
あるいは、両辺から\(a\)を取り除いて

type Reader = (->)

と表しても構わない。これで、\( (\rightarrow) \)は型コンストラクタとなった。ここでは、それを\(Reader\)というシノニムで置き換えている。

ところで、次の図を考えよう。
f:id:bitterharvest:20170218180104p:plain
図で左側は関数\(f:\)でそのドメインは\(a\)でありコドメインは\(b\)である。今、これら\(a,b\)を、右側に示すように、\(r\)をドメインにし、そのコドメインに持ち上げてしまおう。\(a\)を\(g:r \rightarrow a\)に写像する関数は、\(Reader \ r \ a\)と表すことができる。

それでは、\(b\)を\(r \rightarrow b\)に移す関数はどうなるであろうか。\(b\)を関手\(Reader \ r\)を用いて、\(r \rightarrow b\)に写像する。そして、\(r \rightarrow b\)は射である。関手を射に写像するときは\(fmap\)を用いていた。そこで、\(fmap \ (Reader \ r) \)と考えられる。

これでよさそうなのだが、何となくすっきりとしない。そこで、Haskellでの互換図ではなく、圏論での互換図で表してみることにしよう。
f:id:bitterharvest:20170220104235p:plain

上記の互換図で、\({\rm Hom}(R,A)\)は、対象\(R\)から\(A\)への射の集合である。また、\({\rm Hom}(R,\_)\)は\(R\)をドメインとする射の集合である。\(A\)から射の集合\({\rm Hom}(R,A)\)への射の集合は\({\rm Hom}(R,\_)\)となる。

次に、\(R\)から\(B\)への写像を考えてみよう。これは、\(\mathcal {D}\)のところの互換図を用いればよい。(上側の)\(R\)から\(A\)を経由して\(B\)にいたる射の集合を求めると\({\rm Hom}(R,A) \times {\rm Hom}(A,B)\)となる。同じように、(上側の)\(R\)から(下側の)\(R\)を経由して\(B\)にいたる射の集合を求めると\({\rm Hom}(R,R) \times {\rm Hom}(R,B)={\rm Hom}(R,B)\)となる。これが先に求めたものと等しいので、\({\rm Hom}(R,B)={\rm Hom}(R,A) \times {\rm Hom}(A,B)\)となる。

そこで、\(B\)から\({\rm Hom}(R,B)\)への射の集合は、今求めた\({\rm Hom}(R,B)={\rm Hom}(R,A) \times {\rm Hom}(A,B)\)から\(B\)を\(\_\)に代えればよいので、\({\rm Hom}(R,\_)={\rm Hom}(R,A) \times {\rm Hom}(A,\_)\)となる。

少し長くなったが、\(fmap \ (Reader \ r) \)でよいことが判明した。

従って、\(fmap\)のリーダーに対する実装は次のようになる。

type Reader = (->)
instance Functor (Reader r) where
  fmap :: (a -> b) -> (r -> a) -> (r -> b)
  fmap f g = f . g

ここで、f.g は(.) f gと表すことができ左右の辺からf,gを消去すると最終的には次のようになる。

type Reader = (->)
instance Functor (Reader r) where
  fmap :: (a -> b) -> (r -> a) -> (r -> b)
  fmap= ( . )

上記のプログラムをロードするとUse TypeSynonymInstancesとエラーが出る。そこで、これを用いて再度ロードするとファンクタが二重定義であるというエラーが出る。これは、Haskellが(->)のファンクタを用意しているためである。従って、Haskellがあらかじめ用意しているものをここでは用いる。Haskellではどのようになっているかをまず、見てみよう。データ型の定義は次のようになっている。

Prelude> :i (->)
data (->) t1 t2 	-- Defined in ‘GHC.Prim’

しかし、GHC.Primを参照してもこのデータ型の定義は見当たらない。ファイクコードだそうだ。これは表示のためだけに使われているそうである。
しかし、ファンクタの方はちゃんと定義されている。Data.Functorを見ると次のようになっている。

instance Functor ((->) r) where
    fmap = (.)

システムが用意しているものを実際に使うとこんな感じになる。あまり面白くはない。

Prelude> ((+3) . (*4)) 5
23
Prelude> ((+3) . (+4)) 6
13

次回は、圏から圏を作ることを説明する。