プログラマのための圏論 Category Theory for Programmerを読んでいく

はじめに

これから、Category Theory for Programmer(プログラマーのための圏論)を読んでいこうと思う。
Scalaで適宜実装しながら、纏めや自分の疑問点とか調べたことを描いていければと。 (まさかりやご指摘、大歓迎です)
また、本では扱っていない線形代数グラフ理論の例やScalaのライブラリCatsのこともちょくちょく書いていく予定。
(というか、CatsがあるのでScalaを使うことにした)

ここは各章と参考文献の纏め。

各章へのリンク

Part0: Scalaの基本的な文法

Scalaコードの読み方

Part1: 圏論の基本的な言葉・概念を学ぶ

このパートでは、圏論で使用される基本的な言葉や概念を学んでいく。
圏は対象と射で構成されており、
射は対象同士を繋ぎ、
関手は圏同士を繋ぎ、
自然変換は関手同士を繋ぐ。
このパートを読むと、射・関手・自然変換へ進むにつれて抽象度のレベルが1段ずつ上がっていくことを理解できるとおもふ。
(この過程で、高階関数の背後にあるアイデアを目にする)

Ch1 Category: The Essence of Composition 合成の本質
Ch2 Types and Functions 型と関数
[Ch3 Categories Great and Small 大きい圏・小さい圏]
Ch4 Kleisli Categories クライスリ圏
[Ch5 Products and Coproducts 積と余積]
[Ch6 Simple Algebraic Data Types 代数的データ構造]
[Ch7 Functors]
[Ch8 Functoriality]
[Ch9 Function Types]
[Ch10 Natural Transformations]
[ChXX Curry-Howard Isomorphism]

全体の参考文献

プログラマのための圏論 Ch4 Kleisli Categoryを読んでいく

今回は四章: 「クライスリ圏」を読んでいく。
この章では、以下の項目を学ぶ。

  • Writer圏
  • クライスリ圏

章の名前はクライスリ圏だが、ほとんどの言葉はWriter圏に尽くされている。
クライスリ圏は後の章で深く扱う。

注意:
本来、この章で扱うクライスリ圏を学ぶにはまだ言葉が足りないため、正式な定義はまだ現れない。

イントロ

この章は、Kleisli(クライスリ)圏という圏について考えていく。
まずは、なぜこの圏を考えるかということを先に提示しておく。
私達はこれまでの章で 型と純粋関数を圏で表現(モデル化)する方法を考えてきた。
では、副作用のある関数を表現する方法はあるのだろうか?
答えはYesである。

ここで、例を考えてみよう。
実行とともにログを取る関数を作成したいとする。
命令型プログラミングだとこんな感じに書けるんじゃないんだろうか。

// 実装①
var logger = ""
def negate(b: Boolean) = {
    logger += "Not so! " // not pure!
    !b
}

ただ、このプログラムには副作用が存在している...。
じゃあ、副作用を無くすために、loggerを引数で渡すことを考える。

// 実装②
def negate(b: Boolean, logger: String) = (!b, logger + "Not so!")

たし蟹、この実装だと副作用がなくなった。
ただ、この実装だとnegate関数が本来必要としないlogger引数を取ることになってしまう。(negate関数が全体のログを知ってしまう事もイケてない) では、副作用を持たず、logger引数が必要ない実装を考えてみる。

// 実装③
def negate(b: Booelan) = (!b, "Not so!")

おぉ、これはイイ感じの関数じゃないだろうか。...ただ、この関数は実装①②と違って、f ∘ gのような単純な合成ができない。 何故なら、関数の入力と出力の形式が異なるからだ。
ここで、単純な合成と言った事に注意してほしい。何故なら、関数同士の合成規則は他にも考えられるからだ。例えば、今回の場合だと以下のような関数を作れば、実装③の形式の関数を合成(?)することができる。

// 実装④
def process(b: Boolean)  = {
    val p1 = negate(b)
    val p2 = negate(p1._1)
    (p2, p1._1 + p2._1)
}

これで、それぞれの関数は全体のログを気にすること無く、全体の処理を書くことができた。
ただ、このprocess関数みたいなのを毎回書くのは少し面倒だ。
process関数が表している関数の合成規則を抽象化出来ないだろうか?
合成則は圏論の重要な構成要素の一つなので、問題を圏論の視点から考えることから始めよう。

4.1 The Writer Category & 4.2 Writer in Scala

この項目では、Writer Category(Writer圏)について考えていく。
Writer圏は、イントロのように、関数の出力にログなどを付与したものを射として考えた圏だ。

まず、圏の定義を復習しておこう。(ch1読んでみた から引用)

定義: 圏 Category
圏Cは以下の構成物を持つ
1. 対象: 対象の集まりをobj(C)と書く。
2. 射: 対象の関係を表す。 対象aと対象bの間の射の集合をHom(a, b)やC(a , b)と書く。
3. 合成: 射の合成規則。射f, gが合成可能な場合、g ∘ fも射に含まれる。
射は以下の性質を持つ
1. 結合律: f: a → b, g: b → c, h: c → d が存在するなら、それらに関して h ∘ (g ∘ f) = (h ∘ g) ∘ f が成り立つ。
2. 単位律: 1つ1つの対象xに対して、以下の性質を持つ射が存在する。(これは、xの 恒等射**と呼ばれる)
- 任意の射 f: a -> x及び g: x -> bに対して、
- idx ∘ f = f かつ g ∘ idx = g
定義終

