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

Milewski 氏の圏論講座の[第1章 Category: The Essence of Composition](https://bartoszmilewski.com/2014/11/04/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。ソースは[ここ](https://gist.github.com/yasuabe/3a11d9ad827f104feefb45785c3e0bbd))



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

![arrow-hierarchy.png](https://qiita-image-store.s3.amazonaws.com/0/9633/2a597876-fd2a-9c0c-e04b-327699c38163.png)


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

## 方針

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

```scala
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`で定義されている。

```scala
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`になる。

```scala
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`と合わせて、ここで圏の構成要素がそろう。

```scala
val cat = Category[KleisliOption]
cat.id[String].run("foo")  // Some(foo)
```
`algebraK`と`algebra`は、`MonoidK`と`Monoid`を返す。`Compose`では半群だったが`Category`では恒等射を単位元とするモノイドになる。

```scala
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](https://qiita-image-store.s3.amazonaws.com/0/9633/16e3760b-1313-21aa-b75e-c80e031f4178.png)

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


```scala
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`の型が同じ場合に中身をとりだすもの。

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

## Profunctor
`Profunctor`の`dimap`は[以前の記事](https://qiita.com/yasuabe2613/items/ffb075eac360a013964a)で調べたように、`fab`に`f`と`g`を足して`C`から`D`への射を求めるもの。`lmap`と`rmap`は以下のような片側だけの射の合成になる。

![profunctor2.png](https://qiita-image-store.s3.amazonaws.com/0/9633/302492c2-328e-d999-fe94-c697380c186b.png)

以下のように書ける。

```scala
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](http://www-kb.is.s.u-tokyo.ac.jp/~asada/papers/arrStrMnd.pdf)という論文で記述されているというが、正直ピンとこない。

ただし、提供される関数`first`、`second`の型は簡単で以下のように図示できる。
![strong.png](https://qiita-image-store.s3.amazonaws.com/0/9633/848bfeca-d479-134d-2ede-2ee7af45f735.png)

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

```scala
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]`にリフトする。

```scala
val arrow = Arrow[KleisliOption]
val length = arrow.lift((s: String) => s.length)
```
`split`と`merge`は、それぞれ射$f$, $g$を合成して下図のように$f\times g$や$h$を導く。

![arrow2.png](https://qiita-image-store.s3.amazonaws.com/0/9633/1ee9f5a8-4580-0fd5-1a69-050827bb73c6.png)


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

```scala
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`を提供する。
![arrowchoice.png](https://qiita-image-store.s3.amazonaws.com/0/9633/b5208eb2-2971-aab7-89a0-93db7aff2619.png)

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

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