プログラマのための圏論 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で実装している。

おしまい!