圏は、対象と射、単位射、合成規則によって定義されるのだった。
さぁ、Writer圏を作っていこう。
まず、対象と射を以下のように設定する。
(イントロの実装③の形式の関数が射になっている)

対象 単位射 合成則
データ型 関数: A -> Writer[B]
AとBは任意のデータ型
? ?

ここで、Writer[B]を以下のように定義した。

type Writer[B] = (B, String) 

次に合成規則だ。通常の関数合成 g∘f と区別するために、別の記法を用いて、Writer圏の射 f: A -> Writer[B]とg: B -> Writer[C]の合成をf >=> g と書く。

// 実装④に相当  
def >=>[A, B, C](f: A => Writer[B], g: B => Writer[C]): A => Writer[C] = a => {
    val (b, s1) = f(a)
    val (c, s2) = g(b)
    (c, s1 + s2)
}
対象 単位射 合成則
データ型 関数: A -> Writer[B]
AとBは任意のデータ型
? f>=>g: (A -> Writer[B]) -> (B -> Writer[C]) -> (A -> Writer[C])

結合律は、Scalaの関数合成が結合律を満たすこと、String型の結合が結合律を満たすことから満たされる。
最後に、単位射を以下のように作成する。

def pure[A](a: A): Writer[A] = (a, "")

これで、Writer圏が作成できた。

対象 単位射 合成則
データ型 関数: A -> Writer[B]
AとBは任意のデータ型
pure: A -> Writer[A] f>=>g: (A -> Writer[B]) -> (B -> Writer[C]) -> (A -> Writer[C])

補足: 単位射って入力と出力が同じ型じゃなくていいの?
私が最初、pure関数を見たとき、「あれ、単位射って入力と出力が同じ型じゃなくていいの?とかなり混乱しました。

しかし、単位射に対して要求している性質は、任意の射 f: A -> Writer[B] 及び g: B -> Writer[A] に対して、id_a >=> f = f かつ g >=> id_b = g を満たすことです。
id_a: A -> Aであることは要求していません。(たまたまそうなる例をたくさん見てきただけです)
もしid_a: A -> A だったら、そもそも結合ができません。

また、 AからBへの射として A -> Writer[B]の関数を対応させることも全く問題ありません。
射と関数のドメイン・コドメインが一致する必要はなく、圏の合成則などの他の構成物との整合性が取れていればOKです。

scalaでの実行例を以下に記載する。

object WriterExample {

  // a は対象  
  class Writer[A](val a: A, val log: String) {
    // 合成
    // 本文で定義した方法とは異なることに注意。  
   // Writer[A]に A => Writer[B]を適用する方法を定義することで、間接的に合成則を定義している。  
   // この場合、定義されるf, gの合成は a => f(a) >=> g と書ける。  
    def >=>[B](f: A => Writer[B]):Writer[B] = {
      val w_b = f(a)
      new Writer(w_b.a, log + w_b.log)
    }

    // println用に定義
    override def toString: String =
      a.toString + "\n" + "="*10 + "\n with log \n" + log + "\n" + "="*10
  }
    // 単位射
  def pure[A](a: A) = new Writer(a, log="")

  def main(args: Array[String]): Unit = {
    val one = 1

    val twoTimesWithLog = (i: Int) => new Writer(i*2, "2 times\n")
    val fourTimesWithLog = (i: Int) => new Writer(i*4, "4 times\n")
    val toStringFormatWithLog =
      (i: Int) => new Writer("the number is " + i.toString, "output")

    val oneWithLog = pure(one)

    println(
      oneWithLog
        >=> twoTimesWithLog
        >=> fourTimesWithLog
        >=> toStringFormatWithLog
    )
    /*
    結果:
    the number is 8
    ==========
     with log 
    2 times
    4 times
    output
    ==========
    */
  }
}

4.3 Kleisli Categories

さて、ようやく章題のクライスリ圏の話が出てきた。

残念ながら「まだ」クライスリ圏の定義は(言葉が足りないので)述べられないが、イメージとしては以下のように言える。

クライスリ圏(Kleisli Category)のイメージ

対象: 色々 (例: Hasellのデータ型, 自然数, ...)

射: 対象Aから「対象Bに何らかの文脈を足したもの」への関数

(ここでは、「文脈」を、なんらかの情報の付与を意味するものとして使用している。 例えばOption, List, Tuple等だ)

合成規則: 圏の定義を満たすように決める

今までの〇〇圏は基本的に対象・射・合成則が具体的に決まっていたが、今回のKleisli圏の様に、特定の条件を満たす圏を指すことも多い。
プログラムの副作用をクライスリ圏の「文脈」として捉えることで、圏論の世界に押し込んでいる事がわかる。 Writer圏は、ログを文脈と捉えることで上のイメージと合致することから、クライスリ圏の1つである。

4.A CatsでWriter圏を使う

ScalaにはCatsという関数型プログラミングの抽象化を提供するライブラリが存在する。
WriterはCatsで実装されているため、それの使用例を確認していこう。 紹介程度しか私には書けないので、詳しく知りたい方はCatsの公式ドキュメントを参照してほしい。

例として、以下のような操作にログを付加することを考える。

val one = 1

// 関数(射)の定義
val times2: Int => Int = x => x*2
val times5: Int => Int = x => x*5

// 通常の合成
val times10 = compose(times2)(times5)(_)
println(times10(one)) // 10

ログの付加は、CatsのWriter型クラスを使って以下のように書ける。

import cats.data.Writer
// create writer object
val oneWithLog: Writer[List[String], Int] = Writer(List("initial value"), one)

Writer圏の射は以下のように書ける。

