ともちんの Tech ブログ

Scala プログラマのための圏論入門 (1) 圏とは

Scala 圏論 関数プログラミング

はじめに

本記事は、圏論初心者が圏論について学びながら作成した、Scala プログラマのための入門書です。教科書は Bartosz Milewski 氏著の Category Theory for Programmers - Scala Edition で、構成も原則これに沿っています。

Scala をやっていて、圏論について知りたい・学ぶ土台を作りたいという方の参考になれば幸いです。

圏: 合成の本質

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

f:id:tomoki0606:20201023231515p:plain
圏のイメージ

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

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

圏の本質は合成であり、合成の本質は圏であると言われます。本記事では、射の合成について考えていきます。

関数としての射

圏は対象の集まりと射の集まりからなる。

の説明から想像がつくように、圏は抽象的な概念です。高校の授業で、集合を「ものの集まり」と習ったのを懐かしく感じます。

射について、もう少し具体的に掘り下げてみましょう。入力に対して出力を返す関数は、射の例です。ここでは、関数の合成について見ます。

対象の例として、以下の3つのクラスを考えます。

scala> case class A(value: Int)
defined class A

scala> case class B(value: Int)
defined class B

scala> case class C(value: Int)
defined class C

これらの対象の間の射として、関数 f:A => B、g: B => C を考えます。 f は A の値をインクリメントしたものを B に変換する関数で、 g は B の値を2倍したものを C に変換する関数です。

scala> val f = (a: A) => B(a.value + 1)
f: A => B = $Lambda$6756/1477788485@40987409

scala> val g = (b: B) => C(b.value * 2)
g: B => C = $Lambda$6757/1606691516@2e7629b0

scala> val a = A(1)
a: A = A(1)

scala> val b = f(a)
b: B = B(2)

scala> val c1 = g(b)
c1: C = C(4)

f の返り値を g の引数として渡すことによって、これらの関数を合成することができます。

scala> val c2 = g(f(a))
c2: C = C(4)

このような関数の合成 (composition) によって、 A の値を受け取り C を返す新しい関数を定義することができます。数学的には

$$g \circ f$$

と書きます。なお、合成された射は合成射 (composite arrow) といいます。

f:id:tomoki0606:20201023232137p:plain
射の合成

2つの関数 f: A => B、 g: B => C を合成するためには、 f の返り値の型と g の入力の型が一致する必要があります。この例の場合は B で一致しており、f の返り値を g の引数で渡すように合成することができます。一方で、 g の返り値を f の引数で渡すように合成することはできません。

scala では、関数の合成には compose を用います。

scala> g compose f
res2: A => C = scala.Function1$$Lambda$6733/1101289403@5799784c

scala> g (f(a)) == (g compose f) (a)
res1: Boolean = true

合成の性質

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

  1. 射が合成できること
  2. 射が結合律を満たすこと
  3. 任意の対象について恒等射が定義されていること（単位律）

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

射の結合律

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

1 + 2 + 3 = (1 + 2) + 3 = 1 + (2 + 3)
1 ∨ 1 ∨ 0 = (1 ∨ 1) ∨ 0 = 1 ∨ (1 ∨ 0)

などです。

これと同様のことを射の合成について考えます。まず、射の結合律の説明をするために、もう一つクラスと関数を導入します。

scala> case class D(value: Int)
defined class D

scala> val h = (c: C) => D(c.value * 10)
h: C => D = $Lambda$6758/1811383728@1df4cd10

関数 h は、 C の値を10倍したものを D に変換する関数です。

g の返り値と h の引数の型が一致するため、関数 f と g、h を合成することができます。

// val a = A(1)
scala> h(g(f(a)))
res0: D = D(40)

結合律は、射 f: A => B, g: B => C, h: C => D に対して以下が成り立つことです。

h compose g compose f == h compose (g compose f) == (h compose g) compose f

要は f と g と h の合成と、f と g の合成と h を合成したものと、g と h の合成と f を合成したものは、同じになるという性質ですね。

実際に、確かめてみましょう。

scala> (h compose g compose f) (a)
res10: D = D(40)

scala> (h compose (g compose f)) (a)
res11: D = D(40)

scala> ((h compose g) compose f) (a)
res12: D = D(40)

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

恒等射

次に、恒等射についてです。

恒等射 (identity) は、かなり噛み砕いて言うと何もしない操作を表す射です。射の合成の単位元 (unit) とも言います。つまり、ある関数 f と恒等射 id とを合成すると、その結果は f になります。

f compose id[A] == f
id[B] compose f == f

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

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

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

x + 0 = x

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

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

x * 1 = x

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

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

f2 compose f1 = id

このとき f2 は、 f1 と逆の操作をやった結果何もしない操作が得られたという意味から、 f1 の逆射 (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 compose f: A => C が定義される。
    2. 射の合成について、結合律が成り立つ。
    3. 任意の対象について、恒等射が存在する。

  • ある射 f: A => B に対して、 g compose f == id[A] かつf compose g == id[B] を満たす射 g: B => A を f の逆射と呼ぶ。

  • 射 f の逆射が存在するとき、 f は可逆であると呼ばれる。
  • 可逆な射は同型射と呼ばれる。
  • 対象 A から B への射が同型射であるとき、 A と B は同型であると呼ばれる。

参考文献