https://github.com/scalajp/introduction-to-category-theory-in-scala-jp/wiki

に移動しました。こちらは、ミラーとさせていただきます。

これは、Typesafe 社の Director Professional Services である Heiko Seeberger 氏による「Introduction to Category Theory in Scala」の翻訳文です。誤訳、誤記などがありましたら、日本Scalaユーザーズグループの「圏論入門　レビューのお願い」トピックに投稿していただくか、@quassia88 にご連絡ください。

もし君が僕みたいに、以前はJavaディベロッパーで、Scalaのファンになったばかりなら、君は多分遅かれ早かれ、モナドやら関手やらの、圏論の分野からやってきた謎に遭遇するだろう。そういった未知の概念は、君を、自分が恐ろしくまぬけなんじゃないか、という気分にさせることだと思う。もし君がそういう概念に既に親しんでいるなら、時間を無駄にすることはない、すぐにこのページを閉じてほしい。もしそうでないなら、君をちょっとした観光に招待したい。僕が苦労の末に見つけた、抽象数学とコンピューターサイエンスの狭間の秘密の王国へ。

このポストは、あくまで入門を目指している。僕の健康状態（文章を書いているときは、僕は頭が爆発するんじゃないかとヒヤヒヤしている）と、将来の空き時間（理解というのというのは、たとえ来たにせよ、ゆっくりやって来るものだ）と、あなたのフィードバックによるが、僕はフォローアップを書くつもりでいる。だが、まずは始めてみよう。

圏論について語るときに、明らかに最初に出てくる質問だろう。しかし、僕の意見では、圏の定義はプログラミングにそんなに有用というわけじゃない。広義の回答は次の通りだ。

圏（category）とは、対象（object）と対象間のマップ（map）からなる。マップは、射（morphism または arrow）とも言う。マップは、結合則（associativity）にしたがって合成する（compose）ことができる。また、それぞれの対象に対して、合成に関して中立な恒等射（identity map）が存在する。

対象は何でもいいんだけど、とりあえず単純な例「有限集合の圏」を見てみよう。下の図は、2つの有限集合とその間のマップ、つまり、ソース（source）からターゲット（target）へのマップを表している。なお、ソースとターゲットはそれぞれ、ドメイン（domain）とコドメイン（codomain）とも呼ばれる。

訳注：マップ・射については、上の図や map という語から、集合・位相論の「写像」を連想される方もおられると思うが、別物である。Wikipedia の解説が比較的詳しい。圏論では「射」を使う方が一般的である。

もうちょっと形式的に、ドメインを A 、コドメインを B とし、その間のマップを以下のように書くことができる。

さて、合成（composition）とはなんだろう？次の図を見てみよう。ここには、もう一つの有限集合とマップを追加してある。

新しい集合をC、新しいマップを

と呼ぼう。明らかに、最初に f を、その後 g を適用することによって、 A から C へのマップを得ることができる。したがって、f と g との合成によって、新しいマップを得られる。

さて、合成について知った今、今度は結合則と恒等射について話さなきゃならない。新しいマップ h: C -> D を追加しよう。このとき、結合則は以下の式が真であることを要求する。

結合則は、数の和算や乗算を思い浮かべてもらえば、すぐに分かるようになるはすだ。

さて、恒等射に進むことにしよう。恒等射は、圏の任意の対象 X に対して、自分自身と等しくなるマップ

が存在し、かつ、任意の射 f: A -> B に対し、

が成り立つことを要求する。以下の図は、先ほどの有限集合の圏の例における恒等射を表している。明らかに、恒等射はドメインとコドメインで同じ対象になる。

OK。これで全部だ。対象、マップがあり、マップの合成が定義でき、かつ結合則と恒等射の条件を満たす。これが圏だ。もし、君がもうちょっと理論の深みにはまりたいんなら、Wikipedia か“Conceptual Mathematics” by Lawvere and Schanuel をオススメする。さて、ちょっと気分を変えて、Scala の観点から圏をながめてみよう。

注記：以下の内容で、たくさんのアイデアといくらかの（ちょっと修正した）コードを、scalaz プロジェクトから借用することになる。この Scala ライブラリはApocalisp blog とともに、Scala で先進的な関数プログラミングを行ううえで、非常に価値ある情報源・インスピレーション源になる。

有限集合の圏について、今まで例をみてきたわけだけど、ここでは Scala で圏を実装してみよう。つまり、Scala の型を対象、関数をマップとする圏について考えてみる。定義されたものが圏であることを証明しなきゃならないけど、とりあえずコードを見てみよう。

