Home

Scala で圏論入門

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）とも呼ばれる。

図1 圏

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

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

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

図2 合成

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

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

gof

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

gof2

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

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

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

1fa

1fb

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

図3 恒等射

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

Scala での圏

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

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

object Category {
  def id[A]: A => A = a => a
  def compose[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 フレームワークを使うことにする。

class CategorySpec extends Specification with ScalaCheck {
  import Category._

  "A Category" should {

    val f = (i: Int) => i.toString
    val g = (s: String) => s.length
    val h = (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 でより一般的な圏を記述することを考えよう。

trait GenericCategory[->>[_, _]] {
  def id[A]: A ->> A
  def compose[A, B, C](g: B ->> C, f: A ->> B): A ->> C
}

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

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

object Category extends GenericCategory[Function] {
  def id[A]: A => A = a => a
  def compose[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 の型と、それらの間の任意のマップからなる圏）を基盤に使う。

trait GenericFunctor[->>[_, _], ->>>[_, _], F[_]] {
  def fmap[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）と呼ばれる、ソースとターゲットが等しい関手になる。コードは以下のようになる。

trait Functor[F[_]] extends GenericFunctor[Function, Function, F] {
  final def fmap[A, B](as: F[A])(f: A => B): F[B] =
    fmap(f)(as)
}

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

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

object ListFunctor extends Functor[List] {
  def fmap[A, B](f: A => B): List[A] => List[B] = as => as map f
}

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

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

object Functor {

  def fmap[A, B, F[_]](as: F[A])(f: A => B)(implicit functor: Functor[F]): F[B] =
    functor.fmap(as)(f)

  implicit object ListFunctor extends Functor[List] {
    def fmap[A, B](f: A => B): List[A] => List[B] =
      as => as map 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 が、関手の法則を満たすことを、まだ証明していなかった。そこで、単体テストを、以下のように書いてみた。

class ListFunctorTest extends Specification with ScalaCheck {
  import Functor.ListFunctor._

  "A ListFunctor" should {

    "preserve identity" in {
      val stringID = (s: String) => s
      val stringListID = (ss: List[String]) => ss
      Prop forAll { (ss: List[String]) =>
        fmap(stringID)(ss) == stringListID(ss)
      } must pass
    }

    "preserve composition" in {
      val f = (i: Int) => i.toString
      val g = (s: String) => s.length
      Prop forAll { (is: List[Int]) =>
        fmap(g compose f)(is) == (fmap(g) compose fmap(f))(is)
      } must pass
    }
  }
}

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

implicit object OptionFunctor extends Functor[Option] {
  def fmap[A, B](f: A => B): Option[A] => Option[B] =
    o => o map f
}

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

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

implicit object Function0Functor extends Functor[Function0] {
  def fmap[A, B](f: A => B): Function0[A] => Function0[B] =
    a => () => f(a())
}

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

scala> val f = (s: String) => s.length
f: (String) => Int = <function1>

scala> val lifted = fmap(() => "abc")(f)
lifted: () => Int = <function0>

scala> lifted()
res1: Int = 3

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

終わりに

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

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

謝辞

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

Google Chart Tools http://code.google.com/intl/ja/apis/chart/
Cacoo https://cacoo.com/

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

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Home

Scala で圏論入門

圏とは何か？

Scala での圏

関手

終わりに

謝辞

Clone this wiki locally