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だけじゃなく、いろんな合成パターンがある。 - 図に描いてみると意外と規則性が見えてくる。