Scala プログラマのための圏論入門 (6) 関手

はじめに

これまで、圏は対象の集まりと射の集まりからなり、その例として Scala 圏 (対象は型 A、射は関数 A => B)、集合圏 (対象は集合 $A$、射は関数 $f: A \to B$)、Writer 圏 (対象は型 A、A から B への射は関数 A => Writer[L, B]) などがあると説明しました。

taretmch.hatenablog.com

taretmch.hatenablog.com

ここでは、圏そのものの変換を考えます。

圏の間の対応が関手と呼ばれる概念です。関手があれば、圏の構造を維持したまま他のある圏に変換できるようになります。

本記事では、関手とは何かについて定義し、プログラミングにおける関手の例を示します。

サンプルコード

本記事のサンプルコードは、下記リポジトリに置いてあります。コンソールで動かしたい場合、リポジトリをクローンして試してみていただければと思います。

github.com

関手とは

関手 (functor) は、圏の構造を維持しながら、ある圏 $\mathcal{C}$ を別のある圏 $\mathcal{D}$ に変換する対応 $F: \mathcal{C} \to \mathcal{D}$ のことです。

関手の例としては Option 関手、List 関手、Writer 関手、モノイド準同型などがあります。モノイド準同型は、モノイド間の関手です。

圏は対象と射から構成されるので、圏を変換するには対象と射それぞれに関する対応を定義する必要があります。

Option 関手は、型 A の値を Option で包んで型 Option[A] に変換します。また、関数 A => B を関数 Option[A] => Option[B] に変換します。

同様に、List 関手は型 A を List[A] に変換し、関数 A => B を List[A] => List[B] に変換します。Writer 関手も型 A を Writer[A] に変換し、関数 A => B を Writer[A] => Writer[B] に変換します。

関手

関手の例〜順序を保つ関手〜

数学の話になりますが、関手のわかりやすい例があるので、紹介させてください [1]。

まず、圏 $\mathcal{C}$ として、有限集合 (個数が有限個の集合) を対象とし、単射 (出力が被らない関数) が存在するかどうかという関係を射とします。つまり、集合 $A$ から $B$ への単射が存在するとき、またそのときに限って射 $A \xrightarrow{f} B$ があるとします。

単射は、出力が被らない関数のこと

例えば、3つの集合 $A = \{a, b, c, d\}, B = \{e, g, h, i, j\}, C = \{k, l, m\}$ があるとします。$A$ から $B$ へは上図の通り単射が構成できます。一方で、$A$ から $C$ への関数はどのように構成しても出力が被ってしまう ($f(a, k), f(b, l), f(c, m), f(d, k)$ のように、必ず1つは被る) ため、$A$ から $C$ に射はありません。

有限集合を対象とし、単射が存在するかどうかの関係性を射とする圏

この圏は言い換えれば、集合の要素数の大小を比較している圏になります。要素が多い集合から少ない集合への単射は存在しませんが、少ない集合から多い集合への単射は存在するからです。

ここで、もう1つ各自然数を対象として、大小関係 $\leq$ を射とする圏 $\mathcal{D}$ を考えます。

$\mathcal{C}$ から $\mathcal{D}$ への関手 $F$ を、有限集合についてはその要素数を対応させ、単射の存在については大小関係の存在に対応させるものとします。つまり、集合 $A$ に対する $F(A)$ は $A$ の要素数を表し、$A$ から $B$ への単射が存在するとき $F(A) \leq F(B)$ とします。

順序を保つ関手

関手 $F$ は、有限集合の要素数の比較と、単射の存在の関係性とを言い換えた表現であることがわかります。この「順序を保つ関手」のように、関手は圏を言い換える、翻訳するような操作を表します。

対象関数

圏は対象と射から構成されるので、圏を変換するには対象と射それぞれに関する対応を定義する必要があります。

関手において、ある圏の対象をある圏の対象に変換するような対応を対象関数といいます。一般に、圏 $\mathcal{C}$ から $\mathcal{D}$ への関手 $F$ は、圏 $\mathcal{C}$ の対象 $A$ を $\mathcal{D}$ の対象 $F(A)$ に対応させます。Scala 圏から Scala 圏への関手 F の対象関数は、型 A を型 F[A] に対応させます。

Option 関手の例で言うと、Option 関手は型 A を型 Option[A] に対応させています。

def objOptFunc[A]: A =>  Option[A] = Option(_)

objOptFunc(3)
// res0: Option[Int] = Some(value = 3)
objOptFunc("Hoge")
// res1: Option[String] = Some(value = "Hoge")

順序を保つ関手の例で言うと、対象関数は有限集合 $A$ からその要素数への対応です。

射関数

