1. 圏とは

圏は対象 (object) の集まりと、対象から対象へのなんらかの操作を表す射 (arrow, morphism) の集まりからなります。

例えば、Scala を圏として考えてみると、対象は Int、 String、 List[A] などの型を表し，射は f: Int -> String のように関数を表します。

他にも、対象を自然数の集まり {0, 1, 2, ..., n, ...} のみと考えてみると、射は自然数の間の操作を表します。射の例として加算、乗算、減算、除算や、自然数を+1した値を返すインクリメンタなどがあります。

圏の例は3章で紹介します。本章では、圏とは何かについて学んでいきます。圏の構成要素 - 対象、射 - と、圏が満たすべき性質 - 射の合成、合成の結合律、恒等射 - について見ていきます。

射とは、圏の対象から対象へのなんらかの操作を表すようなものです。例えば、自然数を対象とすれば、自然数の間の操作、つまり加算や減算のような操作が射とみなせます。プログラミングにおいては、ある型をある型に変換する関数は射とみなせます。

1.1.1 射の例: 四則演算

射の例として、自然数間の四則演算を考えてみましょう。

対象 1 から対象 2 への射としては「1を足す操作」「2倍する操作」などがあり、対象 2 から対象 1 への射としては「1を引く操作」「2で割る操作」などがありますね。それぞれを add1, double, minus1, div2 と命名すれば、以下のように表現できます。

add1:   1 -> 2
double: 1 -> 2
minus1: 2 -> 1
div2:   2 -> 1

1.1.2 射の例: Scala の関数

Scala の関数も射とみなせます。

数をインクリメントする（つまり1を足す）関数 increment: Int => Int は、型 Int から型 Int への関数です。圏論の言葉にすると、Int 型という対象から Int 型という対象への射です。

def increment: Int => Int = _ + 1

increment(1)
// res0: Int = 2
increment(3)
// res1: Int = 4

1.1.3 始域と終域

射を議論する際によく使われる概念を定義しておきます。

射はある対象からある対象への操作を表しますが、それは対象から対象への矢印のようなものと考えられます。

f: a -> b

このとき、矢印が出ている方の対象のことを始域あるいは域 (domain) と呼び、矢印の先の対象のことを終域あるいは余域 (codomain) と呼びます。個人的には始集合・終集合との関連で始域と終域の方が好きです。

しばしば、射 f の始域のことを dom(f) 、終域のことを cod(f) と表します。

dom(f) = a, cod(f) = b

1.2 射の合成

圏に関する最も重要な性質は、射の合成です。圏の本質は合成であり、合成の本質は圏であると言われたりします。射の合成について考えてみましょう。

入力に対して出力を返す関数は、射の例です。型 A の値を受け取って B の値を返す関数 f と、型 B の値を受け取って C の値を返す関数 g があるとしましょう。f の返り値を g に渡すことによって、関数を合成できますね。そうすると、型 A から C への新しい関数を定義できます。

例えば、以下のような String から Int への関数 length と、Int から Boolean への関数 isEven を合成してみます。

def length: String => Int = _.length
def isEven: Int => Boolean = _ % 2 == 0

length("abcdefg")
// res2: Int = 7
isEven(3)
// res3: Boolean = false
isEven(8)
// res4: Boolean = true

length は文字列の長さを返す関数で、 isEven は数が偶数かどうかを判定する関数です。Scala において、関数の合成は compose や andThen メソッドで行われます。

def isLengthEven1: String => Boolean = isEven compose length
// or
def isLengthEven2: String => Boolean = length andThen isEven  
// or
def isLengthEven3: String => Boolean = str => isEven(length(str))

isLengthEven1("abcdefg")
// res5: Boolean = false
isLengthEven2("abcdefg")
// res6: Boolean = false
isLengthEven3("abcdefg")
// res7: Boolean = false
val len = length("abcdefg")
// len: Int = 7
isEven(len)
// res8: Boolean = false

この isLengthEven* 関数は、文字列に length 関数を適用したあと、その返り値に isEven 関数を適用するような新しい関数です。合成によって作られた関数は、しばしば合成関数と呼ばれます。

このように、射の例である関数は合成することができます。一般に、圏における射も合成することができます。ただし、2つの射の合成の結果は一意でなければなりません。すなわち、射の合成は以下のように定義されます。

2つの射 f と g について、cod(f) = dom(g) であれば dom(f) から cod(g) への一意の射が存在します。そのような射を f と g の合成 (composition) と呼び、g . f と書きます。

1.3 合成の性質

圏は対象の集まりと射の集まりからなるものと説明しましたが、圏にはもう少し厳密な定義があります。それは

射が合成できること
射が結合律を満たすこと
恒等射が定義されていること

です。合成については 1.2 節で見ましたので、ここでは 2 と 3 について説明していきます。

1.3.1 射の結合律

まずは、射の結合律についてです。結合律と言うと、足し算や掛け算の結合律や、論理演算の結合律が思い出されるのではないでしょうか。例えば

