プログラマのための圏論: 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らしい