// Writer圏の射に変換
val initialLog = Writer(List("initial value"), identity[Int](_)) // memo: Explicit conversion
val times2WithLog = Writer(List("times 2"), times2)
val times5WithLog = Writer(List("times 5"), times5)

// 関数の適用
val oneWithLog = initialLog.map(_.apply(one))
println(oneWithLog) // WriterT((List(initial value),1))
val twoWithLog = times2WithLog.map(_.apply(one))
println(twoWithLog) // WriterT((List(times 2),2))

Writer圏の合成は以下のように書ける。

// Writer圏の合成
val times10WithLog: Int => Writer[List[String], Int] =
  x => initialLog.map(_.apply(x))
        .ap(times2WithLog)
        .ap(times5WithLog)
println(times10WithLog)
println(times10WithLog(one)) // WriterT((List(times 5, times 2, initial value),10))

// 別のやり方 Logの順番が逆になっている
val tenWithLog = for {
  init <- initialLog
  times2 <- times2WithLog
  times5 <- times5WithLog
} yield (times5 >>> times2 >>> init)(one)
println(tenWithLog) // WriterT((List(initial value, times 2, times 5),10))

4.4 Challenge 練習問題

引数のすべての可能な値に対して定義されていない関数は、部分関数と呼ばれます。
これは数学的な意味での関数ではないので、標準的な圏の型には合いません。
しかし、Option型を返す関数で表現することはできます。
Option型はCh8で扱うので詳細はその時に譲りますが、この型を一言でいうと、「値がない時を表現する事ができる型」です。
値がない場合はNoneを返し、ある場合はSome(値)となります。

例えば、辞書から値を取り出す時に、指定されたキーが存在しない場合はそれを表すNoneを返すような実装は以下のように書けます。

// Optionの例
val dict = Map("key" -> 12)
println("get value of key: %s".format(dict.get("key")))
// output: get value of key: Some(12)

println("get value of notExistKey: %s".format(dict.get("notExistKey")))
// output: get value of notExistKey: None

さて、そんなOption型を使用して、平方根を取る関数を以下のように書けます。

def safe_root(x: Double): Option[Double] = {
  if (x >= 0) {
    return Some(math.sqrt(x))
  } else {
    return None
  }
}
println(safe_root(4)) // Some(2.0)
println(safe_root(-4)) // None
  1. 部分関数のクライスリ圏を作ってください。(合成と単位射を定義してください)

Ans.
最初にあったように、部分関数はA => Option[B]の型で表せるので、この圏の対象はデータ型で射はA => Option[B]の関数とする。
射の例を1つあげる。

// 入力の逆数を返す関数 0の場合は結果を返さない
def safe_reciprocal(a: Double): Option[Double] = {
  if (a != 0) {
    return Some(1/a)
  } else {
    return None
  }
}

println(safe_reciprocal(5)) // 0.2
println(safe_reciprocal(0)) // None

