Cats の関数覚え書き(Semigroup, Monoid)

この記事は [MicroAd Advent Calendar 2021](https://qiita.com/advent-calendar/2021/microad) の 15 日目の記事です。

記事としては 
- [Cats の関数覚え書き(Functor, Apply, Applicative, FlatMap)](https://qiita.com/nozomitaguchi/items/24ab70f921f1e013d49b)
- [Cats の関数覚え書き(ApplicativeError, MonadError)](https://qiita.com/nozomitaguchi/items/a74d9bfe67ae63530222) 
の続きになります。

# はじめに

現在、弊チームでは Cats 製の WEB アプリを実装(既存のアプリのリプレイス)を進めています。

Cats にはたくさんの型クラスにたくさんの関数が定義されているのですが、それを知った上で実装を行うのと、知らないで実装を行うのではコーディングの難易度に天と地ほどの差があるように感じています。

今回はチームメンバーへの共有も兼ねて、よく使うであろう型クラスの関数について覚書程度ですが使い道などを書いていこうと思います。

- flatMap とそれに連なる型クラス
    - Functor
    - Bifunctor
    - FunctorFilter
    - Apply
    - Applicative
    - FlatMap
- エラー処理に関する型クラス
    - ApplicativeError
    - MonadError
- cats.kernel 系
    - Eq
    - Order
    - Semigroup
        - (SemigroupK)
    - Monoid
        - (MonoidK)
- traverse とそれに連なる型クラス
    - Foldable
    - Bifoldable
    - Reducible
    - Traverse
    - Bitraverse
    - TraverseFilter

上記の型クラスに定義されている関数を紹介しようと思ったのですが、めちゃくちゃ長くなってしまったので記事を分割して、１カテゴリーずつ毎週水曜日に紹介していこうと思います。

前回の記事では、エラー処理に関する型クラスとして ApplicativeError, MonadError を見ていきました。今回は、cats.kernel に定義されている型クラスとそれに関連するものを見ていきます。

- Eq
- Order
- Semigroup
    - (SemigroupK)
- Monoid
    - (MonoidK)

## 今回使用する cats, scala のバージョン

- scala 2.13.1
- cats  2.6.1

を使って今回のコードを書いています。

## 使用するクラスについて

本記事では、関数の使い方の具体例を書いていこうと思うのですが、以下の様なクラスを使って例をあげていこうと思っています。

```scala
// 値クラス
case class AccountId(private val toInt: Int) extends AnyVal

case class AccountName(override val toString: String) extends AnyVal

```

```scala
// 値クラスを使ったクラス
case class Account(private val id: AccountId, private val name: AccountName)

```

```scala
// ファーストクラスコレクション
case class AccountIds(private val toList: List[AccountId]) extends AnyVal

case class Accounts(private val toNel: NonEmptyList[Account]) extends AnyVal
```

よくある感じですね。これらを使って実装例を示していきますので、覚えておいていただければと思います。

## F として抽象化する際のコード例について

関数の説明をする中で、具体的な List, Either などのクラスとしてではなく、F として抽象化した状態での関数の使い方を説明する場合があります。

```scala
class FunctorContext[F[_]: Functor] {
  def f: F[Int => String] = ???
  def apply(i: Int): F[String] = ???
}
```

その時は、上記のようなクラスを作り、その中で対象の型クラスの関数を使う様にして説明していこうと思います。

## 関数の使い方の説明について

関数の使い方を説明する際、なるべく

- `〇〇を使わないと・・・`
- `〇〇を使うと・・・`

というように、関数を使わなかった場合の実装と、使った場合の実装を比較して説明してしようと思っています。

関数を使う例が List, Either などの scala 標準で用意されているデータ型の場合は、`〇〇を使わないと・・・`の方ではなるべく cats 自体を使わないように努め、cats を使う場合とそうでない場合の比較が出来るようにしようと思っています。

関数を使う例が`F[_]: Functor`などとして抽象化してある場合は、cats を使わないのは無理なので、他の実装方法をとる場合はどういう風になるのか、例えばその関数の存在を知らない場合は、どういう実装が必要になってしまうのかの様な比較が出来る様に書いていこうと思います。

### syntax をなるべく使う

cats では関数の実装(定義)とは別に、それをスマートに使うための syntax が用意されています。例えば、Foldable::combineAll という関数を使う場合、syntax を使わないで書くと、

```scala
Foldable[List].combineAll(List(1, 2, 3))
// 6
```

この様に書く必要がありますが、syntax を使って書くと

```scala
List(1, 2, 3).combineAll
// 6
```

この様に書くことが出来ます。こちらのほうが自然ですよね。

実際にコーディングをする場合はこちらを使うことになると思いますので、実践的な意味で syntax を使える場合は使ってコード例を示していこうと思います。


# Eq

こちらは equals の Eq ということで、インスタンスが何を持って等価なのかというのを表す型クラスになっています。

## by

```scala
def by[@sp A, @sp B](f: A => B)(implicit ev: Eq[B]): Eq[A]
```

by は scala の標準関数である Ordering::by で見慣れた方もいるかと思いますが`A => B`を受け取って`Eq[A]`が返ってくるファクトリメソッドです、contramap な感じの関数ですね。主には値クラスに対して使うケースが多くなってくると思います。先ほどの AccountId を例にすると、

```scala
case class AccountId(private val toInt: Int) extends AnyVal

object AccountId {
  implicit val eqAccountId: Eq[AccountId] = Eq.by(_.toInt)
}
```

この様にして、AccountId を Eq の型クラスのインスタンスにすることができます。Int はもともと Eq の型クラスのインスタンスとして定義されていますので、それを使って AccountId を Eq の型クラスのインスタンスにしたという形になります。

## instance

```scala
def instance[A](f: (A, A) => Boolean): Eq[A]
```

こちらの instance 関数は、任意の関数によって Eq を生成してくれるファクトリメソッドになります。今のところあまり使っていないのですが「ID 以外が一緒だったら同じと見做す」という時とかに使えますでしょうか。

```scala
case class Account(private val id: AccountId, private val name: AccountName)

object Account {
  implicit val eqAccount: Eq[Account] = Eq.instance((l, r) => l.name == r.name)
}

```

自分で等価の定義を細かくしたい場合に使いそうな関数ですね。

## fromUniversalEquals

```scala
def fromUniversalEquals[A]: Eq[A] =
  new Eq[A] {
    def eqv(x: A, y: A) = x == y
  }
```

こちらは、case class の場合に役に立ちそうだなと思っているのですが、`==`での比較を基に Eq のインスタンスを作ってくれる関数です、先ほどの例でいうと、

```scala
case class Account(private val id: AccountId, private val name: AccountName)

object Account {
  implicit val eqAccount: Eq[Account] = Eq.instance((l, r) => l == r)
}

```

この様に、`(l, r) => l == r` と書いている場合は、fromUniversalEquals を使った処理に書き直した方がシンプルに記述できます。

```scala
case class Account(private val id: AccountId, private val name: AccountName)

object Account {
  implicit val eqAccount: Eq[Account] = Eq.fromUniversalEquals
}

```

## allEqual

```scala
def allEqual[A]: Eq[A] = new Eq[A] {
  def eqv(x: A, y: A) = true
}
```

全部のインスタンスを同じだと見做したい場合に使える関数ですね。今のところ「そんなケースってあるのかなぁ？」と思っているのですが、あるのでしょう。

---

## Eq についてのまとめ

Eq はインスタンスの生成方法について中心に見ていきました。Scala With Cats を読んだ時も思ったのですが、皆さんもインスタンスの作り方はわかったけれど、これって実務で使うんだろうかという疑問を持つかと思います。

私が認識している範囲だと、Eq は Monoid::isEmpty を使うときに要素が Eq の型クラスのインスタンスであることを要求されるのが使い方の一つだと思います。

```scala
def isEmpty(a: A)(implicit ev: Eq[A]): Boolean
```

つまり、あるクラスを、Monoid と Eq の型クラスのインスタンスにすると、自動的にそのクラスに isEmpty メソッドが生えてくるんですね。これは便利ですね！

# Order

Order は順序に関する型クラスです。scala の標準では Ordered とそのラッパーの様な存在の Ordering がありますが、Order はその Ordering のラッパーの様な存在かなと思います。

## by

```scala
def by[@sp A, @sp B](f: A => B)(implicit ev: Order[B]): Order[A]
```

こちら Eq にもありましたが、Ordering の by と同じ使い勝手のファクトリメソッドになります。

```scala
case class AccountId(private val toInt: Int) extends AnyVal

object AccountId {
  implicit val orderAccountId: Order[AccountId] = Order.by(_.toInt)
}

```

## reverse

```scala
def reverse[@sp A](order: Order[A]): Order[A]
```

名前の通り逆順にする関数です。以下のように使うことが出来ます。

```scala
case class AccountId(private val toInt: Int) extends AnyVal

object AccountId {
  implicit val orderAccountId: Order[AccountId] =
    Order.reverse(Order.by(_.toInt))
}

```

## whenEqual

```scala
def whenEqual[@sp A](first: Order[A], second: Order[A]): Order[A]
```

こちらは、first として受け取った Order で equal 判定されてしまったときに second として受け取った Order で比較してくれるような Order に合成してくれる関数ですね。

```scala
case class AccountId(private val toInt: Int) extends AnyVal

object AccountId {
  implicit val orderAccountId: Order[AccountId] =
    Order.reverse(Order.by(_.toInt))
}

case class AccountName(override val toString: String) extends AnyVal

object AccountName {
  implicit val orderAccountName: Order[AccountName] = Order.by(_.toString)
}

case class Account(private val id: AccountId, private val name: AccountName)

```

上記の様な Account で例えば、id が同一のものが存在する場合(そんなものはなさそうな例ですみませんが・・・)次は name で比較したい場合は以下のように Order を実装します。

```scala
object Account {
  implicit val orderAccount: Order[Account] =
    Order.whenEqual(Order.by(_.id), Order.by(_.name))
}

```

２つの値で一意になるようなデータに対して使うといいかもしれないですね。もし３個以上の比較をしたい場合は、whenEqual をネストしていくんでしょうか。

## allEqual

```scala
def allEqual[A]: Order[A]
```

Eq と同じ様に、全部のインスタンスを同じだと見做したい場合に使える関数ですね、「僕の並べた順番を絶対に変えて欲しくない！」みたいな場合に使うんでしょうか。

## Order についてのまとめ

Order についてもインスタンスの生成方法についての関数を見ていきました。このクラスは Eq クラスを継承しているで、Eq だけの比較では足りない場合はこちらを使うように変更したりするのかなと思います。使い道ですが Foldable の minimumOption, maximumOption や

```scala
def minimumOption[A](fa: F[A])(implicit A: Order[A]): Option[A]
def maximumOption[A](fa: F[A])(implicit A: Order[A]): Option[A]
```

Reducible の minimum, maximum

```scala
def minimum[A](fa: F[A])(implicit A: Order[A]): A
def maximum[A](fa: F[A])(implicit A: Order[A]): A
```

NonEmptyList の distinct などの様々な関数

```scala
def distinct[AA >: A](implicit O: Order[AA]): NonEmptyList[AA]
```

などで要求されているので、例えば NonEmptyList を使っていると「Order の型クラスのインスタンスにしたいなぁ」と思う場面が出てくると思います。

---

# Semigroup

「empty はないけど combine はある」でお馴染みの Semigroup ですが、この型クラスのインスタンスとしてわかり易い例は、NonEmptyList やそのファーストクラスコレクションが挙げられると思います。

```scala
case class Accounts(private val toNel: NonEmptyList[Account]) extends AnyVal
```

NotEmptyList なので当然 empty は定義できないけど、combine(足したときにどうなるか)というのは定義できそうに思えます。

## instance

```scala
def instance[A](cmb: (A, A) => A): Semigroup[A]
```

名前の通り、Semigroup のインスタンスを作るためのファクトリメソッドで、combine の定義を関数として渡してあげるとインスタンスが生成されます。先程の Accounts クラスを Semigroup の型クラスのインスタンスにしてみましょう。

```scala
case class Accounts(private val toNel: NonEmptyList[Account]) extends AnyVal

object Accounts {
  implicit val semigroupAccounts: Semigroup[Accounts] =
    Semigroup.instance((l, r) => Accounts(l.toNel ::: r.toNel))
}
```

この様に combine を定義するだけで Semigroup としての機能を手に入れることが出来ました。

### ちなみに・・・

NonEmptyList には、`NonEmptyList[A]`を Semigroup の型クラスのインスタンスにするためのヘルパー関数が予め定義されており、例えば

```scala
Semigroup[NonEmptyList[Account]]
```

とやるだけで`NonEmptyList[Account]`を Semigroup のインスタンスを作ることが出来ます。これを利用して、

```scala
object Accounts {
  implicit val SemigroupAccounts: Semigroup[Accounts] =
    Semigroup[NonEmptyList[Account]].imap(Accounts(_))(_.toNel)
}
```

この様に imap を使って Accounts を Semigroup の型クラスのインスタンスとして簡単に定義することが出来ます。また shapeless.Unwrapped を使えば、NonEmptyList な AnyVal の Semigroup 定義を一括で行うことが出来ます。shapeless は全く勉強していないので雰囲気で書いていますが、

```scala
implicit def semigroupAnyValOfF[F[_], W <: AnyVal, U](
  implicit unwrapped: Unwrapped.Aux[W, F[U]],
  semigroupF: SemigroupK[F]
): Semigroup[W] = SemigroupK[F].algebra[U].imap(unwrapped.wrap)(unwrapped.unwrap)

implicit def semigroupAnyValOfNel[W <: AnyVal, U](
  implicit unwrapped: Unwrapped.Aux[W, NonEmptyList[U]]
): Semigroup[W] = semigroupAnyValOfF[NonEmptyList, W, U]
```

この様な感じで、implicit を用意しておけば、これを import するだけで、NonEmptyList な AnyVal を Semigroup の型クラスのインスタンスにすることが出来ます。面白いですね。

## first

```scala
@inline def first[A]: Semigroup[A] =
  new Semigroup[A] {
    override def combine(x: A, y: A): A = x
  }
```


定義を見ればわかるように、足したときに必ず先勝ちするような定義をしたい場合に使えるファクトリメソッドのようです。

```scala
object Accounts {
  implicit val semigroupAccounts: Semigroup[Accounts] = 
    Semigroup.first[Accounts]
}
```

この様に定義することが出来ます。同様に必ず後勝ちするように定義できる last という関数もあります。

## intercalate

```scala
def intercalate(middle: A): Semigroup[A] =
  new Semigroup[A] {
    def combine(a: A, b: A): A =
      self.combine(a, self.combine(middle, b))
  }
```

こちらの関数は、足し合わせるときに、別の要素を間に挟む新しい Semigroup を生成して返してくれる関数になります。なんのために使うのか想像しづらいと思うのですが、この関数が内部的に使われている Foldable::intercalate では、String::mkString を抽象化したような処理を書くことができます。

```scala
List("a", "b", "c").intercalate("-")
// "a-b-c"
```

詳しくは、Foldable の項目で再度見ていきますが、このような処理をするときなどに使える関数なんだなとふわっと思っておけば良いのではないかと思っています。個人的にはこれ単体で何かをするイメージはまだついていません。

## combineAllOption

```scala
def combineAllOption(as: IterableOnce[A]): Option[A]
```

こちらは、List などに包まれた要素をまとめてくれる関数です。ただし、List.empty の場合や None の場合はこの関数の返り値は None になります。実際にはこの関数を使って Foldable の方に定義してある combineAllOption を使うことの方が多いと思います。詳しくは Foldable の方で見ていきましょう。

# SemigroupK

Semigroup に K が付いているこの型クラスですが、K というは何を表しているんでしょうか。カインドの K なのかなと思っているんですがあまり自信がありません。Semigroup は Int, `List[String]`などの具体的な型やクラスに対するものだったのに対し、SemigroupK は List, Option などのカインド型に対するものといった違いがあります。

List だったら要素がなんであれ、List 同士の足し算は`:::`になりそうなので、中身が関係ない感じで抽象的な定義が可能な気がしますよね。

## combineK(<+>)

```scala
def combineK[A](x: F[A], y: F[A]): F[A]
```

この関数は、List でいうと`:::`をやってくれるような関数です。List と Option の場合の例を確認してみましょう。

```scala
List(1, 2, 3) <+> List(3, 4, 5)
// List(1, 2, 3, 3, 4, 5)
```

```scala
1.some <+> none[Int]
// Some(1)
```

Option の場合は、none は無視されるんですね。

## algebra

```scala
def algebra[A]: Semigroup[F[A]]
```

こちらは、SemigroupK から Semigroup を生成するための関数になります。Semigroup のインスタンスを作る例として、以下のような実装例を先程示しましたが、

```scala
object Accounts {
  implicit val SemigroupAccounts: Semigroup[Accounts] =
    Semigroup[NonEmptyList[Account]].imap(Accounts(_))(_.toNel)
}
```

こちらがなぜ実現できるかというと、implicit として `Semigroup[NonEmptyList[A]]`を定義してくれているからなんですが、その定義に SemigroupK::algebra が使われています。

```scala
implicit def catsDataSemigroupForNonEmptyList[A]: Semigroup[NonEmptyList[A]] =
  SemigroupK[NonEmptyList].algebra[A]
```

このような定義がない場合で、SemigroupK の型クラスのインスタンスを Semigroup として扱いたい場合は、algebra 関数を使うと良いでしょうか。

## sum

```scala
def sum[A, B](fa: F[A], fb: F[B])(implicit F: Functor[F]): F[Either[A, B]]
```

語感としては、足し算をしてくれそうな名前に感じるこの関数ですが、型定義をみると`F[A]`と`F[B]`を受け取って`F[Either[A, B]]`を返すような関数になっています。どういうときに使うのでしょうか。あまり想像できていないのですが、例えば出自の違う一覧を一旦左右に分けた後で、分類し直したい場合とかがあるでしょうか。

```scala
val a: NonEmptyList[Char] = NonEmptyList.of('a', 'b', 'c', '4')
val b: NonEmptyList[Int] = NonEmptyList.of(1, 2, 3)
a.sum(b).map(_.recover { case c if c.isDigit => c - '0' })
```

上記の例は、Char と Int の一覧があり「Char が数値だった場合は Int の一覧として扱い直したい」というときに sum で一旦`NonEmptyList[Either[Char, Int]]`にしたあとで、isDigit な Char を右側に recover しています。こんなケースありますかね。。どうなんでしょう。filter して変数 a から `'4'`を抜いて、変数 b に`'4'`を足すよりはわかりやすいかもしれないですね。

# Monoid

続いては「empty と combine」でお馴染みの Monoid です。Semigroup に empty 機能を追加したものという感じでしょうか。この型クラスのインスタンスとしてわかり易い例は、List などの Iterable なクラスとそのファーストクラスコレクションでしょうか。

```scala
case class AccountIds(private val toList: List[AccountId]) extends AnyVal
```

List の empty は`List::empty[A]`で、List 同士の足し算は`:::`を使えば良いような気がしますね。

## instance

Semigroup と同じですが、Monoid にも instance というファクトリメソッドが用意されています。

```scala
case class AccountIds(private val toList: List[AccountId]) extends AnyVal

object AccountIds {
  val empty: AccountIds = AccountIds(List.empty)
  implicit val monoidAccountIds: Monoid[AccountIds] =
    Monoid.instance(empty, (l, r) => AccountIds(l.toList ++ r.toList))
}

```

この様に、empty と combine を定義して上げると Monoid のインスタンスを手に入れることができます。

### 蛇足ですが・・・

こちらも Semigroup と同様ですが、`List[A]`に対しても Monoid 定義を予めしてくれていますので、ファーストクラスコレクションを Monoid の型クラスのインスタンスにしたい場合は imap を使うほうがシンプルに記述できると思います。

```scala
object AccountIds {
  implicit val monoidAccountIds: Monoid[AccountIds] =
    Monoid[List[AccountId]].imap(AccountIds(_))(_.toList)
}
```

Semigroup と同様に shapeless を使って、List な AnyVal を Monoid の型クラスのインスタンスとして定義することが可能だと思います。

```scala
implicit def monoidAnyValOfF[F[_], W <: AnyVal, U](
  implicit unwrapped: Unwrapped.Aux[W, F[U]],
  monoidKF: MonoidK[F]
): Monoid[W] = MonoidK[F].algebra[U].imap(unwrapped.wrap)(unwrapped.unwrap)

implicit def monoidAnyValOfList[W <: AnyVal, U](
  implicit unwrapped: Unwrapped.Aux[W, List[U]]
): Monoid[W] = monoidAnyValOfF[List, W, U]
```

## empty

```scala
def empty: A
```

こちら Monoid たる所以みたいな関数ですが、empty というものが定義されています。

### empty を使わないと・・・

例えば AccountIds が Monoid でない場合、以下のようにコンパニオンオブジェクトなどに、empty を定義してそれを使うのがベターだと思います。

```scala
object AccountIds {
  val empty: AccountIds = AccountIds(List.empty)
}
```

私はこのような変数、これまでたくさん用意してきました。

### empty を使うと・・・

AccountIds が Monoid の型クラスのインスタンスになっていれば、

```scala
Monoid[AccountIds].empty
```

というように、どこでも empty を呼び出すことが出来ます。便利ですね。自分で empty 変数を書かなくていいのはとても良いと思います。

## isEmpty

```scala
def isEmpty(a: A)(implicit ev: Eq[A]): Boolean
```

こちらは見ればわかると思いますが、empty かどうか判断するメソッドですね。

### isEmpty を使わないと・・・

この isEmpty、私はファーストクラスコレクションのメソッドとして、よく自分で定義していました。

```scala
case class AccountIds(private val toList: List[AccountId]) extends AnyVal {
  def isEmpty: Boolean = toList.isEmpty
}
```

または、コンパニオンオブジェクトに empty を定義した上で

```scala
case class AccountIds(private val toList: List[AccountId]) extends AnyVal {
  def isEmpty: Boolean = this == empty
}
```

などと、やっていまいた。

### isEmpty を使うと・・・

cats で定義されたこの関数を使うためには、Monoid に加えて、Eq の型クラスのインスタンスである必要があります。

```scala
object AccountIds {
  
  implicit val eqAccountIds: Eq[AccountIds] = Eq.fromUniversalEquals
  
  implicit val monoidAccountIds: Monoid[AccountIds] = 
    Monoid[List[AccountId]].imap(AccountIds(_))(_.toList)
  
}
```

この様に定義されている場合は

```scala
val accountIds: AccountIds = ???
accountIds.isEmpty
```

どこでも isEmpty を呼び出すことが出来ます。こちらも個人的には自分で定義しなくてよくなることに、とても魅力を感じます。

## Option::orEmpty

```scala
def orEmpty(implicit A: Monoid[A]): A = oa.getOrElse(A.empty)
```

直接 Monoid の関数というわけではないんですが、Monoid を使った関数が Option から生えているので紹介します。定義を見ればわかると思うんですが、Option を剥がすときに getOrElse + empty というコードをよく書くと思うのですが、要素が Monoid のとき、それをまとめてくれている orEmpty という関数を使うことが出来ます。

```scala
val maybeAccountIds: Option[AccountIds] = ???
def apply: AccountIds = maybeAccountIds.orEmpty
```

面白いですね。

# おわりに

cats.kernel 系の型クラスは、他にもたくさんあるのですが、主要そうな型クラスに絞って見ていきました。SemigroupK は cats.kernel ではないですが、Semigroup を１段階抽象化したような存在だったのでこちらにまぜさせていただきました。また SemigroupK と同様に MonoidK というものも存在するのですが、empty 定義以外ほとんど違いがなさそうなので省略しました。

Semigroup と Monoid は関数型言語の勉強をしていると最初の方に登場する概念かなと思います。個人的には「面白い概念なのはわかるんだけど、実装にどう役に立つんだろう？」というのが勉強している段階だと想像できていませんでした。今回関数を見てみて、ファーストクラスコレクションにボイラープレートのように定義していた empty, isEmpty を書かなくて済むようになるのだけで「おお、結構使えるじゃんか」と私は感じましたが、みなさんはどうでしょうか。