Haskell の Arrow tutorial の Scalaによる試行

最近では DDD 関連で語られることもある Functional Reactive Programming (FRP)の分野では、`Arrow`がよく使われてるという。[Arrows-based FRP](https://wiki.haskell.org/Arrows-based_Functional_Reactive_Programming) といった呼び方もあるらしい。

ただ、Scalaのライブラリに入っているのを見たことはあるけど、今まで使ったことがない。そこで今後の予習もかねて、Cats に入っている `Arrow` で素振りしてみる。お題は、Haskellの [Arrow tutorial](https://wiki.haskell.org/Arrow_tutorial) を選んでみた。

ちなみに自分は初見時やや混同したけど、圏論で「射(morphism)は〜で矢印(arrow)とも呼ばれる」といった文脈での *arrow* とこの`Arrow` は別のもので([参考](https://ncatlab.org/nlab/show/arrow))、Freyd-category という圏の一種らしい。ただしここでは深入りせず、monad の *generalization* としての単なる型クラスの一つといった程度の理解で先に進む。

## 依存関係など
Scala 3.1.2 と Cats 2.6.1
[詳細](https://github.com/yasuabe/qiita-cats3-sample/blob/main/build.sbt)

## 1. The Arrow
チュートリアルの[「1. The Arrow」](https://wiki.haskell.org/Arrow_tutorial#The_Arrow)では Haskellの`Control.Arrow`から、`arr`、`>>>`、`first`、`second`、が紹介されている。これを順に試してみる。

※ Cats では `Arrow` に関連して以下のような継承関係があること踏まえておく。

```
Compose    <-- Category <--┐
                           ├─ Arrow
Profunctor <-- Strong   <-─┘ 
```

### arr

```haskell
arr :: (Arrow a) => (b -> c) -> a b c
```
Cats では`Arrow#lift`が対応する。Cats で提供される `Arrow[Function]` インスタンスを使うと、以下のようになる。

```scala
val f1 = Arrow[Function].lift(1d / (_: Int))
f1(10) // res0: Double = 0.1
```

### >>>
```haskell
(>>>) :: (Arrow a) => a b c -> a c d -> a b d
```
Haskellの`(>>>)`は、Cats では`Compose#andThen` のエイリアスとして提供される。同様に、これと逆向きの `Compose#compose` にもエイリアス`<<<`が提供される。これらは`import　cats.syntax.compose._`で使えるようになる。

```scala
val f2: Int => String = (1d / (_: Int)) >>> (s => s"$s%")
f2(10) // res1: String = 0.1%
```

### first と second
```haskell
first :: (Arrow a) => a b c -> a (b, d) (c, d)
second :: (Arrow a) => a b c -> a (d, b) (d, c)
```

`first`と `second`は、Cats では `Strong`で定義されている。

```scala
val f3: ((Int, String)) => (Double, String) = (1d / (_: Int)).first[String]
f3((10, "ten")) // (0.1, ten)

val f4: ((Int, Double)) => (Int, String) = ((_: Double).toString.reverse).second[Int]
f4((10, 3.14)) // (10, 41.3)
```

上記 `>>>`、`first`、`second`を以下のよう組み合わせることもできる。

```scala
val f5: ((Int, Double)) => (Double, String) =
  (1d / (_: Int)).first >>> ((_: Double).toString.reverse).second
f5((10, 3.14)) // (0.1, 41.3)
```

ちなみに Cats では、`Function`以外にも`Kleisli`と`Cokleisli`のインスタンスが定義されており、例えば`Cokleisli`なら以下のように書ける。

```scala
def f6(using A: Arrow[[A, B] =>> Cokleisli[NonEmptyList, A, B]]) =
  A.lift[String, Int](_.length)
f6.run(NonEmptyList.of("abc", "ab", "c")) // 3
```

[worksheet](https://github.com/yasuabe/qiita-cats3-sample/blob/main/src/main/scala/arrow_tutorials/tutorial01.worksheet.sc)

## 2. A Simple Arrow
[「2. A Simple Arrow」](https://wiki.haskell.org/Arrow_tutorial#A_Simple_Arrow)では`SimpleFunc`という型を定義して、その`Arrow`インスタンスを作っている。

```scala
sealed case class SimpleFunc[A, B](runF: A => B)

given Arrow[SimpleFunc] with 
  def lift[A, B](f: A => B): SimpleFunc[A, B] = SimpleFunc(f)

  def first[A, B, C](fa: SimpleFunc[A, B]): SimpleFunc[(A, C), (B, C)] =
    SimpleFunc((a, c) => (fa runF a , c))

  def compose[A, B, C](g: SimpleFunc[B, C], f: SimpleFunc[A, B]): SimpleFunc[A, C] =
    SimpleFunc(g.runF compose f.runF)
```
Cats で `Arrow`を実装すると、チュートリアルの Haskell コードと以下の点で違いが出る。

- チュートリアルでは別途 `Category`のインスタンスも書いているが、Catsでは `Arrow`が `Category`を継承しているため不要。
- `second`ではなく`Category#compose`を実装することで自動的に`second`も定まり、逆に`Category#id`は`Arrow側`で`lift`を実装することで自動的に定まる。

[worksheet](https://github.com/yasuabe/qiita-cats3-sample/blob/main/src/main/scala/arrow_tutorials/tutorial02.worksheet.sc)

## 3. Some Arrow Operations
[「3. Some Arrow Operations」](https://wiki.haskell.org/Arrow_tutorial#Some_Arrow_Operations)では、`Arrow`で一般的に使える関数をいくつか定義している。以下順に見てみる。

### split / unsplit
以下、チュートリアルのと同等な`split`、`unsplit`のコード。可読性のためとチュートリアルのコードに近づけるために`arr`も定義した。

```scala
def arr[F[_, _]: Arrow, A, B](f: A => B): F[A, B] = Arrow[F] lift f
def split[F[_, _]: Arrow, A]: F[A, (A, A)]        = arr(x => (x, x))
def unsplit[F[_, _]: Arrow, A, B, C](f: (A, B) => C): F[(A, B), C] =
  arr(f.tupled)
```

### *** / &&&
`***`は `Arrow#split`の、`&&&`は `Arrow#merge`のエイリアスになっている（名前は同じだが `Arrow#split` と上で独自実装した`split`は別物。

### liftA2
チュートリアルで紹介されている２通りの書き方が、Scalaでも同様に書ける。

```scala
def liftA2[F[_, _]: Arrow, A, B, C, D](f: (B, C) => D, fb: F[A, B], fc: F[A, C])
  : F[A, D] = (fb &&& fc) >>> unsplit(f)

```

```scala
def liftA2[F[_, _]: Arrow, A, B, C, D](f: (B, C) => D, fb: F[A, B], fc: F[A, C])
  : F[A, D] = split[F, A] >>> fb.first >>> fc.second >>> unsplit(f)
```

`&&&` は `import cats.syntax.arrow._`で使える。
[worksheet](https://github.com/yasuabe/qiita-cats3-sample/blob/main/src/main/scala/arrow_tutorials/tutorial02.worksheet.sc)

## 4. An Example
[「4. An Example」](https://wiki.haskell.org/Arrow_tutorial#Some_Arrow_Operations)では、ここまでのコードを使って`SimpleFunc`を動かしている。Scalaでは以下のようになる。

```scala
val f: SimpleFunc[Int, Int] = arr(_ / 2)
val g: SimpleFunc[Int, Int] = arr(_ * 3 + 1)
val plus: (Int, Int) => Int = _ + _

val h = liftA2(plus, f, g)
h runF 8 // : Int = 29
```
チュートリアルと同様の結果が得られる。
[worksheet](https://github.com/yasuabe/qiita-cats3-sample/blob/main/src/main/scala/arrow_tutorials/tutorial02.worksheet.sc)

## 5. Kleisli Arrows
`Kleisli`はふだん`ReaderT`として使うことも多いが、[「5. Kleisli Arrows」](https://wiki.haskell.org/Arrow_tutorial#Kleisli_Arrows)では`Arrow`としての用法が示される。Cats で提供されている`Kleisli`の `Arrow`インスタンスを使って同等な Scalaコードを書いた。

```scala
type Arr = Kleisli[List, Int, Int]
val plusMinus: Arr = Kleisli(x => x :: (-x) :: Nil)
val double   : Arr = arr(_ * 2)
val h2       : Arr = liftA2((_: Int) + (_: Int), plusMinus, double)

h2 run 8 // : List[Int] = List(24, 8)
```
計算の流れは 8→(8,8)→([8,-8], 16)→[24, 8]となり、チュートリアルと同じ。

([Haskell の Arrow](https://en.wikibooks.org/wiki/Haskell/Arrows)の`proc a -> returnA -< a`のような構文は現状の Catsには見当たらない。)

[worksheet](https://github.com/yasuabe/qiita-cats3-sample/blob/main/src/main/scala/arrow_tutorials/tutorial03.worksheet.sc)

## 6. A Teaser
[「6. A Teaser」](https://wiki.haskell.org/Arrow_tutorial#A_Teaser)では、Haskellの`Control.Arrow`で定義されている`returnA`と`<+>`を使った応用例が示されている。ここでは`returnA`も`<+>`も自前で定義した。

```scala
def returnA[S] = Arrow[ListKleisli].id[S]

extension [X[_], S](k1: Kleisli[X, S, S])(using M: Semigroup[X[S]])
  def <+>(k2: Kleisli[X, S, S]) = Kleisli((s: S) => k1.run(s) |+| k2.run(s))
```

`main`相当は以下。

```scala
val arrK = f => arr[ListKleisli, String, String](f)

val prepend = (s: String)                      => arrK(s ++ _)
val append  = (s: String)                      => arrK(_ ++ s)
val withId  = (t: ListKleisli[String, String]) => returnA[String] <+> t

val xform = withId(prepend("<"))
        >>> withId(append(">"))
        >>> withId(prepend("!")
        >>> append("!"))

List("test", "foo") >>= xform.run
```

チュートリアルにも'important observation'と注意喚起されてるように、結果の組み合わせがちょっと面白い。

```
test, !test!, test>, !test>!, <test, !<test!, <test>, !<test>!, 
foo, !foo!, foo>, !foo>!, <foo, !<foo!, <foo>, !<foo>!
```
[worksheet](https://github.com/yasuabe/qiita-cats3-sample/blob/main/src/main/scala/arrow_tutorials/tutorial04.worksheet.sc)

## 所感・TODOなど
- 今回はただの型クラスとして触ってみただけだけど、次は Arrow-Based FRPの中での使われ方もみてみる。
- 冒頭で書いた通り、`Arrow`は"Freyd-categories"とも呼ばれ、Catsでも`Category`を継承している。数学的な背景もある概念らしいので、モナドとの対比も含めて調べておきたい。
- Haskell界隈では、GHCの Arrows 拡張で有効になる[ノーテーション](http://www.staff.city.ac.uk/~ross/papers/notation.pdf)など表現力の面で語られることが多いようなので、これも Scala でどうなるか調べてみたい。
- Scala3 を使って書き直した。[旧 Scala 版](https://qiita.com/yasuabe2613/items/d2ffd775804be52a20ad/revisions/6?type=preview)くらべるとかなりスッキリ書けている気がする。 (2022/05/21)