次に合成則について検討する。
部分関数は「結果を返す」場合と、「結果を返さない(Noneを返す」二つの場合がある。
2つの部分関数を続けて適用した場合も、このどちらかだ。
この場合、合成された関数が結果を返すのは「2つの部分関数が両方結果を返した場合」に限る。
(何故なら、1つ目の部分関数が結果を返さなかった場合、2つ目の関数は正しい入力が得られないからだ。)
この考えを合成則にすると、Scalaで以下のように書ける。

// 合成則
// 第一の関数の出力を oaとしている
// この定義の仕方に関しては、2項の最後の例を参照
def >=>[A, B](f: A => Option[B])(oa: Option[A]):Option[B] = oa match {
  case Some(a) => f(a)
  case _ => None
}

// 例
println(>=>(safe_reciprocal)
                 (safe_root(5)))
// output Some(0.4472135954999579)

最後に単位射を以下のように作ったら、部分関数のクライスリ圏ができる。

// 単位射
def optionIdentity[A](a: A):Option[A] = Some(a)
println(optionIdentity(1)) // 1

// 合成則と組み合わせる
val safe_root_reciprocal:Int => Option[Double] = x =>
    >=>(safe_root)(
    >=>(safe_reciprocal)(
        optionIdentity(
        x)))

println(safe_root_reciprocal(4)) // 0.5
println(safe_root_reciprocal(0)) // None
println(safe_root_reciprocal(-4)) // None
  1. 入力が0以外の場合に逆数を返すsafe_reciprocal関数を作成してください。

Ans.
問題1で実装している。

  1. sqrt(1/x)を入力が正しい場合にのみ計算するsafe_root_reciprocalを実装してください。

Ans.
問題1で実装している。

おしまい!

プログラマのための圏論: Ch2 Types and Functionsを読んでいく

今回は二章: 「型と関数」を読んでいく。 この章では、以下の事を学ぶ。
- データ型とは何か
- プログラムの圏とSet圏のアナロジー

イントロ

プログラムにおいて、「データ型」と「関数」は非常に重要な役割を果たす。
関数は、データ型からデータ型への変換である。 ではデータ型とは何なのか、なぜ必要なのかをこの章では書いてある。

2.1 Who Needs Types? 型が必要なのはどなた?

静的型付けと動的型付けの話が書いてある。
ここら辺の話はネット上にいくらでも落ちてるので省略。

2.2 Types Are About Composability 型は合成に関係している

Ch1 の最後でも話したが、圏論の基本的な概念の中で一番大事なのは「射とその合成」だ。
圏ごとに射の合成方法は異なり、任意の射が合成できるわけではない。
(特に、一方の射のコドメインが次の射のドメインに一致していることを要求する場合が多い)
実際、Ch1 で定義したプログラムの圏では、2つの射が合成できるのは一方の射のコドメインが次の射のドメインに一致している場合であり、
そしてドメイン・コドメインはデータ型を使って表現されていた。
データ型は、射(関数)の結合にも大きな関わりを持っているのである。

2.3 What Are Types? 型とは何か?

さて、型とは何なんだろうか。 直感的には、「値の集合」のように考えられる。
例えば、Boolean 型は true と false の集合と考えられるし、Int 型は{2147483648, 2147483647, ...}の集合と考えられる。
集合は要素数が有限のもの(e.g. Char)と要素数が無限のもの(e.g. String)がある。 ということは、プログラムの圏について考えるときに、集合の圏があればそれのアナロジーが役に立ちそうだ。

補足: 型を集合と同一視することに関しては、すこしめんどくさいことがあるらしいが、一旦ここでは置いておく。
(定義が循環しているような多層関数と、すべての集合を含む集合が得られないこととかが問題ならしい。よくわからん)

まず、Set圏を導入する。Set 圏 は以下のように定義される。

定義: Set圏
1. 対象: 集合
2. 射: f: a -> b として 集合 a が定義域で集合 b が値域の関数
3. 単位射: 恒等関数 f(x) = x
4. 合成: 関数合成
定義終

Set は対象が集合であり、射が対象の各要素にどう作用するかを考えられるので、直感が湧きやすい。
(例えば、単位射は各要素をそのまま出力する射だと考えられる)
もちろん、最終的には対象の中の要素は忘れて、圏論の言葉である対象と射だけで表現するが、概念の理解には対象の中の要素を明示的に考えらえる Set が非常に役に立つ。

さて、理想では Haskell のデータ型が集合で Haskell の関数(つまり純粋関数)が集合の間の数学関数であることなんだけど、1 つ問題がある。 数学関数は必ず終了するが、プログラムの関数は有限のステップで終わらない可能性があることだ。
そして、我々は関数が有限のステップで終了するかを判定することができない。(有名な停止問題らしい)

警告: 私自身ここの話はかなり怪しい.

そこで、偉大なる CS 学者達はbottom(⊥)というものを考案した。
この ⊥ というは、non-terminating computation に相当する。
すると、プログラムで書かれたf: Boolean => Booleanという関数は「true,false, ⊥ のいずれかの値を返す」と考えられる。
ここで、⊥ は f(bool)が二度と終了しない場合を表し、任意のデータ型の要素とする。(関数がどんな型を返すものであれ、有限のステップで終わらない可能性があるからだ)

しかも、一度 bottom を型システムの一部として受け入れると、全てのランタイムエラーを bottom として扱い、関数に bottom を明示的に返すのがすごい便利らしい。
scala で bottom は??? *1 と表現される。

val f: Boolean => Boolean = (x: Boolean) => ???

⊥ は任意の型に含まれるので、これもモチロン OK.

def f: Boolean => Boolaen = ???

ここで、後のために用語の定義をしておこう。

bottom を返さない関数 全域関数(Total function)
bottom を返す可能性のある関数 部分関数(Partial function)

余談:
詳しい話はまだわからないが、Hask は圏じゃない(?)という議論もあるらしい

(ぶっちゃけ undifined と Set,Hask あたりの議論がよく分かっていない。Set の中に undifined が入っていると考えればよいのでは・・・?)

そんなわけで、⊥ の存在を除いてプログラムの圏は Set 圏は非常に似通っていることがわかった。
アナロジーの対応は、以下のようにとる。

圏の構成物 Set 圏 プログラムの圏
対象 集合 (集合の中には更に要素が存在する) データ型 (データ型の中には更に値が存在する。 ⊥ の扱いは考えない。)
数学関数 プログラムの関数 (停止しない関数や ⊥ の扱いは考えない。)
単位射 恒等関数 恒等関数
合成 関数合成 関数合成

2.4 Why Do We Need a Mathematical Model? 数学的モデルが必要な理由

ホゲホゲ!

2.5 Pure and Dirty Functions きれいな関数・汚い関数

純粋関数の話
副作用のない関数は理解しやすいよねという話。

2.6 Examples of Types 型の例

データ型の例を紹介している。
簡単なものしか紹介していないので省略。

2.7 Challenge 練習問題

参考
- https://github.com/awalterschulze/category-theory-for-programmers-challenges
- http://danshiebler.com/2018-11-10-category-solutions/

  1. 好きな言語で高階関数(または関数オブジェクト)を定義してください。
    この関数は純粋な関数 f を引数にとり、元の関数を引数ごとに一度だけ呼び出し、その結果を内部に保存します。
    その後同じ引数で呼び出されるたびにその保存された結果を返すという点を除いては、ほとんど f と同じように振る舞う関数を返します。
    (このことを、関数をメモ化するといいます。)

Ans.
HashMap を使用して高階関数を作成する。
最初の f_m の実行以外は一瞬で結果が帰ってくる。

import scala.collection.mutable.HashMap
def memorise[A, B](f: A => B):A => B = {
    val map = HashMap[A, B]()
    def inner(a: A): B = {
     if (map.contains(a)) return map(a)
     val value = f(a)
     map.update(a, value)
     value
     }
    inner
  }
val f_m = memorise((a:Int) => {
    Thread.sleep(3000)
    a*2
})
println("start")
(1 to 10).foreach(_ => println(f_m(3)))
  1. 乱数を生成するために普段使っている標準ライブラリの関数をメモ化してみてください。うまくいくでしょうか?

Ans.
うまくいかない。seed が固定されているから。

val r = new scala.util.Random(34)
val r_m = memorise((_: Unit) => {Thread.sleep(100); r.nextInt})
(1 to 10).foreach(_ => println(r_m()))
  1. ほとんどの乱数発生器はシードで初期化することができます。シードを受け取り、そのシードを持つ乱数発生器を呼び出し、その結果を返す関数を実装します。
    その関数をメモ化してください。うまくいくでしょうか?

Ans.
うまくいく。seed を随時与えるようにする。

val r = new Random()
    val r_m = memorise((i: Int) => {Thread.sleep(100); r.nextInt(i)})
(1 to 10).foreach(i => println(r_m(i)))
(1 to 10).foreach(i => println(r_m(i))) // 2回目の結果は1回目の実行結果と同じ&すぐ表示される
  1. Boolean -> Boolean 型の関数は何種類ありますか?全部実装してください。(注: 入力と出力が全ておなじになる関数は全て一つとみなす)

Ans. 22=4 つある。

val f1 = (a: Boolean) => if (a) true else false
val f2 = (a: Boolean) => if (!a) true else false
val f3 = (a: Boolean) => if (a) true else true
val f4 = (a: Boolean) => if (a) false else false
  1. Void, () (unit) と Bool の型のみを持つカテゴリの図を描きます。矢印には関数名のラベルを付けます。
    TODO: 後でお絵描きする

おしまい!

*1: ???の定義は、??? : Nothing = throw new NotImplementedErrorらしい

プログラマのための圏論: Ch1 Category: The Essence of Compositionを読んでいく

今回は一章: 「圏: 合成の本質」を読んでいく。
この章では、圏の定義を学ぶ。

イントロ

圏論は圏を扱う分野だ。
では、圏とはどのようなものなのか?
ざっくりと言うと、 圏とは

矢印で点同士を繋げたもの

と表現できる。
矢印は「射(morphism)」、点は「対象(object)」と呼ばれる。

f:id:sereronnrot:20201025023910p:plain

ただ、点と矢印が繋がっていればすべて圏なのかというと、そうではない。
圏には、満たすべき結合に関する法則が存在する。
これもざっくり言うと、

矢印Aと矢印Bが結合可能な場合、矢印Aと矢印Bを結合した矢印Cも存在する

みたいに表現できる。
この結合に関する法則はとても重要ならしい。
なお、ここで「結合方法」という言葉が現れているが、この結合方法は圏によって異なり、我々が設定する必要がある。

まずは「射」とは何かという部分を確認した後、圏の満たすべき条件を学び、最後に圏の定義を確認していこう。

1.1 Arrow as Function 関数としての射

イントロでは圏を「矢印で点同士を繋げたもの」と言った。
矢印(射)の意味は圏によって異なるが、射は対象同士の何らかの関係にあることを示しているという点では共通だ。
言い換えると、対象aと対象bの間に射fがある場合、aとbの間にfで表される関係があると言える。

さて、ここまでかなり抽象的な話をしてきたので、具体的な例を考えていく。
プログラマのための圏論ということで、以下のような例を考えてみよう。
表1

圏の言葉 置き換え
純粋な関数 String.toInt ex "14".toInt -> 14
対象 データ型 String, Int, List[Int]

以降は対象Aから対象Bからの射f を、f:: A -> Bと記載する。 この例では、射f:: a -> bの存在は「対象aを入力として関数fを適用した時に対象bが出力される」「引数がaで出力型がbの関数fが存在する」といったことを意味すると考えられる。

この圏を詳しく見てみよう。
例えば、図1の中にあるものが定義されている場合に、
対象A, B, Cを其々データ型とみなし、
射f, gを以下のような形の関数とみなす。

  • f: A => B
  • g: B => C

図1
f:id:sereronnrot:20201115192022j:plain

これは圏だろうか?
まだ足りない概念がある。
イントロでも触れたように、圏には射の結合方法が定義されていないといけない。

そんなわけで、今考えた射の定義に沿うような射の結合方法を設定しよう。
圏の中の合成可能な射の合成は、常に圏の中に存在していないといけないため、 この条件を満たす結合方法を考える必要がある。
今は射を関数と考えているので、この条件を満たすような自然な関数の結合方法は例えば以下のようなものだろう。

  • f の出口とg の入り口が同じ時(つまり f: ? => A, g: A => ?)、「f を適用した後g を適用すること」を「f とg の合成した関数を適用すること」とする

このルールを採用してみよう。
Scalaでは、f とg を合成した関数は以下のように書ける。

def compose[A, B, C](f: A => B, g: B => C)(a:   A):C = g(f(a))

射の合成と関数の合成は共に、数学の言葉では、g ∘ fと書く。
今後、定義や定理を記述する際には数学の記号も使用するので注意してほしい。(後から頑張って統一するかも)

これで、一部確認していない条件や構成物があるが、大体圏っぽいものはできた。
最後に、今作った圏(っぽいもの)の具体例を作ってみよう。

val f: Int => Double = a => a + 0.1             
val g: Double => String = b => "number is " +   b.toString
val g_after_f = (g compose f)                   
                                                
val result = g_after_f(12)                      
val input = 12                                  
println(f"input: $input output: $result") # in  put: 12 output: number is 12.1

図解(左: 抽象 右: 具体)
f:id:sereronnrot:20201025023941p:plain

 

1.2 Properties of Composition 合成の性質

圏が満たすべき性質は2つある。(2つとも射の合成が関わっている)

  1. 結合律: f, g, hがそれぞれ合成可能なら、
    それらに関して h ∘ (g ∘ f) = (h ∘ g) ∘ f が成り立つ。
  2. 単位律: 1つ1つの対象xに対して、以下の性質を持つ射が存在し、idxと書く。(これは、xの恒等射と呼ばれる)  
      - 任意の射 f: a -> x及び g: x -> bに対して、idx ∘ f = f かつ g ∘ idx = g

この項では、この2つの性質を詳しく見ていく。

まずは1. 結合律からだ。
結合律はざっくりいうと「射を合成する順番を変えても作成されるものは変わらない」ことを要請している。
結合律を図にすると図1のようになるだろう。
f:id:sereronnrot:20201115192907j:plain
ここで、f, g, hを其々組み合わせるとどんな射が作成できるかを考えてみる。
圏の性質として、「射f: A=> Bと射g: B => Cがある時、それらの合成である射g ∘ fが存在する」というものがあったので、 射f, gから g ∘ f: A => C を、 射g, hから h ∘ g: B => D を作成できる。 一旦、箇条書きにするとこうだ。
1. f: A => B
2. g: B => C
3. h: C => D
4. g ∘ f: A => C
5. h ∘ g: B => D

更に、fとh ∘ g, hとg ∘ fが合成出来るので、

  1. f: A => B
  2. g: B => C
  3. h: C => D
  4. g ∘ f: A => C
  5. h ∘ g: B => D
  6. (h ∘ g) ∘ f : A => D
  7. h ∘ (g ∘ f) : A => D

が作成できる。
結合律は6.と7.の射が同じであるということを要求しているわけだ。

余談

  1. 結合法則を満たさない概念ってあるの?

  2. ある。 例えば引き算は結合法則を満たさない。
    例 1 - (2 - 3) ≠ (1 - 2) - 3

次に2. 単位律を見ていく。
単位律は一言でいうと、「射の合成を演算として見た時に単位元が存在する」ということだ。
図で書くと以下のようになる。
f:id:sereronnrot:20201126225400j:plain

補足: 演算、単位元とは
演算とは、写像(関数)のことです。
例えば、足し算 (+)は、2つの値を受け取って1つの値を返す写像とみなせます。
ex) +(1, 3) = 4 // 1 + 3 = 4
単位元e とは、特定の演算 (*)において、以下の性質を持つ値のことを指します。
- e * a = a * e = a

