読者です 読者をやめる 読者になる 読者になる

めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

Functorを例として、圏論とHaskellの関係を分かりやすく説明してみるテスト

[参考文献]

カテゴリーとは?

「カテゴリー」は、「集合と写像」の概念をより抽象化(簡単化)したものです。おもむろに、図1のように、いくつかの●と、●の間の矢印が集まった図式を考えてみます。


図1 カテゴリーのイメージ

それぞれの●は、「a,b,c・・・」で表して、矢印は、「f,g,h,i,j,k・・・」で表します。1組みの●のペアに対して、複数の矢印があっても構いません。また、矢印fがaとbをつなぐ事を次のように表現します。

f :: a -> b

「集合と写像」の勉強をした方なら、それぞれの●は何らかの集合で、矢印は集合間の写像と思うと分かりやすいでしょう。

この時、

f :: a -> b
g :: b -> c

のように、ある●(ここでは「b」)を介して2つの矢印がつながる場合、これを1つにつなげた矢印、

h = g.f :: a -> c

が必ず存在するものとします。「集合と写像」で言うと、合成関数が作れるということですね。

2つの矢印をつなげた後、さらにもう1つつなげて、3つの矢印をつなげる事も可能ですが、全部つなげた結果は、つなげる順番に依存しないものとします。

(g.f).k = g.(f.k)

最後に、任意の●について、自分自身への矢印

id_a :: a -> a

が存在して、

f.(id_a) = f
(id_a).g = g

が成り立つものとします。「集合と写像」で言うと、恒等写像が存在するということですね。

このあたりは、「集合と写像」の場合であれば、「成り立つものとします」ではなくて、そもそも「成り立って当然」なのですが、カテゴリーの面白いところは、「集合と写像」とはまったく関係無い「●と矢印の図式」においても、同様のルールが成り立つ場合がある、というところです。その一例が、次に説明するHaskellにおける「型と関数のカテゴリー」です。

Haskellにおけるカテゴリー

Haskellはご存知のように「関数型言語」、つまり「関数」が主役です。また、「強く型づけされた言語」ですので、それぞれの関数は、「どの型からどの型への関数」なのかという事が厳格に決められています。

そこで、Haskellのあらゆる型を●で表した図を用意しておくと、それぞれの関数は、どれか2つの●を結ぶ矢印として表記することで、「どの型からどの型への関数」なのかを明示することができます。ただし、Haskellの型は無限にあるので、この図は無限に広がる巨大なものになります。図2は、巨大な図の一部として、「Int」「Char」「Bool」などの基本型のみを●で表記したものです。[Int]、[Char]などのリストも基本型でしたよね。


図2 型と関数のカテゴリー(のごく一部)

さて、Haskellでは、高階関数(関数の関数)が許されますので、「型から型への写像」つまり、「(Int -> Int)」とか「(Int -> Bool)」なども同じく「型」として扱われます。したがって、図2をもうちょっと書き足すと図3のようになります。


図3 高階型を含めて記載した「型と関数のカテゴリー」

ここで、型と関数を混乱しないように注意してください。例えば、

f = (+1) :: Int -> Int

は、「Int」から「Int」への関数、つまり「Int」の●を結ぶ「矢印」です。型としての「(Int -> Int)」、つまり「●」自身がfというわけではありません。あくまで、関数が矢印で、型が●です。

ここで、先のカテゴリーの定義を思い出すと、この図3は、カテゴリーになることが分かります。正確には、図3そのものではなくて、「あらゆる型と関数をすべて寄せ集めて作った「型と関数の図式」」がカテゴリーになります。図3は、そのような巨大のカテゴリーの一部を抜粋して描いていると理解してください。

ちなみに、「集合と写像」の場合、●は集合、つまり複数の要素が集まって出来上がった「複合体」ですが、図3の●は、1つの「型」を表現した抽象的な存在です。決して何かが寄り集まった集合ではありません。

図3において、●を「その型を持つ定数が中につまった集合」と考えたくなるかも知れませんが、決してそのようには考えないでください。関数というのは、具体的な「値」を代入して、具体的な「値」を取り出して、初めて実用的に役立つわけですが、具体的な値を忘れて、関数と型の関係だけを取り出して議論した方が、話が分かりやすくなることもあります。「型と関数のカテゴリー」は、そのための道具立てになります。

Functorとは?

圏論におけるFunctor(関手)とは、2つのカテゴリーを並べて、一方から一方へ、●と矢印を対応付ける関係付けのことです。

