シンプルな型 Pair[A]=(A, A) でいろいろな型クラスを実装してみる

とても簡単でわかりやすいデータ型 `Pair[A]=(A, A)` （同じ型の値のペア）について、Functor, Applicative, Monad, Traverse などを実装して型クラスを理解する Cats 入門者向け記事。

## はじめに
たとえば (10, 20) というデータに、「2倍する」という関数を適用すると、直感的には (20, 40) になると考えるのが自然ではないだろうか。たぶん高校数学などでも「ベクトルのスカラー倍」のような形でなじみがある計算ではないかと思う。

同様に("abc", "de")に「文字列の長さ」という関数を適用すると(3, 2) が得られるのも、なんとなく自然な類推ではないだろうかと思う。

考え方としては、ペアの両方の値に同じ関数を単純に適用しているだけなのだけど、(1)ペアになっている値は同じ型であり、(2)関数を適用したあともペアであることは保たれるという暗黙の前提に注意して、ちょっと抽象的に書いてみると以下のようになる。

> f: A → B と Pair[A] から、Pair[B] を得た。 あるいは f: A→B から、Pair[A] → Pair[B] を得た。

これと同じ形の操作を、Scala 標準のデータ型でも `List` や `Option` などの `map` として提供しているが、この共通性を [Cats](https://typelevel.org/cats/) では `Functor` という型クラスに抽象化して、統一的な操作を提供している。この `Functor` として正式に認められるためには、Cats が要請するルールセットを `List` や `Option` と同様に満たさなければいけないが、後にみるように Pair もちゃんとそれを充足する。

実は Pair は、`Functor` 以外にもいろいろな型クラスインスタンスが書ける。実際に書いてみると、成立する型クラスが思っていたよりも多くて、面白かったので紹介したい。

## 進め方

### 対象
Cats にはいくつかの型クラス群があるが、`F[_]` を型パラメータにとる以下の階層に含まれるものについて、Pair のインスタンスを作ってみた[^other-typeclasses]。先に結論を書いてしまうと、緑のティックが付いているものが型クラスのインスタンスが定義できたもので、赤のクロスが付いているものができなかったものになる[^original-picture]。


![cats-typeclasses.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/9633/6531fd12-eb37-4ded-fd62-abb88d1432d3.png)

意外と多いと思ったのではないだろうか（自分はそうだった）。この後、一つずつ確認してみる。

### 趣向
- もともと Cats の型クラス階層は、「非力だが制約の少ない」型クラスを頂点として、薄皮をかさねるように「強力だが制約の多い」型クラスに至るように構成されているが、この記事でもそれをなぞって少しずつ進める。
- 実装コードを `???` で伏せたクイズのような形にして、実装例は畳み込んでおいた。一瞬考えてから実装例を見てみると、Pair でどう実装するかだけではなく、それぞれの型クラス固有の要請についての理解につながるのではないかと思う。[^about-quiz]
- 一番かんたんで自明な `Functor` を 1、個人的に一番難しかった `FlatMap#tailRecM` を 5として、難度を表示しておいた。といっても、たかが二つの値のペアなので、難度=5 でもある程度考えれば分かるレベルだと思う。
- 型クラスごとに Cats が提供するルールセットを使って、それぞれの法則を Discipline テストで検証した。ただし、ルールセットを個別に解説するのはこの記事ではやめておいた[^about-ruleset]。

### 実装
以下の型 `Pair` から、いろいろな型クラスを実装してみる。

```scala
type Pair[A] = (A, A)
```
たとえば `Functor` なら以下のようなものになる。

```scala
trait PairFunctor extends Functor[Pair] { ... }
```
さらに、以下のように Discipline を使ったテストも書く。ただしこの記事には載せずリンクだけ貼っておく。

```scala
class PairFunctorTests extends DisciplineSuite:
  given Functor[Pair] = new PairFunctor {}
  checkAll("Pair.FunctorLaws", FunctorTests[Pair].functor[Int, Int, String])
```
- Scala は 2.13.1、Cats は 2.0.0 を使った。
- 型クラスのインスタンス群のソースは[ここ](https://github.com/yasuabe/qiita-cats3-sample/blob/main/src/main/scala/type_class_instances_for_pair/PairInstances.scala)
- 型クラスのインスタンス群のテストコードは[ここ](https://github.com/yasuabe/qiita-cats3-sample/blob/main/src/test/scala/type_class_instances_for_pair/PairTest.scala)

## Functor まわり
ここでは Invariant, Functor, Contravariant インスタンスを作ってみる。

### Invariant
知名度があまり高くないかもしれないが、この`Invariant` は Cats の型クラス群の頂点の一つで、階層的に `Functor` の一つ上に当たる。したがって、モナド、アプリカティブ、Traverse など `Functor` の下層にある型クラス群は、自動的に `Invariant` の性質も持っていることになる。

と言ってもむずかしいものではなく、`A => B` か `B => A` か、どちらかの関数があれば `F[A] => F[B]` が得られるような性質を表現できればよくて、Scala コードとしては下記のシグネーチャの `imap` を書くことになる。

```scala
trait Invariant[F[_]]:
  def imap[A, B](fa: F[A])(f: A => B)(g: B => A): F[B]
  ...
```
`Pair` なら以下を実装することになるが、どう書けるだろうか？（難度=2）

```scala
trait PairInvariant extends Invariant[Pair]:
  def imap[A, B](fa: (A, A))(f: A => B)(g: B => A): (B, B) = ???
```

<details><summary>実装例</summary><div>

```scala
def imap[A, B](fa: (A, A))(f: A => B)(g: B => A): (B, B) = fa match
  case (a1, a2) => (f(a1), f(a2))
```
</div>
簡単だけど、もしかすると `g` をどうやって使えばよいか悩んだかもしれない。単に捨てるだけでよくて、これで Discipline テストがちゃんと通る。
</details>


### Functor
`Invariant` を継承して、以下のシグネーチャの `map` を追加すると `Functor` ができあがる。

```scala
trait Functor[F[_]] extends Invariant[F]:
  def map[A, B](fa: F[A])(f: A => B): F[B]
  ...
```
Option や List などの操作で、普通の Scala コーディングでも頻繁に使う `map` が `Functor` に関連していて、Cats の型クラスの中でも特に馴染み深いものだと思う。

Pair なら以下の `map` を実装すればよい。どう書けるだろうか？（難度=1）

```scala
trait PairFunctor extends Functor[Pair] with PairInvariant:
  def map[A, B](fa: (A, A))(f: A => B): (B, B) = ???
```
<details><summary>実装例</summary><div>

```scala
override def map[A, B](fa: (A, A))(f: A => B): (B, B) = fa match
  case (a1, a2) => (f(a1), f(a2))
```
</div>
冒頭に書いたスカラー倍の問題そのもので、これは簡単だと思う。結局、Invariant と同じになる。
</details>


### Contravariant
`Invariant` に下記のような `contramap` を追加すると、`Contravariant` になる。

```scala
trait Contravariant[F[_]] extends Invariant[F]:
  def contramap[A, B](fa: F[A])(f: B => A): F[B]
  ...
```

ただし `B => A` から `(A, A) => (B, B)` を得るのは無理なので、どうやら`Contravariant[Pair]` は実装できない[^contravariant-memo]。
[^contravariant-memo]: `Contravariant` に馴染みがない人は、逆にどういう`F[_]` が `Contravariant` になるのか考えてみると理解が深まるかもしれない。

## Semigroupal まわり
`F[_]` をあつかう型クラスの頂点の一つに、`Semigroupal` がある。ここでは `Semigroupal`以下、`InvariantSemigroupal`、`InvariantMonoidal`、`ContravariantSemigroupal`、`ContravariantMonoidal`を見てみる。

### Semigroupal
`Semigroupal` は、`F[_]` の中で型の積を作るような操作を提供する。以下のシグネーチャの `product` メソッドを実装する。

```scala
trait Semigroupal[F[_]]:
  def product[A, B](fa: F[A], fb: F[B]): F[(A, B)]
  ...
```
Pair の場合は以下を実装すれば良いが、どうなるだろうか。(難度=2)。

```scala
trait PairSemigroupal extends Semigroupal[Pair]:
  def product[A, B](fa: (A, A), fb: (B, B)): ((A, B), (A, B)) = ???
```
<details><summary>実装例</summary><div>

```scala
def product[A, B](fa: (A, A), fb: (B, B)): ((A, B), (A, B)) = (fa, fb) match
  case ((a1, a2), (b1, b2)) => ((a1, b1), (a2, b2))
```
</div>
素朴に `_1`同士、`_2`同士をペアにすれば良い。行列の転置のような操作になる。
</details>

#### InvariantSemigroupal
`Semigroupal` と `Invariant` を合わせると`InvariantSemigroupal` となるが、ここまでに作った `PairSemigroupal` と `PairInvariant` を合成するだけでよくて、Discipline が要求する ルールセットも自然と満たされる。

```scala
trait PairInvariantSemigroupal
  extends InvariantSemigroupal[Pair] with PairSemigroupal with PairInvariant
```

### InvariantMonoidal
`InvariantSemigroupal` に `unit: F[Unit]` を追加した型クラスが `InvariantMonoidal` となる。`Pair` の場合、型`(Unit, Unit)`の値を作ればよいが、どう書けるだろうか？（難度=２）

```scala
trait PairInvariantMonoidal extends InvariantMonoidal[Pair] with PairInvariantSemigroupal:
  def unit: (Unit, Unit) = ???
```
<details><summary>実装例</summary><div>

```scala
def unit: (Unit, Unit) = ((), ())
```
</div>
`Unit` の値がわからなければ、もしかすると悩んだかもしれない。
</details>

### ContravariantSemigroupal, ContravariantMonoidal
`ContravariantSemigroupal` は `Contravariant` を継承するが、上で見たように `Contravariant[Pair]` は定義できない。このため `ContravariantSemigroupal[Pair]` も定義できず、また`ContravariantSemigroupal[Pair]` を継承する`ContravariantMonoidal[Pair]` も定義できないということになる。

## Applivative 〜 Monad など
ここまでに見た、`Functor` と `Semigroupal` から新たな型クラス `Apply` が定義でき、その下の型クラス階層に `Applicative` や `Monad` といった有名な型クラスが構成される。ここでも一歩ずつ順に見てみる。

### Apply
`Functor` と `Semigroupal` を合成して[^actually-invariant]、さらに `F[A => B]` から `F[A] => F[B]` が得られる性質を付け加えると `Apply` になる。簡潔にした実装は以下のようなもの。

```scala
trait Apply[F[_]] extends Functor[F] with InvariantSemigroupal[F]:
  def ap[A, B](ff: F[A => B])(fa: F[A]): F[B]
  ...
```
後述の `Applicative` を知っていれば、`Applicative` の `pure` がないものと考えることもできる（`Semigroup` が `empty` のない `Monoid` と理解できるのと同様に）。
 
`Pair`の場合、以下を実装すればよい。どう書けばよいだろか（難度=3）？

```scala
trait PairApply extends Apply[Pair] with PairFunctor:
  def ap[A, B](ff: (A => B, A => B))(fa: (A, A)): (B, B) = ???
```
<details><summary>実装例</summary><div>

```scala
def ap[A, B](ff: (A => B, A => B))(fa: (A, A)): (B, B) = (ff, fa) match
  case ((f1, f2), (a1, a2)) => (f1(a1), f2(a2))
```
</div>
関数のペアと型Aのペアで、`_1`同士と `_2`同士を自然に適用する。ちなみに `(f2(a1), f1(a2))` と書くと、コンパイルすることはできるが、Discipline テストで失敗する。
</details>

#### CommutativeApply
上述の通り `Apply`は `Semigroupal`を継承しているが、`Semigroupal#product`と `Apply#ap`を組み合わせると、下記のようなシグネーチャをもつ `map2` が得られる。

```scala
def map2[A, B, Z](fa: F[A], fb: F[B])(f: (A, B) => Z): F[Z]
```
この `map2` が可換となるような `Apply` が `CommutativeApply` となる。

ただし `Pair` の場合は、自然と可換性が成立して Discipline テストも成功する。

```scala
trait PairCommutativeApply extends CommutativeApply[Pair] with PairApply
```

### Applicative
`A` を `F[_]` の文脈にのせる操作 `pure` を `Apply` に追加したものが、`Applicative` になる。だから、もし「Applicative とは何か？」と聞かれるようなことがあったら、Scala+Cats 的には「Apply に pure を付け加えたものですが、なにか問題でも？」と、簡潔に答えることができる。

細部を省略したシグネーチャは以下のようなものになる（※ `pure(())` により `unit`が提供できるので、実際の実装では`InvariantMonoidal` も継承する形になっている）。

```scala
trait Applicative[F[_]] extends Apply[F]:
  def pure[A](x: A): F[A]
  ...
```

`pure` の実装は、例えば `List` や`Option` ならば、与えられた `a:A` について、それぞれ `List(a)`、`Some(a)` だが、`Pair` の場合はどうだろうか？(難度=3)

```scala
trait PairApplicative extends Applicative[Pair] with PairApply:
  def pure[A](a: A): (A, A) = ???
```
<details><summary>実装例</summary><div>

```scala
def pure[A](a: A): (A, A) = (a, a)
```
</div>
サイズ２固定のコレクションを `a` でフィルするようなイメージの直感的な実装で、Discipline テストがちゃんと通る。
</details>

#### CommutativeApplicative
`CommutativeApply` と `Applicative` を合成すると `CommutativeApplicative` になる。`Pair` の場合、単に多重継承するだけで、それぞれの法則が満たされるようになる。特に追加のメソッドを実装する必要もない。

```scala
trait PairCommutativeApply extends CommutativeApply[Pair] with PairApply
```

### FlatMap
だんだんモナドに近づいてきた。

Cats では、`Apply`に下記シグネーチャの `flatMap`, `tailRecM` を付け加えると `FlatMap`となる[^tail-rec-m]。

```scala
trait FlatMap[F[_]] extends Apply[F]:
  def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]
  def tailRecM[A, B](a: A)(f: A => F[Either[A, B]]): F[B]
```
別々に見てみる。まず `flatMap`から。

おさらいすると、`F[A] => F[B]`を得る前提として `A => B` が使えるのが `Functor`、さらに`F[A => B]`も使えるのが `Apply`(`Applicative`)だった。ここでさらに `A => F[B]` も使えるのが `FlatMap`(そして後述の`Monad`) になる。

`Pair` の場合、以下を実装すればよい。どう書けるだろうか？(難度=４)

```scala
trait PairFlatMap extends FlatMap[Pair] with PairApply:
  def flatMap[A, B](fa: (A, A))(f: A => (B, B)): (B, B) = ???
...
```
[^tail-rec-m]: 個人的には、代数的性質から要請される `flatMap` と、実装都合の `tailRecM` が同じトレイトに含まれるのは、異なる関心事が混在してしまっている気がする。Scalaz ではたしかちゃんと分離されていた。

<details><summary>実装例</summary><div>

```scala
def flatMap[A, B](fa: (A, A))(f: A => (B, B)): (B, B) = map(fa)(f) match
  case ((b1, _), (_, b2)) => (b1, b2)
```
</div>
`fa:(A,A)` の二つの A値にそれぞれ f を関数適用すると(map)、得られる型は `((B,B),(B,B))` となるから、これを`(B, B)`にする必要がある。言い換えると `Pair[Pair[B]]` を平らにして `Pair[B]` にしている訳で、これが `FlatMap` の "flat" たるゆえんでもあるが、ここでは両端の要素だけを残すことで実現している。値を捨てちゃって良いのだろうかと心配になるが、これでちゃんと Discipline テストも通る。
</details>

次に `tailRecM` を見てみる。これは代数や圏論からの要請というより、スタックセーフを実現するための実装上の仕組みで、シグネーチャを再掲すると下のようなものだった。

```scala
def tailRecM[A, B](a: A)(f: A => F[Either[A, B]]): F[B]
```
関数`f` の使い方としては、`f(a)` の結果が Right 値なら結果に含めて、Left値なら再び `f` を適用して計算を継続するようにすればいい。ただし、うまく末尾再帰を構成してスタックオーバーフローを防ぐ必要がある。

`Pair` なら以下を実装すればよいが、どうなるだろうか？(難度=５)

```scala
trait PairFlatMap extends FlatMap[Pair] with PairApply:
...
  def tailRecM[A, B](a: A)(f: A => (Either[A, B], Either[A, B])): (B, B) = ???
```
<details><summary>実装例</summary><div>
先に失敗例を示すと以下のようになる。

```scala
def tailRecM[A, B](a: A)(f: A => (Either[A, B], Either[A, B])): (B, B) = f(a) match
  case (Right(b1), Right(b2)) => (b1,                 b2)
  case (Left(a1),  Right(b2)) => (tailRecM(a1)(f)._1, b2)
  case (Right(b1), Left(a2))  => (b1,                 tailRecM(a2)(f)._2)
  case (Left(a1),  Left(a2))  => (tailRecM(a1)(f)._1, tailRecM(a2)(f)._2)
```
この実装だと、計算結果の値自体には問題がないが、末尾再帰にならないのでスタックセーフティが得られない。実際にスタックオーバーフローが発生するのは、この FlatMap のルールセットではなくて次のモナドのルールセットだけど、`tailRecM` の実装なのだからちゃんと tailrec にしておきたい。

末尾再帰を構成したスタックセーフな実装例は、以下のようなものになる。

```scala
def tailRecM[A, B](a: A)(f: A => (Either[A, B], Either[A, B])): (B, B) =
  @scala.annotation.tailrec
  def first(a: A): B = f(a) match
    case (Right(b), _) => b
    case (Left(a),  _) => first(a)

  @scala.annotation.tailrec
  def second(a: A): B = f(a) match
    case (_, Right(b)) => b
    case (_, Left(a))  => second(a)

  (first(a), second(a))
```
</div>
</details>

#### CommutativeFlatMap
`Apply`、`Applicative` に、それぞれ対応する `CommutativeApply`、`CommutativeApplicative` があったように、`FlatMap` にも `CommutativeFlatMap` がある。Pair の場合、`CommutativeFlatMap[Pair]` も、`FlatMap` と `CommutativeApplicative` を継承するだけで、自然とDiscipline のルールセットを満たすようになる。

```scala
trait PairCommutativeFlatMap extends CommutativeFlatMap[Pair] with PairFlatMap with PairCommutativeApply
```

### Monad
`Applicative` と `FlatMap` を合成すると、それだけで `Monad` になってしまう。具体的には、`Applicative#pure` と、`FlatMap#flatMap`（と `tailRecM`）があれば `Monad` になって、Discipline が提供する「モナド則」も自然と満たされる。

数学的にモナドを理解しようとすると、よく知られている「モナドとは自己函（ry」にしても、随伴とかを使った構成にしても、それなりに段階を踏んで理解を積み上げていく必要があるけど、Scala+Cats での `Monad` は、ここまでで見たように単に `Applicative` と `FlatMap` を多重継承したトレイトにすぎず、予めお膳立てされた Discipline ルールセットについてテスト実行がグリーンになりさえすれば、プログラミング技術としては十分だったりする。

#### CommutativeMonad
`Apply`、`Applicative`、`FlatMap` に、それぞれ対応する Commutative版 があったように、`Monad` にも `CommutativeMonad` がある。Pair の場合も、下記のような継承構成で自然と Discipline のルールセットを満たす可換性が得られる。

```scala
trait PairCommutativeMonad extends CommutativeMonad[Pair]
  with PairMonad
  with PairCommutativeFlatMap
  with PairCommutativeApplicative
```

## Foldable〜Traverse まわり
Cats 型クラス階層の頂点の一つに `UnorderedFoldable` がある。階層の下の方には、わりとよく使われる `Foldable` や `Traverse` が含まれるが、ここでは `Pair[A]=(A, A)` をサイズ２固定のコレクション[^shapeless-sized]と捉えてインスタンスが作れるか試してみる。

### UnorderedFoldable
`UnorderedFoldable` では、以下のようなシグネーチャのメソッドを実装する。

```scala
def unorderedFoldMap[A, B: CommutativeMonoid](fa: F[A])(f: A => B): B
```

B が可換モノイドであることに注意して、Pair の場合ならば以下を実装すればよい。どのように書けるだろうか？（難度=3）

```scala
trait PairUnorderedFoldable extends UnorderedFoldable[Pair]:
  def unorderedFoldMap[A, B: CommutativeMonoid](fa: (A, A))(f: A => B): B = ???
```
<details><summary>実装例</summary><div>

```scala
def unorderedFoldMap[A, B: CommutativeMonoid](fa: (A, A))(f: A => B): B = fa match
  case (a1, a2) => f(a1) |+| f(a2)
```
</div>
`CommutativeMonoid` の意味が、単位元と可換な二項演算をもつことだとわかれば簡単だと思う。空がありうるような`F[_]`、たとえば List や Option なら単位元も利用することになるが、Pair の場合、空はありえないので二項演算のみを利用する。
</details>

### UnorderedTraverse
`UnorderedFoldable` に、以下のようなシグネーチャの `unorderedTraverse` を追加すると、`UnorderedTraverse` になる。

```scala
trait UnorderedTraverse[F[_]] extends UnorderedFoldable[F]:
  def unorderedTraverse[G[_]: CommutativeApplicative, A, B](sa: F[A])(f: A => G[B]): G[F[B]]
  ...
```
後述の `Traverse#traverse` と似ているが、G の型制約が `CommutativeApplicative` となっていて、`Traverse` が要請する`Applicative`より厳しいために、その分逆に型クラスとしては自由度が高く、型クラス階層で上の方に位置している。

Pair を`UnorderedTraverse` とするには以下を実装すればよいが、どうかけるだろうか？(難度=３)

```scala
trait PairUnorderedTraverse extends UnorderedTraverse[Pair] with PairUnorderedFoldable:
  def unorderedTraverse[G[_]: CommutativeApplicative, A, B](sa: (A, A))(f: A => G[B]): G[(B, B)] = ???
```
<details><summary>実装例</summary><div>

```scala
def unorderedTraverse[G[_]: CommutativeApplicative, A, B](sa: (A, A))(f: A => G[B]): G[(B, B)] =
  sa match
    case (a1, a2) => f(a1) product f(a2)
```
</div>
`CommutativeApplicative` を階層上の上にたどると `Semigroupal` に突き当たるので、そのメソッド `product` を使って `G[(B, B)]`を作れば良い。
</details>

### Foldable
`UnorderedFoldable` に `foldLeft` と `foldRight` を付け加えると `Foldable` になる。

```scala
trait Foldable[F[_]] extends UnorderedFoldable[F]:
  def foldLeft[A, B](fa: F[A], b: B)(f: (B, A) => B): B
  def foldRight[A, B](fa: F[A], lb: Eval[B])(f: (A, Eval[B]) => Eval[B]): Eval[B]
  ...
```
まず `foldLeft` から。Pair ならば以下を実装すればよいが、どうなるだろうか？（難度=2）

```scala
trait PairFoldable extends Foldable[Pair]:
  def foldLeft[A, B](fa: (A, A), b: B)(f: (B, A) => B): B = ???
  ...
```

<details><summary>実装例</summary><div>

```scala
def foldLeft[A, B](fa: (A, A), b: B)(f: (B, A) => B): B = fa match
  case (a1, a2) => f(f(b, a1), a2)
```
</div>
普通の Scala コードの List操作などから、簡単に類推できるのではないだろうか。
</details>


次に `foldRight`。こちらは `Eval` を使うので難度が高まる。遅延評価させるために、あえて導入している `Eval` なので、単に型合わせだけしてコンパイルを通しただけでは、Discipline テストで失敗する可能性がある。Pair の場合、以下を実装すればよいがどうなるか？（難度=4）


```scala
trait PairFoldable extends Foldable[Pair]:
  ...
  def foldRight[A, B](fa: (A, A), lb: Eval[B])(f: (A, Eval[B]) => Eval[B]): Eval[B] = ???
```

<details><summary>実装例</summary><div>

```scala
def foldRight[A, B](fa: (A, A), lb: Eval[B])(f: (A, Eval[B]) => Eval[B]): Eval[B] =
  fa match
    case (a1, a2) => Eval.defer(f(a1, Eval.defer(f(a2, lb))))
```
</div>
右から畳み込む操作自体は全然むずかしいものではないが、`Eval.defer` に気づかないとなかなか Discipline テストが通らないかもしれない。例えば `f(a1, f(a2, lb))` のようにしてしまうと、lazy であることを要求するいくつかのルールが満たされなくなる。
</details>


### Reducible
`Foldable` の *non empty* 版が `Reducible` で、下記シグネーチャの `reduceLeftTo`、`reduceRightTo` が追加される。

```scala
trait Reducible[F[_]] extends Foldable[F] { self =>
  def reduceLeftTo[A, B](fa: F[A])(f: A => B)(g: (B, A) => B): B
  def reduceRightTo[A, B](fa: F[A])(f: A => B)(g: (A, Eval[B]) => Eval[B]): Eval[B]
  ...
```
foldLeft/Right では初期値を明示的に与えていたが、reduceLeft/RightTo では、少なくとも１つのA型値があることを前提にしているので、初期値の代わりに `f: A=>B`を与える。Pair の場合は以下を実装すればよいがどうなるか？（難度=3）

```scala
trait PairReducible extends Reducible[Pair] with PairFoldable:
  def reduceLeftTo[A, B](fa: (A, A))(f: A => B)(g: (B, A) => B): B = ???
  def reduceRightTo[A, B](fa: (A, A))(f: A => B)(g: (A, Eval[B]) => Eval[B]): Eval[B] = ???
```

<details><summary>実装例</summary><div>

```scala
def reduceLeftTo[A, B](fa: (A, A))(f: A => B)(g: (B, A) => B): B = fa match
  case (a1, a2) => g(f(a1), a2)

def reduceRightTo[A, B](fa: (A, A))(f: A => B)(g: (A, Eval[B]) => Eval[B]): Eval[B] = fa match
  case (a1, a2) => g(a1, Eval.later(f(a2)))
```
</div>
`reduceRightTo` の `Eval.later` は`Eval.now` でも問題ない（多分。少なくとも Discipline 的にはグリーン）。
</details>

### Traverse
`Foldable`、`UnorderedTraverse`、`Functor` を継承して、さらにメソッド `traverse` を付け加えると、おなじみの `Traverse` になる。`traverse` のシグネーチャは以下のようなものだった。

```scala
trait Traverse[F[_]] extends Functor[F] with Foldable[F] with UnorderedTraverse[F]:
  def traverse[G[_]: Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]]
  ...
```
Pair の場合、下の未実装部分を書き足せば　`Traverse[Pair]` が得られるが、どう書けるだろうか？（難度=２）


```scala
trait PairTraverse extends Traverse[Pair] with PairFunctor with PairFoldable:
  def traverse[G[_]: Applicative, A, B](fa: (A, A))(f: A => G[B]): G[(B, B)] = ???
```

<details><summary>実装例</summary><div>

```scala
override def traverse[G[_]: Applicative, A, B](fa: (A, A))(f: A => G[B]): G[(B, B)] =
  fa match
    case (a1, a2) => f(a1) product f(a2)
```
</div>
`unorderedTraverse` と同じ実装で良いが、G の型制約が `traverse` の方がゆるいので、`traverse` の定義で `unorderedTraverse` を使うことはできない。逆に、`unorderedTraverse` の定義で `traverse` を使うことは可能。
</details>

### NonEmptyTraverse
`Traverse` にメソッド `nonEmptyTraverse` を追加すると、型クラス`NonEmptyTraverse`になる。`nonEmptyTraverse` は `traverse` と似ているが、`F[_]` が `NonEmpty` であることがわかっているため、型パラメータ `G`の制約が少し弱まり、`Applicative`から `Apply`になる。

Pair を `NonEmptyTraverse` にするには下記を実装すればよいが、どう書けるだろうか？(難度=2)

```scala
trait PairNonEmptyTraverse extends NonEmptyTraverse[Pair] with PairReducible:
  def nonEmptyTraverse[G[_]: Apply, A, B](fa: (A, A))(f: A => G[B]): G[(B, B)] = ???
```

<details><summary>実装例</summary><div>

```scala
def nonEmptyTraverse[G[_]: Apply, A, B](fa: (A, A))(f: A => G[B]): G[(B, B)] = fa match
  case (a1, a2) => f(a1) product f(a2)
```
</div>
もともと `traverse` でも `Applicative#pure` は使っていなかったので、結局まったく同じコードで済む。
</details>


## CoflatMap、Distributive など
`Functor` からの継承ラインのうち、`Apply`、`Traverse` 以外のものについて。

### CoflatMap
すでに見た `FlatMap`は `A => F[B]`から `F[A] => F[B]`を得るものだったが、これと逆の `F[A] => B`から `F[A] => F[B]` を得る性質を `Functor`に追加すると、`CoflatMap`となる。

```scala
trait CoflatMap[F[_]] extends Functor[F]:
  def coflatMap[A, B](fa: F[A])(f: F[A] => B): F[B]
  ...
```

Pair の場合、以下の未実装部分を書けばよいが、どうなるだろうか？(難度=3)

```scala
trait PairCoflatMap extends CoflatMap[Pair] with PairFunctor:
  def coflatMap[A, B](fa: (A, A))(f: ((A, A)) => B): (B, B) = ???
```
<details><summary>実装例</summary><div>

```scala
def coflatMap[A, B](fa: (A, A))(f: ((A, A)) => B): (B, B) =
  val x = f(fa)
  (x, x)
```
</div>
A のペアから`f`によって得られる B は1個だけだが、`Applicative#pure`と同じような考え方でタプルを埋めると、それで Discipline のルールセットも満たされる。
</details>

### Comonad, Bimonad
`Monad` の双対である `Comonad` を得るには、上で書いた `flatMap` の双対の `coflatMap`と、あとは `pure: A => (A, A)` の双対の `extract: (A, A) => A`が書ければよい。

単純に考えると、`_1`か`_2`を返せば良さそうに思えるが、しかし実はこれだと Comonad のルールセットを満たせない（例えば、coflatMap と extract を組み合わせると、元の (A, A) に復元できるといったプロパティがある）。なので `Comonad[Pair]` は成立しない。従ってまた、`Comonad` を継承とする `Bimonad` も成立しない。


### Distributive
`A => F[B]` から `G[A] => F[G[B]]` が得られるようなメソッド `distributive`を `Functor`に追加すると、`Distributive` になる。

```scala
trait Distributive[F[_]] extends Functor[F] {
  def distribute[G[_]: Functor, A, B](ga: G[A])(f: A => F[B]): F[G[B]]
  ...
```

`Traverse` の双対になっていて[^dual-of-traverse]、以下のような対応関係がある。

| 型クラス | この射から | この射を得る | G の条件 |
|:-:|:-:|:-:|:-:|
| Traverse[Pair]       | A → G[B]  |  Pair[A] → G[Pair[B]] | Applicative |
| Distributive[Pair]  | A → Pair[B]  | G[A] → Pair[G[B], G[B]  | Functor|

Scala コードとしては以下の未実装部分を補えばよいが、どうなるか？(難度=３)

```scala
trait PairDistributive extends Distributive[Pair] with PairFunctor:
  def distribute[G[_], A, B](ga: G[A])(f: A => (B, B))(using Functor[G]): (G[B], G[B]) = ???
```
<details><summary>実装例</summary><div>

```scala
def distribute[G[_], A, B](ga: G[A])(f: A => (B, B))(using Functor[G]): (G[B], G[B]) =
  val gpb: G[(B, B)] = ga map f
  (gpb.map(_._1), gpb.map(_._2))
```
</div>
`G` が Functor であることを利用して、`ga`、`f` から `G[Pair[B]]` を得てから、内箱と外箱を入れ替えて `Pair[G[B]]` とすればいい。
</details>

## SemigroupK など
おさらいすると、Cats の [K のつく型クラス](https://qiita.com/yasuabe2613/items/8e8940b85634bf916610)は、任意の型パラメータで成立する操作、つまり`F[A]` なら A にかかわらず`F[_]`の性質のみで成立する操作を提供するものだった。例えば `List[A]` なら、型 A が何であろうとリストの連結という二項演算があり、空リストという単位元がある。これを Pair の場合でみてみる。

### SemigroupK
`SemigroupK` は、二つの`F[A]` をあわせて一つの`F[A]` にするメソッド `combineK` を持つ。

```scala
trait SemigroupK[F[_]]:
  @simulacrum.op("<+>", alias = true)
  def combineK[A](x: F[A], y: F[A]): F[A]
  ...
```
`SemigroupK` なら二組の `(A, A)` をあわせて一組の `(A, A)` にするから、4つの A値を 2個にすることになる。A について前提を置かないのが、「Kのつくクラス」なので、A同士を合成することはできない。したがって半分すてて 2個だけとるしかない。どのように書けるだろうか。(難度=２)

```scala
trait PairSemigroupK extends SemigroupK[Pair]:
  def combineK[A](x: (A, A), y: (A, A)): (A, A) = ???
```
<details><summary>実装例</summary><div>

```scala
def combineK[A](x: (A, A), y: (A, A)): (A, A) = (x, y) match
  case ((x1, _), (_, y2)) => (x1, y2)
```
</div>
2個の A値の取りかたは associatiive law が成立すればいい。実は上のとり方だけが正解ではなくて、x や y をそのまま返したりしても、Discipline テストは上手く行く。逆に失敗するパターンを探してみると、SemigroupK の結合律の理解の助けになるかもしれない。
</details>

### MonoidK, Alternative
`Monoid` が単位元を提供するのと似たように `MonoidK` は「空」を提供する。これも型パラメータに依存しないものが求められ、たとえば List なら 空リスト、Option なら Noneでよいが、Pair の場合は単位元に相当するものはない。したがって `MonoidK[Pair]` は成立しないとわかる。

またさらに `MonoidK` に依存する（継承する）`Alternative` も、Pair では成立しないことになる。

## おわりに

- 質問者：「モナドとはなんですか？」
- この記事を読んだ Cats ユーザ：「`Applicative` と `FlatMap` を継承した `Monad` トレイトの実装で、Discipline テストの実行結果がグリーンになるものですが、なにか問題でも？」
- サンプルコードを Scala 3 に変更


[^other-typeclasses]: `A` を型パラメータにとる `Eq`系、`Monoid`系、`F[_,_]`を型パラメータにとる `BiFunctor`、`Arrow` 系、あるいは `F[_]` でも Cats Effect や Cats MTL に含まれるものもあるが、ここでは扱わない。
[^actually-invariant]: 図では `Semigroupal` だけど、実装上は `InvariantSemigroupal`。
[^dual-of-traverse]: 以前、調べてみた[記事](https://qiita.com/yasuabe2613/items/956402d8fdd06341e56f)を書いた。
[^about-ruleset]: 【理由１】かなり数が多い、【理由２】あらかじめ法則を知悉していなくても、テストがコケたときに調べるくらいがコスパが良い、【理由３】自分も含め、ほとんどのプログラマは数学徒ほど証明や法則が好きではない（たぶん）。
[^shapeless-sized]: Shapeless の [Sized](https://github.com/milessabin/shapeless/wiki/Feature-overview:-shapeless-2.0.0#collections-with-statically-known-sizes) で固定サイズのコレクションを表現することもできる。
[^original-picture]: もとの画像は[ここ](https://typelevel.org/cats/typeclasses.html#type-classes-in-cats)
[^about-quiz]: 『Learn Better』という一般向けの学習理論の本によれば、ただ読むだけという行為は、どれだけマーカーを引こうが、あるいは何度読み返そうが、学習効果はぜんぜん薄いというのが、心理学でも脳科学でも無数のエビデンスに支持された結論らしい。そこで同書では本の中の要所要所に、小テストを入れて理解と記憶の定着を支援していたが、この記事でもそれにならって、「学習」を「活動」につなげるためにクイズ形式を取り入れてみた。