演算が足し算の場合は1, 演算が掛け算の場合は0が単位元になります。
ex) 1 + 0 = 1
ex) 5 * 1 = 5

なぜ圏が(射の合成における)単位律を満たすことを要請しているかというと、日常生活で0や1が便利なように、射の合成を考える時に何かと便利だからだ。 (詳しい用例は今後見られるはず)

1.A Definition of Category 圏の定義

これまでの話をまとめると、圏の定義は以下のように書ける。

定義: 圏 Category

圏Cは以下の構成物を持つ
1. 対象: 対象の集まりをobj(C)と書く。
2. 射: 対象の関係を表す。 対象aと対象bの間の射の集合をHom(a, b)やC(a , b)と書く。
3. 合成: 射の合成規則。射f, gが合成可能な場合、g ∘ fも射に含まれる。
射は以下の性質を持つ
1. 結合律: f: a → b, g: b → c, h: c → d が存在するなら、それらに関して h ∘ (g ∘ f) = (h ∘ g) ∘ f が成り立つ。
2. 単位律: 1つ1つの対象xに対して、以下の性質を持つ射が存在する。(これは、xの 恒等射**と呼ばれる)
- 任意の射 f: a -> x及び g: x -> bに対して、
- idx ∘ f = f かつ g ∘ idx = g
定義終