カテゴリーAの●と矢印を「a,b,c・・・」「f,g,h・・・」
カテゴリーBの●と矢印を「aa,bb,cc,・・・」「ff,gg,hh・・・」

と表記した際にカテゴリーAの任意の●と矢印について、

F: a ===> aa
F: f ===> ff

という感じで、対応するカテゴリーBの●と矢印が決まるとき、この関係づけFがFunctorとなります。ただし、Functorは次のルールを満たす必要があります。

f :: a -> b として、F(f) :: F(a) -> F(b)
F(id_a) = id_aa
F(f.g) = F(f).F(g)

最初のルールは、Fは、矢印と●をくっつけたままにするということで、その後は、恒等写像は恒等写像に移すことと、矢印を合成してから写したものは、移してから合成したものと一致する、ということです。

ちょっと、抽象的で分かりにくいので、先の「型と関数のカテゴリー」で具体例を紹介します。一般には、カテゴリーAとカテゴリーBは、全く別のカテゴリーで構わないのですが、HaskellのFunctorでは、同じ「型と関数のカテゴリー」を2つ並べて、そのあいだの関係付けを行います。(こういうものを自己関手/Endofunctorと言います。)

いろんな関係づけが考えられますが、たとえば、図4の例、

F: a ===> [a]
F: f ===> map f

はどうでしょうか。図4における「カテゴリーA」「カテゴリーB」はどちらも同じ「型と関数のカテゴリーです」


図4 「型と関数のカテゴリー」におけるFunctorの例

図から分かるように、Int型を[Int]型(Intのリスト)、Bool型を[Bool]型、というように、あらゆる型をその型のリストに対応づけようというわけです。矢印の対応付けについては、先のルールを満たすようにうまく考える必要がありますが、

f :: a -> b ならば、map f :: [a] -> [b]

という型の関係を考えると、「f を map f に対応づける」という方法で最初のルールが満たされることが分かります。残りの2つのルールももちろん成立します。

このようにして、[]とmapというペアーは、圏論におけるFunctorであることが分かりました。この事実を持って、Haskellにおいても、リストはFunctorの仲間として認められています。もう少し正確に言うと、Haskellの場合、まず、Functorは次のような「型クラス」として定義されています。

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

これまで大文字のFでFunctorを表していましたが、ここでは、小文字のfがFunctorを表しているので注意してください。これは、

・fは、型「a」「b」に対して、新しい型「f a」「f b」を対応付けている
・元の型「a」「b」の間の関数「h :: a -> b」に対して、新しい型「f a」「f b」の間の関数「fmap h :: f a -> f b」が対応付けられている

という2つの事実を表しています。先ほどのリストの例でいうと、

・f = []
・fmap = map

と考えるとピタリと当てはまることが分かります。実際、リストは、次のように型クラスFunctorのインスタンスとして定義されています。

instance  Functor []  where
    fmap = map

型と類の違い

ところで、図4から分かるように、HaskellにおけるFunctor(例えば[])は、型から型への写像です。関数(カテゴリーにおける矢印)とは別の概念であることに注意してください。一般に、このような型の間の写像(関数)は、「型コンストラクタ」と呼ばれます。普通の関数は、その「型」を持ちますが、型コンストラクタには、対応する「kind(類)」が付随します。Functorの場合は、1つの型「*」をもう1つの型「*」に移すので、Functorのkindは「*->*」のように表現されます。

一般に「型コンストラクタ」は、0個以上の引数を持ちます。0個の引数を持つものは、それ自体が「型」を表すので、kindは「*」です。[]やMaybeのように1個の引数を持つものは「*->*」。Eitherのように2個の引数を持つものは「*->*->*」となります。

先に、Functorは「型クラス」として定義されていると言いましたが、Functor自身は決して型ではありません。型から型への対応づけ(型を与えると新しい型を生み出すもの)なのです。このあたりがFunctorの理解を難しくしている要因かも知れません。同様の存在に、「Maybe」など、いわゆる多相型の型コンストラクタがあります。つまり、Maybeは型ではありませんが、Intという型を与えると、「Maybe Int」という新しい型を生み出してくれます。

というわけで、実は、MaybeもFunctorの仲間になっています。具体的な定義は次の通りです。

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

リストの場合は、mapで、リスト内の値に関数を適用することが、矢印の対応付け(fmap)の実体でした。Maybeの場合は、この定義から分かるように、Just内の値に関数を適用するものをfmapの実体としています。