関手において、ある圏の射を別のある圏の射に変換するような対応を射関数といいます。一般に、圏 $\mathcal{C}$ から $\mathcal{D}$ への関手 $F$ の射関数は、圏 $\mathcal{C}$ の射 $A \xrightarrow{f} B$ を $\mathcal{D}$ の射 $F(A) \xrightarrow{F(f)} F(B)$ に対応させます。Scala 圏から Scala 圏への関手 F の射関数 fmap は、関数 A => B を関数 fmap(f): F[A] => F[B] に対応させます。

Option 関手の例で言うと、射 f: A => B を fmap(f): Option[A] => Option[B] に対応させる必要があります。この対応は、標準ライブラリにある Option#map メソッドによって実現されます：

def isEven: Int => Boolean = n => n % 2 == 0

Option(3).map(isEven)
// res2: Option[Boolean] = Some(value = false)

Option 関手

関手性

射関数が満たすべき性質として、以下の2つがあります。この2つの性質は関手性 (functor laws) と呼ばれます。

定義：関手性

1. $\mathcal{C}$ の射 $f, g$ の合成 $g \circ f$ について $F(g \circ f) = F(g) \circ F(f)$ が成り立つこと。

fmap(g compose f)(a) == (fmap(g) compose fmap(f)) (a)

2. $\mathcal{C}$ の任意の対象 $A$ の恒等射 $id_A$ について $F(id_A) = id_{F(A)}$ が成り立つこと。

fmap(identity[A])(a) == identity[F[A]](F(a))

1つ目の性質は、関手が射の合成を保存することを意味します。

// f: isEven
// g: negate
def negate: Boolean => Boolean = b => !b

// fmap(g compose f)
OptionFunctor.fmap(negate compose isEven)

// fmap(g) compose fmap(f)
OptionFunctor.fmap(negate) compose OptionFunctor.fmap(isEven)

OptionFunctor.fmap(negate compose isEven)(Option(3)) == (OptionFunctor.fmap(negate) compose OptionFunctor.fmap(isEven))(Option(3))
// res3: Boolean = true

合成の保存

2つ目の性質は、関手が恒等射を保存することを意味します。

// fmap(identity[A])
OptionFunctor.fmap(identity[Int])

// identity[F[A]]
identity[Option[Int]]

OptionFunctor.fmap(identity[Int])(Option(3)) == identity[Option[Int]](Option(3))
// res4: Boolean = true

関手の定義

では、関手の定義を与えましょう。一般に、関手は以下のように定義されます。

定義：関手

圏 $\mathcal{C}$ から圏 $\mathcal{D}$ への関手 (functor) $F$ とは、以下を満たす対応のことです。

1. $\mathcal{C}$ の射 $A \xrightarrow{f} B$ を $\mathcal{D}$ の射 $F(A) \xrightarrow{F(f)} F(B)$ に対応させること。

   fmap(f: A => B): F[A] => F[B]
   

2. $\mathcal{C}$ の射 $f, g$ の合成 $g \circ f$ について $F(g \circ f) = F(g) \circ F(f)$ が成り立つこと。

   fmap(g compose f)(a) == (fmap(g) compose fmap(f))(a)
   

3. $\mathcal{C}$ の任意の対象 $A$ の恒等射 $id_A$ について $F(id_A) = id_{F(A)}$ が成り立つこと。

   fmap(identity[A])(a) == identity[F[A]](F(a))
   

先ほどみたように、2 番目と 3 番目は関手性を表します。

なお、圏 $\mathcal{C}$ と $\mathcal{D}$ は同じであってもよく、特に圏 $\mathcal{C}$ から圏 $\mathcal{C}$ への関手は自己関手 (endofunctor) と呼ばれます。Scala 圏における関手は全て、自己関手です。

プログラミングにおける関手

前節では、関手の定義を与えました。本節では、Scala プログラミングにおける関手を考えていきます。

Functor 型クラス

関手は Scala において、Functor 型クラスとして実装できます。Functor 型クラスは、対象関数として型構築子 F[_] をもち、射関数として fmap メソッドを持ちます。

// Functor
trait Functor[F[_]] {
  def fmap[A, B](f: A => B): F[A] => F[B]
}

この射関数 fmap は、関手性を満たす必要があります。すなわち、関数の合成を保存し、恒等射を保存しなければいけません。残念ながら型クラスの定義にこのバリデーションをかけられないので、fmap が関手性を満たすかどうかは Functor のインスタンスの実装によります。

fmap メソッドは関数を引き上げる (lift)、とも言われます。関数 A => B は、fmap によって F[_] 上の関数 F[A] => F[B] に引き上げられます。

Option 関手