圏の定義において構成物は対象 Obj(C), 射 Hom(a, b), 合成則 ∘ の3つだが、便宜上、以下の4つの構成物を定義することで具体的な圏を考えていく。
1. 対象 obj(C)
2. 射 Hom(a, b)
3. 恒等射 ida
4. 合成 ∘

構成物に恒等射が追加されていることに注目してほしい。本来は恒等射も射の一部であるが、自明でないものもあるため明示的に書くことにする。
 
さて、我々はこれから圏論の様々な定理を学んでいく過程で、具体例として以下のように定義されたプログラムの圏 というものを多用する。

定義: プログラムの圏

  1. 対象: Scalaのデータ型
  2. 射: Scalaで書かれた純粋関数*1
  3. 合成: 以下のコードで定義されたcompose関数
def compose[A, B, C](f: A => B, g: B => C)(a:   A):C = g(f(a))  

4 . 単位射: 以下のコードで定義されたidentity関数

def identity[A](a: A) = a

定義終

この圏は、Haskellというプログラミング言語の圏(Hask圏)をScalaで再現した圏になっている。
コード例をScalaで書くためにこの圏を導入しているので、適宜Hask圏に置き換えても問題は(多分)ない。

Ch1.1で見た図解には単位射が書かれていなかった。キチンと書くなら以下のようになる。
f:id:sereronnrot:20201123205601j:plain

