Milewski 氏の圏論講座の第1章 Category: The Essence of Compositionを読んでたら、冒頭あたりに次のような一文があった。

But the essence of a category is composition. Or, if you prefer, the essence of composition is a category.

射の合成こそが圏の本質で、またその逆も成り立つという。

Cats だと cats.arrowパッケージのArrowやCategoryといった型クラスで、いろいろなパターンの合成が提供されているらしい。今回はこれを調べてみた。

(Cats バージョンは 2.12の 2.0.0-M1。ソースはここ)

Arrow の階層

cats.arrow パッケージ内のArrow関連の継承関係は、下図のようになる。

以降、これらの型クラスを観察しながら素振りしてみる(CommutativeArrowは可換なだけのArrowなので割愛)。

方針

射のタイプとしては、ただのFunction1[?, ?]だとあまり面白くないので、Kleisli[Option, ?, ?]を使うことにした。また簡単のために以下のクライスリ射をなるべく使い回す。

type KleisliOption[A, B] = Kleisli[Option, A, B]

val toInt        = Kleisli((s: String) => Try(s.trim.toInt).toOption)
val invert       = Kleisli((n: Int)    => n.some.filter(_ != 0).map(1.0 / _))
val toPercentile = Kleisli((d: Double) => s"${d * 100}%".some)

Compose

Composeでは、異なる向きで射を合成するcomposeとandThenが提供されている。また、各々に対応する構文<<<と>>>が、cats.syntax.composeで定義されている。

val cko = Compose[KleisliOption]

(toInt >>> invert >>> toPercentile).run("5")         // "5" → 5 → 0.2 → "20.0%"
cko.compose(toPercentile, invert <<< toInt).run("5") // same as above
(invert <<< toInt).run("0")                          // None
cko.andThen(toInt, invert).run("foo")                // None

algebraK、algebraは、それぞれSemigroupK、Semigroupを返す。型パラメータの位置が違うだけで内容は変わらない。半群の結合的二項演算はcomposeになる。

val braces  = Kleisli((s: String) => s"{$s}".some)
val brackets = Kleisli((s: String) => s"[$s]".some)

cko.algebraK.combineK[String](braces, brackets).run("foo") // Some({[foo]})
cko.algebra[String].combine(braces, brackets).run("bar")   // Some({[bar]})

Category

Composeを継承するCategoryでは恒等射idが加わる。Compose#composeと合わせて、ここで圏の構成要素がそろう。

val cat = Category[KleisliOption]
cat.id[String].run("foo")  // Some(foo)

algebraKとalgebraは、MonoidKとMonoidを返す。Composeでは半群だったがCategoryでは恒等射を単位元とするモノイドになる。

type EndoKleisliOption[A] = KleisliOption[A, A]
implicit val monoidK: MonoidK[EndoKleisliOption] = cat.algebraK

cat.algebraK.empty[Int].run(100) // Some(100)

val ks: List[EndoKleisliOption[String]] = List(brackets, braces, brackets)
ks.foldK.run("baz") // Some([{[baz]}])

Choice

Categoryを継承するChoiceは、下図左の $f$ と $g$ から $h$ を求めるchoiceを提供する。圏論でいう余積の説明でよく見る構造になっている。

図の右のようにtoDoubleとinvertを合成して、KleisliOption[Either[String, Int], Double]を求めた。エイリアスとして提供される|||構文も使用した。

val choice = Choice[KleisliOption]

val toDouble = Kleisli((s: String) => Try(s.trim.toDouble).toOption)
val h = choice.choice[String, Int, Double](toDouble, invert)

h(Right(100))  // Some(0.01)
h(Left("NaN")) // Some(NaN)

import cats.arrow.Choice.ops._
(toDouble ||| invert)(Left("3.14")) // Some(3.14)
(toDouble ||| invert)(Right(0))     // None

