はじめに
前回、圏と圏との間の対応である関手について定義し、いくつかのインスタンスを見ていきました。
本記事では関手についてさらに深掘り、今後の議論の際に必要となるいくつかの関手について説明します。
まず、型構築子に2つの型パラメータを持つ関手である双関手について説明します。双関手の一般的な定義は直積圏を用いて与えられるので、直積圏についても説明します。双関手を用れば、積と余積を構成可能であることを示します。
次に、以前見た Writer 圏は、Writer 関手でもあることを説明します。
Writer 関手を見たあとは、Reader 関手について説明します。Reader 関手は前章でも少し見まして、ある型を返すような関数を作る操作が関手であることが言えましたね。ここでは、Reader 関手に与える型パラメータを1つと固定する (返り値の型を指定する) のではなく、2つ指定する (引数と返り値の型を指定する) ことを考え、これと双関手の関係性について見ていきます。実は、2つの型パラメータをとる Reader 関手は、Profunctor と呼ばれる関手の1つであることがわかります。
最後に、Profunctor の具体例であって、圏論において重要な概念である Hom 関手について説明します。
少し難しいかもしれませんが、なるべくコードに落として学んでいければと思います!
サンプルコード
本記事のサンプルコードは、下記リポジトリに置いてあります。コンソールで動かしたい場合、リポジトリをクローンして試してみていただければと思います。
双関手
双関手 (bifunctor) は、型構築子に2つの型パラメータを持つ関手です。
双関手において、対象関数 F[_, _]
を、2つの型 A
、B
を型 F[A, B]
に対応させるものとして定義します。
また、射関数 bimap
を、射 A => C
と B => D
に対して射 F[A, B] => F[C, D]
を対応させるものとして定義します。
双関手の型クラスを定義すると、以下のようになります。
trait Bifunctor[F[_, _]]: /** Morphism mappings for Bifunctor */ def bimap[A, B, C, D](f: A => C)(g: B => D): F[A, B] => F[C, D] def first[A, B, C](f: A => C): F[A, B] => F[C, B] = bimap(f)(identity[B]) def second[A, B, D](g: B => D): F[A, B] => F[A, D] = bimap(identity[A])(g)
Bifunctor
型クラスは、対象関数として型構築子 F[_, _]
をもち、射関数として bimap
メソッドをもちます。first
および second
は、双関手の型パラメータの1つ目と2つ目の値に対してそれぞれ変換を施すものです。
bimap
メソッドを定義すれば first
メソッドと second
メソッドを実装できますし、first
メソッドと second
メソッドを実装すれば bimap
メソッドを実装することができます。
直積圏を定義する
双関手の一般的な定義を与えるために、直積圏 (product category) という概念を導入します。
2つの圏 ${\mathcal{C}}1$ と ${\mathcal{C}}2$ に対して、直積圏 ${\mathcal{C}}1 \times {\mathcal{C}}2$ を考えることができます。
直積圏 ${\mathcal{C}}1 \times {\mathcal{C}}2$ は、対象を ${\mathcal{C}}1$ の対象 $a$ と ${\mathcal{C}}2$ の対象 $b$ のペア $(a, b)$ とします。
そして、射を ${\mathcal{C}}1$ の射 $f: a \to c$ と ${\mathcal{C}}2$ の射 $g: b \to d$ のペア $(f, g)$ とします。Hamcat では、関数のペアをラッパークラスとして実装してみました:
case class ProductFunction[A, B, C, D](run: (A => C, B => D))
どちらも対象と射のペアをとっているだけですね。
射の合成についてもペアをとるだけです。${\mathcal{C}}1$ における射の合成 $h \cdot f$ と ${\mathcal{C}}2$ における射の合成 $k \cdot g$ に対して、$(h \cdot f, k \cdot g)$ は直積圏 ${\mathcal{C}}1 \times {\mathcal{C}}2$ における射の合成になります:
/** Composition of morphism in product category */ def andThen[E, H](v: ProductFunction[C, D, E, H]): ProductFunction[A, B, E, H] = run match case (f, g) => v.run match case (h, k) => ProductFunction((f andThen h, g andThen k)) /** Composition of morphism in product category */ def compose[E, H](v: ProductFunction[E, H, A, B]): ProductFunction[E, H, C, D] = run match case (f, g) => v.run match case (h, k) => ProductFunction((f compose h, g compose k))
上記のように射の合成 andThen
メソッドと compose
メソッドを定義すると、Scala の直積圏における2つの射 (A => C, B => D)
と (C => E, D => H)
を合成して (A => E, B => H)
を構成できます。
恒等射も同様に、 $\mathcal{C}1$ の恒等射 $id_1$ と $\mathcal{C}2$ の恒等射 $id_2$ に対して $(id_1, id_2)$ が直積圏の恒等射になります。
/** Identity morphism */ def productIdentity[A, B]: ProductFunction[A, B, A, B] = ProductFunction((identity[A], identity[B]))
直積圏における射の合成の例
ProductFunction
クラスは、Scala 圏と Scala 圏の直積圏の実装です。
対象は、2つの Scala 圏の対象、すなわち型 A
と型 B
のタプルです。例として、A
を Int
とし、B
を Long
としておきます。
/** Object declaration */ val obj = (3, 4L)
直積圏における射 func1
と func2
は、Scala 圏の2つの射、すなわち関数 A => C
関数 B => D
のタプルです。func1
は第1引数として Int
型のインクリメント関数 increment
を持ち、第2引数として Long
型の数を2倍する関数 doubleL
を持ちます。func2
は第1引数として Int
型の数が偶数かどうか判定する関数 isEven
を持ち、第2引数として Long
型の数が奇数かどうか判定する関数 isOddL
を持ちます。
def increment: Int => Int = _ + 1 def doubleL: Long => Long = _ * 2 def isEven: Int => Boolean = _ % 2 == 0 def isOddL: Long => Boolean = _ % 2 == 1
import hamcat.arrow.ProductFunction /** Morphism declaration */ val func1 = ProductFunction((increment, doubleL)) val func2 = ProductFunction((isEven, isOddL))
それぞれの関数の定義は以下のようになっています。
ProductFunction
クラスには関数適用のために apply
メソッドをはやしているので、以下のように関数適用の結果を出力できます。
/** Apply morphism to object */ val func1Apply: (Int, Long) = func1(obj) // func1Apply: (Int, Long) = (4, 8L) val func2Apply: (Boolean, Boolean) = func2(obj) // func2Apply: (Boolean, Boolean) = (false, false)
この直積圏における射の合成は、先ほど定義した andThen
メソッドおよび compose
メソッドを使って構築できます。この合成関数は、第1引数として Int
型の数が奇数かどうか判定する(インクリメントして偶数かどうか判定するので)関数を持ち、第2引数として常に false
を返す(数を2倍したあと奇数かどうかを判定するので)関数を持ちます。
/** Compose morphism */ def func2ComposeFunc1 = func2 compose func1 def func1AndThenFunc2 = func1 andThen func2
これらの関数に (3, 4L)
を適用すると以下の結果が返ります。
/** Apply composition of morphism */ val result1 = func2ComposeFunc1(obj) // result1: (Boolean, Boolean) = (true, false) val result2 = func1AndThenFunc2(obj) // result2: (Boolean, Boolean) = (true, false)
双関手の一般的な定義
さて、2つの圏の対象と射、射の合成をそれぞれペアにすることによって、直積圏を定義しました。双関手の話に戻りましょう。
一般的に、双関手は以下のように定義されます。
Scala 圏において関手は自己関手となるので、Scala 圏における双関手 (すなわち Bifunctor) は Scala 圏と Scala 圏の直積から Scala 圏への関手になります。
すなわち、Bifunctor
は、対象関数 F[_, _]
として Scala の直積圏の対象 A
と B
を F[A, B]
に対応させ、射関数 bimap
として Scala の直積圏の射 A => C
と B => D
を F
に関する射 F[A, B] => F[C, D]
に対応させます。
なお、bimap
の引数が (A => C, B => D)
ではなく A => C
と B => D
であるのは、使いやすさの観点からです。これらは、互いに同型であるので、どちらの形でも問題はありません。
def isomorpTupleToFunc1[A, B, C, D]: ((A => C, B => D)) => (A => C) => (B => D) = { case (f, g) => f => g } def isomorpFuncToTuple[A, B, C, D]: (A => C) => (B => D) => ((A => C, B => D)) = f => g => (f, g)
では、双関手のいくつかの例をみていきましょう。
Tuple2 は双関手
積は、2つの型パラメータから構築されます。
val tuple: Tuple2[Int, String] = (33, "thirty three")
Tuple2
は2つの型パラメータを持つため、双関手の候補になります。
実際、積を構築する積関手 Tuple2
は、双関手の例です。
Scala の直積圏から型を1つずつとってきて、型構築子 Tuple2[_, _]
によって Scala 圏の型 Tuple2
を構成します。
Tuple2
の射関数 bimap
は以下のように定義されます。すなわち、直積圏の射 f: A => C
, g: B => D
が与えられると、それらを Tuple2
に関する射 Tuple2[A, B] => Tuple2[C, D]
に引き上げます。
/** Product bifunctor */ given Bifunctor[Tuple2] with def bimap[A, B, C, D](f: A => C)(g: B => D): ((A, B)) => ((C, D)) = case (a, b) => (f(a), g(b))
Either もまた双関手
余積も積と同様、2つの型パラメータから構築されます。
val right: Either[Int, String] = Right("thirty three")
余積を構築する余積関手 Either
は、双関手の例です。
積と同様に、Scala の直積圏から型を1つずつとってきて、型構築子 Either[_, _]
によって Scala 圏の対象 Either
型に対応させます。
Either
の射関数 bimap
は以下のように定義されます。すなわち、直積圏の射 f: A => C
, g: B => D
が与えられると、それらを Either
に関する射 Either[A, B] => Either[C, D]
に引き上げます。
/** Coproduct bifunctor */ given Bifunctor[Either] with def bimap[A, B, C, D](f: A => C)(g: B => D): Either[A, B] => Either[C, D] = case Left(a) => Left(f(a)) case Right(b) => Right(g(b))
Writer 関手の再登場
以下の記事で、Kleisli 圏の例として Writer 圏を見ました。
Writer 圏において、以下のような型 Writer
を導入しました。
// L: Monoid type Writer[L, A] = (L, A)
Writer 圏における対象は任意の型 A
で、A
から A
への射は A => Writer[L, A]
だと定義しました。
実は、Writer 圏における射の合成をうまく活用することによって、Writer
型についての fmap
メソッドを実装することができます。そのため、Writer
型は関手であって、Writer 関手と呼ばれます。
/** Writer Functor */ case class Writer[L, A](run: (L, A)): def fmap[B](f: A => B)(using Monoid[L]): Writer[L, B] = (identity[Writer[L, A]] _ >=> (a => Writer.pure[L, B](f(a))))(this)
identity[Writer[L, A]] >=>
が使えることに驚くかもしれませんが、うまくいきます。>=>
は A => Writer[L, B]
の形をした関数が持つメソッドです。identity[Writer[L, A]]: Writer[L, A] => Writer[L, A]
はこの形をしているので、>=>
を呼び出すことができます。
Reader 関手
前回の記事では型 A
を R => A
に対応させ、関数 A => B
を R => B
に引き上げる Reader 関手を考えました。
/** Reader functor */ given [R]: Functor[Function1[R, *]] with def fmap[A, B](f: A => B): (R => A) => (R => B) = f compose _
この型構築子 Function1[_, _]
は2つの型パラメータを持つので、双関手の候補であると考えられます。
ここでは、Function1
を双関手のインスタンスとして実装できるかどうかについて考えていきましょう。
Function1 は双関手か?
Bifunctor
のインスタンスでは、bimap
を実装する必要があります。ただ、bimap
は first
および second
を実装することによって、これらを組み合わせて実装することができます。
trait Bifunctor[F[_, _]]: /** Morphism mappings for Bifunctor */ def bimap[A, B, C, D](f: A => C)(g: B => D): F[A, B] => F[C, D] def first[A, B, C](f: A => C): F[A, B] => F[C, B] = bimap(f)(identity[B]) def second[A, B, D](g: B => D): F[A, B] => F[A, D] = bimap(identity[A])(g)
まず、Bifunctor
の second
メソッドは、前章でみた Reader 関手の射関数です。
/** Reader bifunctor ? */ given Bifunctor[Function1] with override def second[A, B, C, D](g: B => D): (A => B) => (A => D) = fab => g compose fab
では、first
メソッドはどうでしょうか?
def first[A, B, C](f: A => C)(fa: A => B) => (C => B) = ???
シグネチャを見ると分かる通り、関数 A => C
と A => B
の組み合わせでは C => B
を構成することができません。
first
メソッドを定義できない、すなわち射関数 bimap
を定義できないことから、Function1
は双関手でないと言えます。
Function1 に対して first メソッドを定義する
前項で見た通り、関数 A => C
と A => B
からは C => B
を構成することはできませんでした。
override def first[A, B, C](f: A => C): (A => B) => (C => B) = ???
しかしながら、関数 f: A => C
の矢印を反転させて oppF: C => A
を受け取れば、first
メソッドを定義できます。
override def first[A, B, C](oppF: C => A): (A => B) => (C => B) = fa => fa compose oppF
少し言い換えると、直積圏における第1要素の射の矢印を入れ替えれば、第1要素の射を Function1
に関する射に引き上げることができました。
さて、ある圏において、対象はそのままで射の矢印を入れ替えたものを、その圏の双対圏と呼ぶことができましたね。これはすなわち、Function1 が Scala の双対圏と Scala 圏の直積圏から Scala 圏への関手となっていると言うことができます。first
メソッドは、Scala の双対圏からの射関手であると言えます。
共変関手と反変関手
一般に、ある圏 $\mathcal{C}$ の双対圏 ${\mathcal{C}}^{op}$ からある圏 $\mathcal{D}$ への関手のことを反変関手 (contravariant functor) と呼びます。
一方で、これまで話してきた標準の関手は共変関手 (covariant functor) と呼ばれます。
共変関手と同様に、反変関手の型クラス Contravariant
は以下のように定義されます。対象関数 F[_]
は反変関手と同じです。射関数 contramap
は、射 B => A
を F
に関する射 F[A] => F[B]
に引き上げます。
// Contravariant functor trait Contravariant[F[_]]: def contramap[A, B](f: B => A): F[A] => F[B]
Function1
の第1引数に対して Contravariant
のインスタンスを以下のように実装できます。型の変数は違うものの、先ほどの見た first
メソッドと同じ実装になっているはずです。
/** Reader contravariant functor */ given [R]: Contravariant[Function1[*, R]] with def contramap[A, B](f: B => A): Function1[A, R] => Function1[B, R] = _ compose f
override def first[A, B, C](oppF: C => A): (A => B) => (C => B) = fa => fa compose oppF
Profunctor
共変関手と反変関手の概念を用いると、型構築子 Function1[_, _]
は第1引数に関して反変であり、第2引数に関して共変であると言われます。
このように、1つ目の型パラメータが反変で2つ目の型パラメータが共変であるような型構築子は、Profunctor と呼ばれます。Profunctor も関手であって、対象関数は F[_, _]
です。射関数 bimap
は、第1引数 C => A
を反変関手のように引き上げ、第2引数 B => D
を共変関手のように引き上げることによって F[A, B] => F[C, D]
に引き上げます。
// Profunctor trait Profunctor[F[_, _]]: def bimap[A, B, C, D](f: C => A)(g: B => D): F[A, B] => F[C, D]
先ほど見たように、Function1
は Profunctor
です。Function1
の Profunctor
のインスタンスは、以下のように定義されます。
/** Reader profunctor */ given Profunctor[Function1] with def bimap[A, B, C, D](f: C => A)(g: B => D): (A => B) => (C => D) = g compose _ compose f
なお、Profunctor の一般的な定義は双対圏を用いて与えられます:
Scala 圏は集合圏の拡張であるため、Scala 圏の双対圏と Scala 圏の直積から Scala 圏への関手を Profunctor と定義することができます。
Hom 関手
最後に、圏論における重要な概念である Hom 集合 (hom set) について紹介します。一般に、ある圏 $\mathcal{C}$ の Hom 集合は、$\mathcal{C}$ の全ての射の集まり $\mathcal{C}(a, b)$ ($a$ と $b$ は $\mathcal{C}$ における任意の対象)として定義されます。
Scala 圏における Hom 集合は、射 $a \to b$ の集まり、すなわち Function1[A, B]
です。Function1[A, B]
を構成する操作は Profunctor で、Scala の双対圏と Scala 圏の直積圏から Scala 圏への関手のことでした。
これと同様に、Hom 集合を構成する操作も Profunctor であって、Hom 関手 と呼ばれます。Profunctor として捉えると、ある圏 $\mathcal{C}$ の Hom 関手とは、直積圏 ${\mathcal{C}}^{op} \times \mathcal{C}$ から集合圏 Set への関手であると考えられます。
${\mathcal{C}}^{op} \times \mathcal{C}$ の射 $(F^{op}: e \to a, g: b \to f)$ を Hom 関手によって引き上げると、Hom 集合 $\mathcal{C}(a, b)$ から Hom 集合 $\mathcal{C}(e, f)$ の集合に変換されます。ここで、$\mathcal{C}(a, b)$ のなんらかの要素 $h$ (これは射 $a \to b$ の一つ)をとってきて
$g \cdot h \cdot F^{op}$
とすると、これは射 $e \to f$ となり、$\mathcal{C}(e, f)$ の要素が得られます。
まとめ
- 2つの圏 $\mathcal{C}$ と $\mathcal{D}$ の直積圏とは、対象・射・射の合成それぞれを $\mathcal{C}$ と $\mathcal{D}$ のペアとして定義した圏のことである。
- 対象:
(A, B)
- 射:
(A => C, B => D)
- 射の合成:
((C => E) compose (A => C), (D => H) compose (B => D))
- 対象:
- 双関手は型構築子に2つの型パラメータを持った関手である。
- 直積圏からの関手と定義される:$\mathcal{C} \times \mathcal{D} \to \mathcal{E}$
- 積関手である Tuple2 は、双関手である。
- 余積関手である Either は、双関手である。
- Writer も関手である。
- Function1 は型構築子に2つの型パラメータを持つが、双関手ではない。
- 双対圏からの関手を反変関手という。
- 標準の圏からの関手を共変関手という。
- 第1引数が反変で、第2引数が共変な関手を Profunctor という。
- Function1 は Profunctor である。
- Profunctor は、双対圏との直積圏から集合圏への関手として定義される: ${\mathcal{C}}^{op} \times \mathcal{D} \to Set$
- ある圏 $\mathcal{C}$ の Hom 集合とは、$\mathcal{C}$ の全ての射の集まりのことである。
- Scala 圏の Hom 集合は
Function1[A, B]
である。 - 2つの対象 $a$ と $b$ から Hom 集合 $\mathcal{C}(a, b)$ を作る操作は関手であり、Hom 関手と呼ばれる。
- Hom 関手は、Profunctor である:${\mathcal{C}}^{op} \times \mathcal{C} \to Set$
- Scala 圏の Hom 集合は