補足:
Hask圏は圏ではないという考えもある(https://myuon.github.io/posts/versus-hask-category/ など)が、この記事の目的は圏の正確な理解ではなく、ざっくりとした理解とプログラミングへの応用を考えることなので、ひとまずこの問題には目を瞑ろうと思う。
ぶっちゃけよくわからない。この本を読めたらこの記事もわかるんだろうか。

1.B 圏を見る視点

このノートでは、圏を見る視点/アイデアが3つ紹介されている。
圏によってどの視点で見るのが自然であるかは異なるため、それぞれの視点で見るのが適切である圏の特徴も合わせて記載する。
(勿論、2つの視点で見ることができる圏もある多分)

  1. 関係としての圏: 圏は対象の集まりであり、それらは互いにある一貫した方法で関連している。

    • 特徴: 2つの対象の間の射は、多くの場合存在したとしても1つのみ
  2. 操作としての圏: 圏は操作の集まりであり、それらはある一貫した方法で組み合わせることができる。

    • 特徴: 対象が1つだけである場合が多い
  3. 特別な構造を持つ空間と写像としての圏: 圏は特別な構造を持った空間や集合の集まりであり、それらの間の写像はその構造と両立される。

    • 特徴: 最も一般的。特にこれといったものはない。

プログラムの圏は、1.関係としての圏と見るのが最も自然だろうか。
1. 関係としての圏の視点から見た場合、データ型同士の関係としてどのようなものが考えられるかを表している。
ex) f: Int -> String = x => x.toString + "!!!"
(この場合、Int型の各値に関して、文字列に変換した後"!!!"を結合した結果の文字列が関係していると言える)

それぞれの視点から見た圏の例を以下に載せる(が、興味がある人だけで良い)

関係としての圏

例1) 集合と順序関係の圏
1. 対象 : ≦を順序関係とした前順序集合S
2. 射 : f: a -> bとして a ≦ b
3. 単位射 : a ≦ a
4. 合成 : (a ≦ b) ∘ (b ≦ c) = ( a ≦ c)

前順序集合とは、前順序を満たす集合だ。
前順序とは、以下の2つの条件を満たす関係をいう。
1. 反射律(Reflexivity) : 任意のx ∈ S に対して x ≦ x
2. 遷移律(Transitivity) : 任意の x, y, z ∈ S に対して、もし x ≦ y かつ y ≦ z なら x ≦ z

反射律は単位射の存在を、遷移律は合成の存在を保証していることに注意しよう。
この圏においては、射は正に関係を表していると言える。

余談:
前順序集合の例として、「物の値段」が紹介されていた。
前順序関係は「物品Aの値段が物品Bの値段より安い」場合に A ≦ Bとし、
集合としては「物品の集合」を考える。
この時、A ≦ B かつ B ≦ Aの時にA = B は成り立たない。
(値段が同じだけで物品としては異なるからだ)
しかし、それらは「値段が同じであるため、交換が可能」という視点では「同値」である。
圏論でも、2つの対象が「同じ」ではないが、何らかの基準で「同値」であることを利用する時がある。
例えばものの交換を考えるときなどは2つの対象が強い意味で「同じ」である必要はないからだ。
f:id:sereronnrot:20201126235350j:plain

関係としての圏において、2つの対象の間の射は多くの場合存在したとしても1つのみである。
なぜなら、関係は「ある」か「ない」かの2択であるからだ。

操作としての圏

いきなり例に移る前に、言葉の定義をする。

定義: 群 Group
集合 G とその集合上の二項演算 ・: G × G -> G の組が以下の条件を満たすときに,その組 (G,・) を群と言う。
この時、二項演算・を積と呼ぶ。
a. 結合法則: 任意のa, b, c ∈ G に対して、 (a・b)・c = a・(b・c)
b. 単位元の存在: a・e = e・a = a を満たすe ∈ G が存在し、単位元と呼ぶ。eは1とも表記される。
c. 逆元の存在: 任意のa ∈ Gに対して、 a・a' = a'・a = e を満たす a' ∈ Gが存在し、逆元と呼ぶ。
定義終

例えば、(Z 整数, +)は群である。(Z, *)は群にはならない。何故なら0に対する逆元が存在しないからだ。
さて、何故ここで群を紹介したのかというと、群は図形の回転などの何らかの操作を表すことができるからだ。
例) パックマンの回転
パックマンが絵として書かれていた時に、それを90°, 180°, 270°, 360°回転する操作を考える。
この回転を、それぞれS0, S1, S2, S3, S4と表記し、a, bの積をaの操作を行った直後にbの操作を行うこととすると、
G = ({S0, S1, S2, S3, S4}, ・)は群になる。
例えばS3 = S2・S1であり、S3の逆元はS1だ。単位元はS0。

f:id:sereronnrot:20201127004523j:plain

圏の例に移ろう。

例2) 群の圏
(G, ・)を群とする。The delooping of G (訳が見つからなかった) を BGと書き、以下の圏とする。
1. 対象: たった一つの☆ (☆自体に意味はない)
2. 射: Gの各要素 g に対して1つの射 g: X -> X が定義される(要素の名前と射の名前が同じ出ることに注意)
3. 単位射: 特に、 1 ∈ Gに対応する射
4. 合成 ∘ : 合成は群の積・によって与えられる。つまり、g ∘ f はg・f ∈ G に対応する射。
圏の結合律と単位律は群の定義により満たされる。

群の圏は少し変わったものに見えるだろう。
(Z, +)を圏として図で書くと、以下のようになる。
f:id:sereronnrot:20201127002341j:plain
(図には書ききれないが、勿論Zの中の要素の数だけ射がある)
この圏では対象に関しては特に意味はなく、射にすべての意味が凝縮されていることに注目しよう。

パックマンの回転の圏は、以下のような図でかける。
f:id:sereronnrot:20201127004751j:plain

操作としての圏では、対象が1つだけである場合が多い。
なぜなら、対象自体に意味はなく、射とその結合に意味があるからだ。