objectCategory {defid[A]:A=>A= a=> adefcompose[A,B,C](g:B=>C,f:A=>B):A=>C=  g compose f// This is Function.compose, not a recursive call!}

OK、必要となる材料は全部揃っているように見える：型が対象、引数を一つとる関数（Function トレイト）はマップ、関数id がそれぞれのA に対する恒等射で、関数compose がふたつの関数を合成する。

これらは疑う余地なく、結合則と恒等射を満たすように見える。けれども、念のためユニットテストを書いてチェックしておこう。ここでは、specs と ScalaCheck フレームワークを使うことにする。

classCategorySpecextendsSpecificationwithScalaCheck {importCategory._"A Category" should {valf= (i:Int)=> i.toStringvalg= (s:String)=> s.lengthvalh= (i:Int)=> i* i"satisfy associativity" in {Prop forAll { (i:Int)=>        compose(h, compose(g, f))(i)== compose(compose(h, g), f)(i)      } must pass    }"satisfy identity" in {Prop forAll { (i:Int)=>        compose(f, id[Int])(i) mustEqual compose(id[String], f)(i)      } must pass    }  }}

OK、これによって、Category オブジェクトが圏の条件を厳密に満たすことが示されたわけだ。でも、話はこれで終わりじゃない！Scala でより一般的な圏を記述することを考えよう。

traitGenericCategory[->>[_, _]] {defid[A]:A->>Adefcompose[A,B,C](g:B->>C,f:A->>B):A->>C}

A ->> B は、->>[A,B] の別記法にすぎないことに注意しよう。この記法は、ここではマップに注目しているということを、うまい具合に反映している。

もちろん、われわれのCategory オブジェクトは、このGenericCategory をインプリメントする。

objectCategoryextendsGenericCategory[Function] {defid[A]:A=>A= a=> adefcompose[A,B,C](g:B=>C,f:A=>B):A=>C=    g compose f// This is Function.compose, not a recursive call!}

もし君が、もっといろいろな圏に興味を持っているなら、迷わずscalaz を見るべきだ。このプロジェクトで、たくさんの圏を見ることができるだろう。たとえば、部分関数の圏、モナドの圏などだ。ここでは、圏論のもう一つの重要なコンセプトについて話を進めるとしよう。

さて、圏については勉強したし、Scala でいくつかの圏を記述する方法も分かった。ここでは、圏論のもう一つの重要なコンセプトに目を向けてみよう。これは、関数プログラミングにおいても、非常に重要なものだ。2 つの圏 C1 と C2 を考える。このとき、関手（functor）F はこれら 2 つの圏の構造を保持するマッピング（structure-preserving mapping）である。

訳注：structure-preserving mapping については特に定訳はない模様。

OK。だがこれってどういう意味だ？圏と圏のマップというのは、単純に、以下のことを意味している。

• C1 上のすべての対象 A は、C2 上の対象 F(A) にマップされる。
• C1 上の2つの対象 A,B 間のすべての射 A -> B は、C2 上の2つの対象 F(A),F(B) 間の射 F(A) -> F(B) にマップされる。

圏の構造を保存するためには、このマップは恒等射と合成を保存しなきゃならない。もっと形式的に書くと、

• 　　
• 　　　where　

となる。

関手の「意味するところ」を考える前に、Scalaでコードしてみよう。前章のGenericCategory（Scala の型と、それらの間の任意のマップからなる圏）を基盤に使う。

traitGenericFunctor[->>[_, _],->>>[_, _],F[_]] {deffmap[A,B](f:A->>B):F[A]->>>F[B]}

今一度、->> 、->>> およびF はすべて型コンストラクタだ。これを見ると、必要とするものは全部揃っているようだ。型A とB は型F[A] とF[B] にマップされ、マップA ->> B はマップF[A] ->>> F[B] にマップされる。

さて、任意のマップから Scala の関数に話を移そう。すなわち、われわれが定義したCategory を関手のソースとターゲットとして選ぼう。これは、つまるところ自己関手（endfunctor）と呼ばれる、ソースとターゲットが等しい関手になる。コードは以下のようになる。

traitFunctor[F[_]]extendsGenericFunctor[Function,Function,F] {finaldeffmap[A,B](as:F[A])(f:A=>B):F[B]=    fmap(f)(as)}

注意してほしいのは、新しいfmap 関数は、単に便宜上のもので、継承されたfmap を代表するもの、ということだ。第一引数に高カインド型（後述）を使うことで、第二引数におけるAの型を推論することが可能になっている。

サンプルコードを作るために、型コンストラクタF を特定しなきゃならない。ここでは、古きよきList からはじめてみよう。

objectListFunctorextendsFunctor[List] {deffmap[A,B](f:A=>B):List[A]=>List[B]= as=>asmap f}

この object は、List 上の関数をマップできるようにしている。つまり、この関手がリストのすべての要素に関数を適用することを許すコンテナのように見える、ということを意味している。これは関手を考える上で、非常に直感的な方法だ。そしてこのことから、関数プログラミングにおいて関手が非常に重要なコンセプトであることが分かる。その証拠に、Scala ライブラリの「コレクション」をみてみよう。それらのすべてが「要素に関数をマッピングする機能（map）」を提供しているのがみてとれるだろう。

OK。どうすれば、僕らが関手を使えるかどうかを見ていこう。Functor オブジェクトをコードに追加するため、ListFunctor を内部に埋め込み、implicit オブジェクトとして使う。また、ジェネリックなfmap メソッドを追加しよう。

objectFunctor {deffmap[A,B,F[_]](as:F[A])(f:A=>B)(implicitfunctor:Functor[F]):F[B]=    functor.fmap(as)(f)implicitobjectListFunctorextendsFunctor[List] {deffmap[A,B](f:A=>B):List[A]=>List[B]=      as=>asmap f  }}

型クラスの世界へようこそ！新しいジェネリックなfmap メソッドは、追加の暗黙パラメータをとる。このパラメータは、高カインド型（higher kinded type）によってパラメタライズされたFunctor 型である。このメソッドを、Functor を指定せずに、F[A] とf だけ（高カインド型のインスタンスと関数）で呼び出した場合、コンパイラはマッチする暗黙の値を探しにいく。

訳注：高カインド型については、 @eed3si9n 氏によって翻訳された「Iterator パターンの本質」内の注釈に、詳しい解説が載っている。同記事のコメント欄でも高カインド型について議論がなされている。http://eed3si9n.com/ja/essence-of-iterator-pattern

どんな動きをするか、実際に見てみよう。

scala> import com.weiglewilczek.cats.Functor._import com.weiglewilczek.cats.Functor._scala> fmap(List(1, 2, 3))(x => x + 1)res0: List[Int] = List(2, 3, 4)

同じ結果を単にList インスタンス上のmap を呼び出すだけで得られる間は、もっと一般的なもの―――関手を定義したすべての型で動作するfmap メソッド―――を得ることができる。

ListFunctionFunctor が、関手の法則を満たすことを、まだ証明していなかった。そこで、単体テストを、以下のように書いてみた。

classListFunctorTestextendsSpecificationwithScalaCheck {importFunctor.ListFunctor._"A ListFunctor" should {"preserve identity" in {valstringID= (s:String)=> svalstringListID= (ss:List[String])=> ssProp forAll { (ss:List[String])=>        fmap(stringID)(ss)== stringListID(ss)      } must pass    }"preserve composition" in {valf= (i:Int)=> i.toStringvalg= (s:String)=> s.lengthProp forAll { (is:List[Int])=>        fmap(g compose f)(is)== (fmap(g) compose fmap(f))(is)      } must pass    }  }}

スバラシイ！さて、もう一つ例を見てみよう。Functor トレイトの型コンストラクタにOption 型を指定してやるとどうなるか？

implicitobjectOptionFunctorextendsFunctor[Option] {deffmap[A,B](f:A=>B):Option[A]=>Option[B]=    o=> o map f}

これにより、Option の中身に関数をマップすることができる（つまりは、Option のコンテキストに関数を適用すると考えることができる）。もしNone であれば、関数は適用されない。もしSome[A] であれば、関数は適用される。この「計算コンテキスト（computational context）」は、関手の別の見方ともいえる。関手は、時に関数の「持ち上げ（lifting）」と呼ばれることがある。これは、関数が通常のコンテキストから、関手のコンテキストに「持ち上げ」られるからだ。

この解釈がよりよく分かる例をコーディングしてみよう。ここでは、Function0 をFunctor トレイトの型コンストラクタに使う。

implicitobjectFunction0FunctorextendsFunctor[Function0] {deffmap[A,B](f:A=>B):Function0[A]=>Function0[B]=    a=> ()=> f(a())}

これが動作するところを見てみよう。

scala> val f = (s: String) => s.lengthf: (String) => Int = <function1>scala> val lifted = fmap(() => "abc")(f)lifted: () => Int = <function0>scala> lifted()res1: Int = 3

見ての通り、関数f は与えられたFunction0 のコンテキストに「持ち上げ」られている。すなわち、Function0 の出力が返ってきている。

このブログポストでは、圏論の二つの重要な概念、圏と関手を見てきた。もちろん、このほかにも頻繁に使われる概念はいくつかあるけれど（たとえばモナド）、とりあえずそれは置いておこう。圏論が持っている興味深い点や、重要なコンセプトのなかで、Scala に適用可能な部分や、記述に役立つ部分を紹介できたなら本望だ。僕は圏論については初心者だと思っているので、フィードバックをもらえると大変うれしい。

もし、圏論について興味があるなら、scalaz プロジェクトを参照してほしい。

図・数式は、以下のサービスを利用させていただきました。

• Google Chart Toolshttp://code.google.com/intl/ja/apis/chart/
• Cacoohttps://cacoo.com/

また、日本Scala ユーザーズグループの方々にレビューしていただきました。深謝いたします。