1 + 2 + 3 = (1 + 2) + 3 = 1 + (2 + 3)

1 ∨ 1 ∨ 0 = (1 ∨ 1) ∨ 0 = 1 ∨ (1 ∨ 0)

などです。

全くこの通りというわけではないのですが、射の結合律とは、以下のように定義されます。

合成可能な3つの射 f, g, h があるとき、以下が成り立つならば射は結合律を満たすと言います。

h . (g . f) = (h . g) . f = h . g. f

結合律は、Scala で書くと以下のようになります（=== は Hamcat で用意している「等しくあるべきものを主張するための文法」です）。

def f[A, B]: A => B = ???
def g[B, C]: B => C = ???
def h[C, D]: C => D = ???

import hamcat.util._
def associativeLaw1 = ( h compose (g compose  f)) === ((h compose g) compose f)
def associativeLaw2 = ( h compose (g compose  f)) === ( h compose g  compose f)
def associativeLaw3 = ((h compose  g) compose f)  === ( h compose g  compose f)

具体的な関数で確かめてみましょう。

以下の3つの関数を考えます。

def negate: Boolean => Boolean = b => !b

def length: String => Int = _.length
def isEven: Int => Boolean = _ % 2 == 0

これらの関数を合成して、"abcdefg" という文字列を入力してみます。

( negate compose  isEven  compose length)  ("abcdefg")
// res9: Boolean = true
((negate compose  isEven) compose length)  ("abcdefg")
// res10: Boolean = true
( negate compose (isEven  compose length)) ("abcdefg")
// res11: Boolean = true

すべての計算の結果は等しく、確かに結合律は成り立っています。

1.3.2 恒等射

次に、恒等射についてです。あるシステムが圏であるためには、任意の対象について恒等射が存在しなければいけません。この条件を単位律と呼びます。

恒等射 (identity) は、他の射と合成するとその射そのものになるような射です。射の合成の単位元 (unit) とも言います。つまり、ある関数 f と恒等射 id とを合成すると、その結果は f になります。

f . id[A] = f
id[B] . f = f

Scala:

import hamcat.data.identity

def identityLaw1[A] = (f compose identity[A]) === f
def identityLaw2[B] = (identity[B] compose f) === f

要は、入力と出力が等しい関数です。かなり噛み砕いて言うと、何もしない操作とも捉えることができるかもしれません。 Hamcat において、恒等射を表す identity は以下のように定義されています。

/** Identity morphism for scala category */
def identity[A]: A => A = a => a

何もしない操作が何に使えるのか、わかりづらいですよね。何もしないのなら使う場面もわからないし、定義になんて組み込む必要ないじゃん、と思うかもしれません。

では、何もしない操作についてもう少し考えてみましょう。

「何もしない」で最も典型的なものは 0 という数ではないでしょうか。0 は、加算という射における単位元です。これは、以下が成り立つことを意味します。

x + 0 = x

これは当然のように成り立ちますよね。

他に、乗算という射における単位元は 1 です。これは、以下が成り立つことを意味します。

x * 1 = x

単位元についてもう少し掘り下げてみます。

ある操作をしたあとにもう一つ操作をすると、単位元が得られる場合を考えます。すなわち、射 f と射 g を合成すると恒等射 id が得られたとします。

g . f = id

このとき g は、 f と逆の操作をやった結果何もしない操作が得られたという意味から、 f の逆射 (inverse) であるといわれます。

では、加算と乗算の逆射は何でしょうか。加算の単位元は 0、乗算の単位元は 1 なので、ある操作をしたあとにもう一つ操作をすると単位元が得られる、とは以下の状況を意味します。

x + (- x) = 0
x * (1 / x) = 1

加算 + x に対して - x すると単位元 0 が得られ、乗算 * x に対して * 1/x すると単位元 1 が得られています。これらはそれぞれ減算、除算です。すなわち、加算の逆射は減算、乗算の逆射は除算ですね。

以上の通り、何もしない操作である恒等射は、ある操作とは逆の操作を行う逆射の存在を扱うのにも必要な概念です。

対象 A から B への射に逆射が存在するとき、相互変換可能であるという意味で A と B は同型 (isomorphic) であると言われます。また、射 f の逆射が存在することを f は可逆 (invertible) であるといい、可逆な射を同型射 (isomorphism) と呼びます。

まとめ

圏の定義: 圏は対象の集まりと射の集まりから構成され、以下の条件を満たすシステムである。
1. 射 f: a -> b と射 g: b -> c に対して、合成射 g . f: a -> c が定義される。Scala においては compose メソッド。
2. 射の合成について、結合律が成り立つ。
3. 任意の対象について、恒等射が存在する。
ある射 f: a -> b に対して、 g . f = id[A] かつf . g = id[B] を満たす射 g: b -> a を f の逆射と呼ぶ。
射 f の逆射が存在するとき、 f は可逆であると呼ばれる。
可逆な射は同型射と呼ばれる。
対象 a から b への射が同型射であるとき、 a と b は同型であると呼ばれる。

1章圏とは