特別な構造を持つ空間と写像としての圏

この視点の圏は、これまでのものよりかなり一般的なものだ。
そのため、射の結合に関してきちんと確認する必要が出てくる。
(関係としての圏では合成則を調べるのは楽だった。対象間の射の数がほぼ1つだからだ。
操作としての圏では1つしか対象がないので、ドメインとコドメインに関して何も考える必要がなかった。)

いくつか例を記載するので、知っている分野があればそこから空気感を掴んでほしい。

例3) Set圏
1. 対象: 集合
2. 射: f: a -> bとして 集合aが定義域で集合bが値域の関数
3. 単位射: 恒等関数
4. 合成: 関数合成

例4) Vect圏 1. 対象: (抽象)ベクトル空間
2. 射: f: a -> bとして aからbへの線形写像 3. 単位射: 恒等写像
4. 合成: 関数合成

例5) Meas圏
1. 対象: (抽象)可則空間
2. 射: f: a -> bとして aからbへの可則写像
3. 単位射: 恒等写像
4. 合成: 関数合成

例6) Graph
1. 対象: (有向または無向)グラフ
2. 射: f: G -> Hとして グラフGからグラフHへの、ノード間の隣接関係を保持した写像
3. 単位射: 恒等写像
4. 合成: 関数合成

1.C Definition of Diagram and Commutative Diagram 図式と可換図式

ここで、これからずっと使用する「可換図式」のざっくりとした定義をする。
(よりフォーマルな定義は関手という概念を学んだあとになる)

定義 図式 Diagram

圏Cの可換図式は圏Cの(全部・或いは一部の)対象をノード(点)、射をエッジ(矢印)としてもつ有向グラフである。 可換図式は以下の特徴を持つ。
a. 各対象・射は図式に複数回現れる事ができる。
b. 2つの対象の間で複数の射が存在することができる。
c. 図式内の任意の対象Xに対して、それぞれに対応する恒等射idxは図式内では明示的に書かれない
d. 図式内の射(矢印) f: X -> Y, g: Y -> Z の合成射 g ∘ f は図式内には明示的に書かれない
定義終

同じ対象・射が図式に複数回(異なるノード・エッジとして)書かれる事があることに注意しよう。

図式の例をいくつか載せる。
f:id:sereronnrot:20201127013040j:plain

定義: 可換図式 Commutative Diagram

図式の中の任意の2つの点X, Yに対して、XからYへの合成可能な矢印で構成されるパス(つま合成射)が全て等しい時、図式が可換であると言う。
また、その時の図式を可換図式とも呼ぶ。
定義終

勿論、全ての図式が可換であるわけではない!

以下の図式は、 h = g ∘ f である場合にのみ可換だ。
f:id:sereronnrot:20201127013457j:plain

以下の図式は、g ∘ f = k ∘ hである場合にのみ可換だ。
f:id:sereronnrot:20201127013553j:plain

以下の図式が可換である条件はなんだろうか?
f:id:sereronnrot:20201127014220j:plain

可換である条件を書き下してみると以下のようになる。
(それぞれのパスがどの様に得られるかは下図を見てほしい。)
1. ① = ②: p ∘ k = h ∘ f
2. ③ = ④: q ∘ h = l ∘ g
3. ⑤ = ⑥ = ⑦: q ∘ p ∘ k = q ∘ h ∘ f = l ∘ g ∘ f
f:id:sereronnrot:20201127014434j:plain

ここで、条件3を以下のように変形すると、条件1, 2から自動的に満たされるので条件3は消せることがわかる。
q ∘ p ∘ k = q ∘ h ∘ f (条件1より)
q ∘ h ∘ f = l ∘ g ∘ f (条件2より)
よって、l ∘ g ∘ f = l ∘ g ∘ f = l ∘ g ∘ f

ところで、条件1, 2はそれぞれ{X, Y, A, B}の図式と{Y, Z, B, C}の図式が可換である条件だ。
このように可換図式はそれぞれのー部分が可換であれば全体で可換となる場合がある。(今回触れたパターンはその代表的なものだ)

1.3 Composition is the Essence of Programming 合成こそがプログラムの本質である

プログラムが関数合成で書けたら嬉しいよねって話だったり、
圏論では対象の中身を意識しないのは関数の具体的な実装を見なくて良いような嬉しさがあるよねって 話が書いてある。
正直そんなに大したこと書いてない印象。

ただ、覚えておいた方がいいのは、「圏においてメインの主役は射と合成則」ということだ。(この感覚は章を進むごとにわかる..多分)
これから、対象に対しても様々な特徴付けがなされるが、特に注目すべきは「他の対象との関係に基づく特徴付け」であり、
関係は射(と合成則) によって表現される。
そして、理解を促したり特別な場合を除いて、対象の中身はブラックボックスとして扱う。
ここら辺の話はおいおい強調していきたい。
ぶっちゃけ自分もそこまでわかっていない。

1.4 Challenges

TODO: 今度書く

おしまい!
参考文献
- http://bitterharvest.hatenablog.com/entry/20 16/11/24/203021
- https://ja.wikipedia.org/wiki/%E4%BA%8C%E9%A 0%85%E6%BC%94%E7%AE%97
- https://github.com/hmemcpy/milewski-ctfp-pdf
- https://mathtrain.jp/group

*1:純粋関数とは、「副作用がなく、引数が同じ場合に常に同じ結果を返す関数」のことをいう。
副作用とは、関数が評価値を返す以外の影響をプログラムに与える(例えばグローバル変数の変更など)ことを指す。