Functor のインスタンスは、implicit value によって実装することができます。ここでは、Option についての Functor のインスタンスを定義してみましょう。

Option 関手のインスタンスは、以下のように実装できます。Functor に必要なパラメータは型構築子としての Option です。また、抽象メソッドである射関数 fmap を実装する必要があります。

/** Option functor */
implicit val OptionFunctor: Functor[Option] = new Functor[Option] {
  def fmap[A, B](f: A => B): Option[A] => Option[B] = _.map(f)
}

Option 関手の fmap メソッドは Option#map メソッドと同じです。

実際にこのインスタンスを使ってみましょう。

型クラスのインスタンスは、サンプルコードの hamcat.Implicits パッケージ内においてあります。コンソールにおいて hamcat.Implicits._ をインポートすれば、インスタンスが使えるようになります。

fmap に isEven (偶数かどうかを判定する関数) と Option(3) を与えると、Option(3) の中の値に isEven を適用した結果 (すなわち Some(false)) が出力されます。

import hamcat.Implicits._

OptionFunctor.fmap(isEven)(Option(3))
// res7: Option[Boolean] = Some(value = false)

なお、毎回 OptionFunctor.fmap(...) と書くのは面倒ですし、不便です。この場合、以下のようにシンタックスを定義することによって Option#fmap メソッドとして呼び出せるようになります。

implicit class FunctorOps[F[_], A](v: F[A])(implicit functor: Functor[F]) {
  def fmap[B](f: A => B): F[B] = functor.fmap[A, B](f)(v)
}

Option(3).fmap(isEven)
// res8: Option[Boolean] = Some(value = false)

これは Enrich my library パターンと言われるものです。

では、この Option 関手の fmap メソッドが関手性を満たすかどうかについて調べてみましょう。

関手性とは、以下が成り立つことでした。

fmap(g compose f)(a) == (fmap(g) compose fmap(f)) (a)
fmap(identity[A])(a) == identity[F[A]](F(a))

1つ目について、以下のテストコードで検証します。

val increment:   Int => Int     = n => n + 1
val isEven:      Int => Boolean = n => n % 2 == 0
def identity[A]: A   => A       = a => a
val none:        Option[Int]    = None

"Option functor" should "射の合成を保存する" in {
  // fmap(g compose f) == fmap(g) compose fmap(f)
  // Case: Some(1)
  assert(
    OptionFunctor.fmap(isEven compose increment)(Option(1))
      ==
    (OptionFunctor.fmap(isEven) compose OptionFunctor.fmap(increment))(Option(1))
  )
  assert(Option(1).fmap(isEven compose increment) == Option(1).fmap(increment).fmap(isEven))

  // Case: None
  assert(
    OptionFunctor.fmap(isEven compose increment)(none)
      ==
    (OptionFunctor.fmap(isEven) compose OptionFunctor.fmap(increment))(none)
  )
  assert(none.fmap(isEven compose increment) == none.fmap(increment).fmap(isEven))
}

2つ目については、以下のテストコードで検証します。

it should "恒等射を恒等射へ写す" in {
  // fmap(identity[A]) == identity[F[A]]
  // Case: Some(1)
  assert(OptionFunctor.fmap(identity[Int])(Option(1)) == identity[Option[Int]](Option(1)))

  // Case: None
  assert(OptionFunctor.fmap(identity[Int])(none) == identity[Option[Int]](none))
}

テストを実行してみると、成功しました！ここで実装した fmap は関手性を満たしてそうです。

sbt:hamcat> core/testOnly hamcat.data.FunctorOptionSpec
[info] FunctorOptionSpec:
[info] Option functor
[info] - should 射の合成を保存する
[info] - should 恒等射を恒等射へ写す
[info] Run completed in 452 milliseconds.
[info] Total number of tests run: 2
[info] Suites: completed 1, aborted 0
[info] Tests: succeeded 2, failed 0, canceled 0, ignored 0, pending 0
[info] All tests passed.
[success] Total time: 6 s, completed 2020/12/13 10:36:27

Reader 関手

次の例として、型 A を、A を返すような任意の関数 R => A に変換するような関手を考えます。この関手は Reader 関手と呼ばれます。

Reader 関手で重要なことは、関数も関手であるということです。関数が関手であれば、型 R を受け取って A を返すような関数 R => A があったとき、A を B に変換する関数 f: A => B を与えれば R から B の関数を取得することができます。

Reader 関手のインスタンスは、以下のように実装できます。対象関数として型構築子 Function1[R, ?] を渡し、射関数 fmap を実装します。ここで、Function1 は1変数関数を表す Scala 標準ライブラリの型です。Function1[R, ?] は R => ? を表します。