codiagonalは対角射 $\alpha\rightarrow\alpha\times\alpha$ の双対で $\alpha+\alpha\rightarrow\alpha$ のような型になるが、要するにRightとLeftの型が同じ場合に中身をとりだすもの。

choice.codiagonal("abc".asRight[String])  // Some(abc)
choice.codiagonal("error".asLeft[String]) // Some(error)

Profunctor

Profunctorのdimapは以前の記事で調べたように、fabにfとgを足してCからDへの射を求めるもの。lmapとrmapは以下のような片側だけの射の合成になる。

以下のように書ける。

val prof = Profunctor[KleisliOption]

val l = (s: String) => s.toInt
val r = (d: Double) => s"${d * 100}%"

prof.dimap[Int, Double, String, String](invert)(l)(r)("5") // Some(20.0%)
prof.lmap[Int, Double, String](invert)(l)("10")            // Some(0.1)
prof.rmap[Int, Double, String](invert)(r)(2)               // Some(50.0%)

Strong

Profunctorを継承したStrongは、Hackage のData.Profunctor.Strongの記述によると、"Generalizing Star of a strong Functor"であって、Arrows are Strong Monadsという論文で記述されているというが、正直ピンとこない。

ただし、提供される関数first、secondの型は簡単で以下のように図示できる。

firstとsecondのそれぞれの出力を合成すると射の積になるが、次に説明するArrow#splitと同じものになる。

val strong = Strong[KleisliOption]

strong.first(invert).run((10, 0.5))        // Some((0.1, 0.5))
strong.second(toPercentile).run((10, 0.5)) // Some((10,  50%))

(strong.first(invert) >>> strong.second(toPercentile))
  .run((10, 0.5))                          // Some((0.1, 50%))

Arrow

StrongとCategoryを継承したArrowでは、さらにlift、split、mergeが加わる。Arrow[F].liftは、関数A=>BをF[A, B]にリフトする。

val arrow = Arrow[KleisliOption]
val length = arrow.lift((s: String) => s.length)

splitとmergeは、それぞれ射$f$, $g$を合成して下図のように$f\times g$や$h$を導く。

Arrow構文として、splitに***、mergeに&&&が提供されていて、以下のように書ける。

arrow.split(invert, length)((10, "test")) // Some((0.1, 4))
arrow.merge(length, toInt)("123")         // Some((3, 123))

(invert *** length *** toPercentile).run(((10, "test"), 0.01))
                                          // Some(((0.1, 4), 1.0%))
(length &&& toInt).run("-")               // None

ArrowChoice

ArrowとChoiceを継承したものがArrowChoiceで、choose、left、rightを提供する。

chooseには構文+++も提供されていて、以下のように書ける。

val arrowChoice = ArrowChoice[KleisliOption]

arrowChoice.choose(invert)(length)(Left(10)) // Some(Left(0.1))
(invert +++ length)(Right("right"))          // Some(Right(5))

arrowChoice.left(invert)(Left(10))           // Some(Left(0.1))
length right Right("right")                  // Some(Right(5))

規則性

ここまでで、いくつか対になりそうな関数のペアがみられた。対応関係をまとめると下表のようになる。

関数1	型1	~	関数2	型2
Arrow#merge	(A→B)→(A→C)→(A→B×C)	~	Choice#choice	(A→C)→(B→C)→(A+B→C)
Arrow#split	(A→B)→(C→D)→(A×C→B×D)	~	ArrowChoice#choose	(A→B)→(C→D)→(A+C→B+D)
Strong#first	(A→B)→(A×C)→(B×C)	~	ArrowChoice#left	(A→B)→(A+C)→(B+C)
Strong#second	(A→B)→(C×A)→(C×B)	~	ArrowChoice#right	(A→B)→(C+A)→(C+B)

まとめ

$g\circ f$やandThenだけじゃなく、いろんな合成パターンがある。
図に描いてみると意外と規則性が見えてくる。