Help us understand the problem. What is going on with this article?

Arrowまわりの射の合成いろいろ

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パッケージのArrowCategoryといった型クラスで、いろいろなパターンの合成が提供されているらしい。今回はこれを調べてみた。

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

Arrow の階層

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

arrow-hierarchy.png

以降、これらの型クラスを観察しながら素振りしてみる(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では、異なる向きで射を合成するcomposeandThenが提供されている。また、各々に対応する構文<<<>>>が、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

algebraKalgebraは、それぞれSemigroupKSemigroupを返す。型パラメータの位置が違うだけで内容は変わらない。半群の結合的二項演算は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)

algebraKalgebraは、MonoidKMonoidを返す。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を提供する。圏論でいう余積の説明でよく見る構造になっている。

coproduct.png

図の右のようにtoDoubleinvertを合成して、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$ のような型になるが、要するにRightLeftの型が同じ場合に中身をとりだすもの。

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

Profunctor

Profunctordimap以前の記事で調べたように、fabfgを足してCからDへの射を求めるもの。lmaprmapは以下のような片側だけの射の合成になる。

profunctor2.png

以下のように書ける。

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という論文で記述されているというが、正直ピンとこない。

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

firstsecondのそれぞれの出力を合成すると射の積になるが、次に説明する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

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

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

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

arrow2.png

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

ArrowChoiceを継承したものがArrowChoiceで、chooseleftrightを提供する。
arrowchoice.png

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だけじゃなく、いろんな合成パターンがある。
  • 図に描いてみると意外と規則性が見えてくる。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away