/** Reader functor */
implicit def Function1Functor[R]: Functor[Function1[R, ?]] = new Functor[Function1[R, ?]] {
  def fmap[A, B](f: A => B): (R => A) => (R => B) = fa =>
    f compose fa
}

(なお、Function1[R, ?] という記法は通常だとコンパイルエラーになります。サンプルコードではエラーを回避するため、typelevel 社の kind-projector [2] というコンパイラプラグインをインストールしています)

fmap メソッドは、ただ2つの関数を合成しているだけです。関数 R => A があったとき、引数として関数 A => B を受け取ると関数 R => B が返されます。

これを使うと、例えば以下のようなことができます。

// 偶数かどうか判定する関数を奇数かどうか判定する関数に変換する
isEven.fmap(negate) (3)
// res9: Boolean = true

compose が関手の射関数であるのですね。

関手の合成

圏の対応を考えるとき、その対応の合成、すなわち関手の合成を定義したいですよね。圏を対象として関手を射とするような圏を考えるのであれば、関手の合成は必須です。

Scala 圏における関手は全て自己関手なので、自己関手どうしを合成することができるのかどうかについて考えてみましょう。

例えば、2つの関手 Option と List を合成してみるとどうなるでしょうか。

対象関数は、型 Int を Option 関手によって Option[Int] に変換し、List 関手によって List[Option[Int]] に変換するものとします。

val intOptionList: List[Option[Int]] = List(Some(1), Some(3), None, Some(4))
// intOptionList: List[Option[Int]] = List(
//   Some(value = 1),
//   Some(value = 3),
//   None,
//   Some(value = 4)
// )

次に、射関数は、List 関手の fmap メソッドと Option 関手の fmap メソッドの合成 fmapC と定義します。

def fmapL[A, B]: (A => B) => List[A] => List[B] = ListFunctor.fmap
def fmapO[A, B]: (A => B) => Option[A] => Option[B] = OptionFunctor.fmap

def fmapC[A, B]: (A => B) => List[Option[A]] => List[Option[B]] = fmapL.compose(fmapO[A, B])

この fmapC メソッドを用いると、2つの関手によって包まれた型 Int 上の関数

val increment: Int => Int = _ + 1
// increment: Int => Int = <function1>

を List[Option[Int]] 上の関数として引き上げることができます。

fmapC(increment)(intOptionList)
// res10: List[Option[Int]] = List(
//   Some(value = 2),
//   Some(value = 4),
//   None,
//   Some(value = 5)
// )

これは、fmap メソッドを2回呼び出すことに等しいです。

intOptionList.fmap(_.fmap(increment))
// res11: List[Option[Int]] = List(
//   Some(value = 2),
//   Some(value = 4),
//   None,
//   Some(value = 5)
// )

外側の fmap は List 関手の射関数で、内側の fmap は Option 関手の射関数です。

関手の合成によって定義された射関数 fmapC は射の合成を保存しますし、恒等射を保存します。

// fmap(g compose f) == fmap(g) compose fmap(f)
fmapC(isEven compose increment)(intOptionList) == (fmapC(isEven) compose fmapC(increment))(intOptionList)
// res12: Boolean = true

// fmap(identity[A]) == identity[F[A]]
fmapC(identity[Int])(intOptionList) == identity[List[Option[Int]]](intOptionList)
// res13: Boolean = true

したがって、関手の合成もまた、関手であることがわかります。

自己関手の場合のみを取り上げましたが、自己関手でない一般の関手に関してもこれは成り立ちます。興味があれば証明してみてください。

まとめ

• 関手は、ある圏を、構造を維持しながら別のある圏に変換する対応のこと。
  • 関手の例として、Option、List、Reader などがある。
  • 関手は、対象 A を対象 F[A] に対応させる。
  • 関手は、射 f: A => B を射 fmap(f): F[A] => F[B] に対応させる。
• 関手が満たす以下の性質のことを、関手性と呼ぶ。
  • 射 f, g の合成 g . f について fmap(g compose f) == fmap(g) compose fmap(f) が成り立つこと。
  • 恒等射 identity[A] について fmap(identity[A]) == identity[F[A]] が成り立つこと。
• Reader 関手は、ある型 A に対して、A を返す任意の関数 Function1[?, A] を対応させる関手である。

参考文献

[1] 西郷 甲矢人, 能美 十三, 数学への招待シリーズ 圏論への道案内〜矢印でえがく数学の世界〜, 技術評論社, 2019.

[2] typelevel/kind-projector, https://github.com/typelevel/kind-projector

[3] Bartosz Milewski, Category Theory for Programmers, 2019, https://github.com/hmemcpy/milewski-ctfp-pdf.