Cats の関数覚え書き(Foldable, Reducible, Traverse, TraverseFilter)

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

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

# はじめに

現在、弊チームでは 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

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

前回の記事では、cats.kernel 系として Semigroup, Monoid などの型クラスを見ていきました。今回は、traverse とそれに連なる型クラスとして、Foldable, Reducible, Traverse, TraverseFilter などの関数を見ていこうと思います。

- Foldable
- Bifoldable
- Reducible
- Traverse
- Bitraverse
- TraverseFilter

## 今回使用する 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 を使える場合は使ってコード例を示していこうと思います。


# Foldable

まずは Foldable です。名前の通り、fold(foldLeft, foldRight)できるやつでお馴染みの Foldable ですが標準関数として見慣れた関数から、見慣れない関数まで本当にたくさんの fold で実装された関数を発見することが出来ます。List の拡張関数だと思っておけばだいたい差し支えないんじゃないかと思っています。

## combineAll

```scala
def combineAll[A: Monoid](fa: F[A]): A = fold(fa)
```

こちらは、fold のエイリアスで、要素が Monoid の場合に、`F[A]`を A としてまとめてくれる関数になっています。

標準関数でも fold という関数は定義されているので、例えば List に対して cats で定義されている方の fold を使おうとすると少し手間がかかります、それを解決するために、combineAll という名前でエイリアスを作っているのだと解釈しています。

```scala
case class Money(private val toLong: Long) extends AnyVal

```

例えば Money クラスがあるとします、Money なので、他の Money と足し算する関数を実装したいですよね。

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

通常だと、そういうことがしたい場合は、

```scala
case class Money(private val toLong: Long) extends AnyVal {
  def add(other: Money): Money = Money(toLong + other.toLong)
}

```

add や + などの関数を用意して、

```scala
List(Money(10L), Money(100L)).fold(Money.empty)(_ add _)
```

fold などでまとめ上げると思います。

### combineAll を使うと・・・

さて、combineAll を使うには、まず Money を Monoid の型クラスのインスタンスにする必要があります。

```scala
case class Money(private val toLong: Long) extends AnyVal

object Money {
  implicit val monoidMoney: Monoid[Money] = Monoid[Long].imap(Money(_))(_.toLong)
}
```

このように Monoid のインスタンスにすることが出来ました。Money が Monoid になっていれば、combineAll を使うことが出来ます。

```scala
List(Money(10L), Money(100L)).combineAll
```

便利ですね。

## combineAllOption

```scala
def combineAllOption[A](fa: F[A])(implicit ev: Semigroup[A]): Option[A]
```

combineAll と比べて返り値が Option で包まれているこの関数ですが、要素に要求される型クラスも combineAll と違い Semigroup になっています。例えば Semigroup の例として先ほどあった、Accounts が複数存在する場合に、一つの Accounts にまとめたい場合を考えてみます。

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

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

val accountsList: List[Accounts] = ???
def apply: Option[Accounts] = ???
```

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

まず Accounts を Semigroup として定義しなかった場合の実装方法を考えてみると、add 関数のようなものを実装する必要がありますね。

```scala
case class Accounts(private val toNel: NonEmptyList[Account]) extends AnyVal {
  def add(other: Accounts): Accounts = Accounts(toNel ::: other.toNel)
}
```

その上で List が empty だった場合で分岐をした上で fold するか

```scala
def apply: Option[Accounts] = accountsList match {
  case Nil => none
  case head :: tail => tail.fold(head)(_ add _).some
}
```

headOption で map した上で tail を取って fold する感じになるでしょうか。

```scala
accountsList.headOption.map(accountsList.tail.fold(_)(_ add _))
```

次に Accounts が Semigroup として定義されている場合を考えてみます。cats の場合、List::toNel というメソッドが生えているのと、NonEmptyList::reduce を利用すると、それっぽく書けるかもしれません。

```scala
final class ListOps[A](private val la: List[A]) extends AnyVal {
  def toNel: Option[NonEmptyList[A]] = NonEmptyList.fromList(la)
}

```

```scala
final case class NonEmptyList[+A](head: A, tail: List[A]) extends NonEmptyCollection[A, List, NonEmptyList] {
  def reduce[AA >: A](implicit S: Semigroup[AA]): AA
}
```

上記を利用して実装すると、

```scala
def apply: Option[Accounts] = accountsList.toNel.map(_.reduce)
```

このように書けます。少しシンプルになりました。

### combineAllOption を使うと・・・

```scala
def apply: Option[Accounts] = accountsList.combineAllOption
```

よりシンプルに書くことが出来ますね。また、要求されているのが Semigroup なので Monoid の場合でもこの関数を使うことが出来ます、Monoid の場合でもあえて List が empty の場合は none にしたいケースなどで使うことができそうです。

## collectFold

```scala
def collectFold[A, B](fa: F[A])(f: PartialFunction[A, B])(implicit B: Monoid[B]): B
```

名前の通り collect + fold(combineAll) が実現できる関数ですね。こちらは変換後の要素が Monoid である必要があるという形になっています。数値のリストのうち、偶数だけを選んで、AccountIds にまとめる関数を実装したいとしましょう。

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

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

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

  def of(i: Int): AccountIds = AccountIds(List(AccountId(i)))
}

val ints: List[Int] = (1 to 10).toList
def apply: AccountIds = ???
```

この apply を実装すると、

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

collectFold を使わない場合、関数名の様に collect + fold(combineAll) として処理を書いたり、

```scala
def apply: AccountIds = ints.collect { case i if i % 2 == 0 => AccountIds.of(i) }.combineAll
```

はたまた、filter + foldMap で実装したりするでしょうか。

```scala
def apply: AccountIds = ints.filter(_ % 2 == 0).foldMap(AccountIds.of)
```

### collectFold を使うと・・・

```scala
def apply: AccountIds = ints.collectFold { case i if i % 2 == 0 => AccountIds.of(i) }
```

一つの関数でスッキリ書くことが出来ますね。

## collectFoldSome

```scala
def collectFoldSome[A, B](fa: F[A])(f: A => Option[B])(implicit B: Monoid[B]): B
```

こちらは、collectFold と比較して、受け取る関数が PartialFunction ではなく`A => Option[B]`になっています。ユースケースとしては 例えば、Id 毎に Money を持っている場合に、Id 一覧に対する Money の総額を出したいという場合、

```scala
val moneyById: Map[AccountId, Money] =
  Map(
    AccountId(1) -> Money(100L),
    AccountId(2) -> Money(2000L),
    AccountId(3) -> Money(1L)
  )
val accountIds: List[AccountId] = List(AccountId(1), AccountId(3))
def sum: Money = ???
```

この sum 関数を実装するとき

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

まずは Money が Monoid じゃない場合は、

```scala
def sum: Money = accountIds.foldLeft(Money.empty) { (acc, id) =>
  acc.add(moneyById.getOrElse(id, Money.empty))
}
```

```scala
def sum: Money = accountIds.mapFilter(moneyById.get).reduce(_ add _)
```

などと畳み込む処理を実装することになると思います。Money が Monoid だったら mapFilter, flatMap などを使って List にした後で combineAll する実装になるかもしれません。

```scala
def sum: Money = accountIds.mapFilter(moneyById.get).combineAll
```

### collectFoldSome を使うと・・・

```scala
accountIds.collectFoldSome(moneyById.get)
```

この様にシンプルに実装が出来ます。良いですね。

## reduceLeftToOption

```scala
def reduceLeftToOption[A, B](fa: F[A])(f: A => B)(g: (B, A) => B): Option[B]
```

標準でも実装されている reduceLeftOption と名前がすごく似ていますが、その関数を少し一般化した様な関数になっており初期値用とそれ以降用の二つの関数を受け取るものになっています。

```scala
def reduceLeftOption[A](fa: F[A])(f: (A, A) => A): Option[A] =
  reduceLeftToOption(fa)(identity)(f)
```

cats の reduceLeftOption は reduceLeftToOption を使って再実装をされた形になっていますね。これらの関数は例えば、どういうときに役に立つかというと、

- empty の場合がある値に対して処理を書きたい場合
- その中でも先頭の値に対して何か特別なことをしたい場合

などのときに役に立つと思います。例えば、空の場合もある ints というリストに対して、先頭の要素は 100 倍して、それ以降の処理は、先頭の要素から引き算をしたい(計算できない場合は None にする)という処理を書こうとしてみます。

```scala
val ints: List[Int] = ??? // 空かもしれない。
```

ちょっと説明に対して、都合良すぎると思いますがこういうこともあるでしょう。

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

reduceLeftToOption を使わないで書く場合は、headOption + tail で fold したり

```scala
ints.headOption.map(i => ints.tail.fold(i * 100)(_ - _))
```

要素が存在するかでパターンマッチした上で fold したり

```scala
ints match {
  case Nil => None
  case i :: remaining => Some(remaining.fold(i * 100)(_ - _))
}
```

もっとなんとかならないのかなぁっていうコードを書くハメになると思います。

### reduceLeftToOption を使うと・・・

reduceLeftToOption が使えると、以下の様にシンプルに書くことが出来ます。

```scala
ints.reduceLeftToOption(_ * 100)(_ - _)
```

便利！痒いところに手が届く素敵な関数ですね、reduceRightToOption という関数も用意されています。

## minimumOption, maximumOption

```scala
def minimumOption[A](fa: F[A])(implicit A: Order[A]): Option[A] =
  reduceLeftOption(fa)(A.min)
```

```scala
def maximumOption[A](fa: F[A])(implicit A: Order[A]): Option[A] =
  reduceLeftOption(fa)(A.max)
```

こちらは A が Order である時に使える関数になります。名前の通り、空じゃない時は some の min, max 値を、空の場合は none を返す関数で、同じ役割の関数が標準関数の IterableOnce::minOption, maxOption として実装されていますね。

ですので、List などの具体的なクラスに使うのではなく、Foldable として抽象化されている場合に使うケースが出てくるのかなと思っています。

```scala
class FoldableContext[F[_] : Foldable] {
  def account: F[Account] = ???

  val minAccount: Option[Account] = account.minimumOption
}

```

標準の minByOption, maxByOption と同じ役割の関数として minimumByOption, maximumByOption というものも用意されています。

## get

```scala
def get[A](fa: F[A])(idx: Long): Option[A]
```

こちら、scala 標準の Map::get や PartialFunction::lift(List.lift としても使える関数)としてよく知られている関数だと思いますので、省略します。

## collectFirstSome

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

こちらは、標準関数としても存在する collectFirst と比較して受け取る関数が少し違います、以下は、cats で定義されている collectFirst の型定義になります。

```scala
def collectFirst[A, B](fa: F[A])(pf: PartialFunction[A, B]): Option[B]
```

`PartialFunction[A, B]`を受け取るのか`A => Option[B]`を受け取るのかの違いがありますね。例えば、Map と List があって、List の中から最初に見つかった Map に含まれる要素を取得したい場合を考えます。

```scala
val accountById: Map[AccountId, Account] = ???
val accountIds: List[AccountId] = ???

val maybeAccount: Option[Account] = ??? // これを実装したい。
```

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

どんな実装が考えられるでしょうか。flatMap で要素を取ってきた後、headOption をしたり、

```scala
val maybeAccount: Option[Account] =
  accountIds.view.flatMap(accountById.get).headOption
```

collectFirst で要素が存在する最初の値を取ってきたり

```scala
val maybeAccount: Option[Account] = accountIds.collectFirst {
  case id if accountById.isDefinedAt(id) => accountById(id)
}
```

の様な感じで実装すると思います。どちらも、なんだかシンプルとは言えない実装になっていると思います。

### collectFirstSome を使うと・・・

そんな時は、collectFirstSome を使うとシンプルに書くことが出来ます。

```scala
val maybeAccount: Option[Account] =
  accountIds.collectFirstSome(accountById.get)
```

意図がわかりやすくて良いですね。

## foldMap

```scala
def foldMap[A, B](fa: F[A])(f: A => B)(implicit B: Monoid[B]): B
```

こちらの関数は、名前の通り map + fold(combineAll) といった処理が出来ます、同じ様な役割の関数で collectFold, collectFoldSome というものがありました。

```scala
def collectFold[A, B](fa: F[A])(f: PartialFunction[A, B])(implicit B: Monoid[B]): B
```

collectFold と比較すると A to B の PartialFunction を受け取るのか関数を受け取るのかの違いしかなさそうですね、collect と map の差という感じでしょうか。

```scala
def collectFoldSome[A, B](fa: F[A])(f: A => Option[B])(implicit B: Monoid[B]): B
```

collectFoldSome と比較すると引数として渡す関数の返り値が Option に包まれているかどうかが違いそうですね。例としては、Jpy, Usd の様な通貨変換をする場合を考えてみましょう。

```scala
case class ExchangeRate(private val toDouble: Double) extends AnyVal

case class Jpy(private val toLong: Long) extends AnyVal {
  def toUsdBy(rate: ExchangeRate): Usd = ???
}

case class Usd(private val toDouble: Double) extends AnyVal

```

```scala
def f: List[Jpy] = ???
val rate: ExchangeRate = ???
def apply: Usd = ???
```

関数 f は Jpy のリストになっていますね。みんなからお金をかき集めた場合とかを想像しておいてください。

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

Monoid ではなかった場合で考えてみましょう。Usd に add 関数を用意した上で・・・

```scala
case class Usd(private val toDouble: Double) extends AnyVal {
  def add(other: Usd): Usd = Usd(toDouble + other.toDouble)
}
object Usd {
  val empty: Usd = Uds(0.0)
}
```

foldLeft で両替しながら畳み込むなどすると思います。

```scala
def apply: Usd = f.foldLeft(Usd.empty)(_ add _.toUsdBy(rate))
```

これはこれでシンプルですが、Usd が Monoid として定義されているともっとシンプルに実装することができます。

### foldMap を使うと・・・

まず Usd が Monoid である必要があるので定義すると・・・

```scala
object Usd {
  implicit val monoidUsd: Monoid[Usd] = Monoid[Double].imap(Usd(_))(_.toDouble)
}

```

こんな感じになります。先程の例で実装した add 関数は必要ありません。

```scala
def apply: Usd = f.foldMap(_.toUsdBy(rate))
```

Usd(0.0) も add 関数も関数 apply の実装自体には出てこないで済むのでシンプルに記述出来ました。Monoid を使っているならでは、といった感じでしょうか。

## intercalate

```scala
def intercalate[A](fa: F[A], a: A)(implicit A: Monoid[A]): A 
```

Semigroup にも同じ名前の関数が定義されていましたが、それを内部的に呼び出してこねこねするのでしょうか。こちらの関数は要素が Semigroup ではなく Monoid であることを要求することも面白いですね。

「隙間に挿入する」という意味の単語が示す通りの処理をしてくれる関数で、docs に書かれた例だと、文字列の間に`"-"`を挟み込んで一つの文字列にするような処理が書かれています。

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

これだと mkString を使ったほうがわかりやすいと思いますが、

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

その様な処理を抽象化した関数だと思えば良いでしょうか。もう一つの例として docs に書かれたいたのは以下のような使い方です。

```scala
List(1, 2, 3).intercalate(1)
// 8
```

面白いですね。`1 + 2 + 3` の足し算の間に`+ 1`を差し込んでくれるような挙動になっています。`1 (+ 1) + 2 (+ 1) + 3`となり、合計の 8 が結果になるみたいですね。折角なので自作した Monoid を使った処理を考えてみましょう。

例えば、ギターのネックを修理したいときに「指板一区画100円、１フレット500円」みたいな値段設定されていた場合、「このギターは指板が25区画あるから、その間にあるフレットは24個か・・・25 * 100 + 24 * 500 が修理代金だな・・・」みたいに計算すると思います。

```scala
case class Jpy(private val toLong: Long) extends AnyVal
def apply: Jpy = ???
```

その処理を Jpy クラスを使って関数 apply として実装してみましょう。

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

Monoid でない場合を考えてみましょう。まずは、これまでと同じ様に add 関数と empty を定義します。

```scala
case class Jpy(private val toLong: Long) extends AnyVal {
  def add(other: Jpy): Jpy = Jpy(toLong + other.toLong)
}
object Jpy {
  val empty: Jpy = Jpy(0)
}
```

関数 apply の実装としては以下のようになるかと思います。

```scala
def apply: Jpy = {
  val count = 25
  (List.fill(count)(Jpy(100)) ::: List.fill(count - 1)(Jpy(500))).reduce(_ add _)
}
```

指板の数だけ 100 Jpy のリストとしてもち、その数を一個減らした数分だけ 500 Jpy のリストとして持ちます。それを合体してから reduce する感じで実装出来ました。

### intercalate を使うと・・・

まずは Jpy を Monoid の型クラスのインスタンスにしましょう。

```scala
case class Jpy(private val toLong: Long) extends AnyVal
object Jpy {
  implicit val monoidJpy: Monoid[Jpy] = Monoid[Long].imap(Jpy(_))(_.toLong)
}
```

その上で intercalate を使って実装すると、

```scala
def apply: Jpy = List.fill(25)(Jpy(100)).intercalate(Jpy(500))
```

シンプルですね。私の Monoid 脳が育っていないのもあって、ろくな例がまだ浮かばないのですが Monoid の型クラスのインスタンスを自分で定義していくにつれ、役に立つ場面も考えつくようになっていくだろうなと思っています。mkString に prefix, suffix も定義する version も存在するように、intercalate にも prefix, suffix を受け取る version が別名ですが存在します。

```scala
def foldSmash(prefix: A, delim: A, suffix: A)(implicit A: Monoid[A], F: Foldable[F]): A =
  A.combine(prefix, A.combine(F.intercalate(fa, delim), suffix))
```

最前後を特別な処理にしたい場合に便利な関数だと思います。

## foldA

```scala
def foldA[G[_], A](fga: F[G[A]])(implicit G: Applicative[G], A: Monoid[A]): G[A]
```

fold に A が付いた名前のこの関数。だいたい A って付いてたら Applicative 関連の関数なんじゃないかなと思っていいと思います。こちらの関数は、combineAll の A が更に Applicative な G に包まれていた場合、`G[A]`のままでまとめてくれるという関数です。以下は combineAll の定義になります。

```scala
def combineAll[A: Monoid](fa: F[A]): A 
```

combineAll は、例えば`List[Jpy]`を Jpy として合算してくれる関数でした。

```scala
def f: List[Jpy] = ???
def apply: Jpy = f.combineAll
```

foldA は`List[F[Jpy]]`を`F[Jpy]`に合算してくれるんですね。

```scala
class ApplicativeContext[F[_]: Applicative] {
  def f: List[F[Jpy]] = ???
  def apply: F[Jpy] = f.foldA
}
```

要素が Applicative なコンテキストに包まれた Monoid であれば、combineAll と同じ感覚でまとめ上げることができるんですね。便利。

## foldMapA

```scala
def foldMapA[G[_], A, B](fa: F[A])(f: A => G[B])(implicit G: Applicative[G], B: Monoid[B]): G[B]
```

こちらは、foldA を一般化した関数で、`F[A]`が`A => G[B]`という関数を受け取ると`G[B]`になることが出来ます。

```scala
def foldA[G[_], A](fga: F[G[A]])(implicit G: Applicative[G], A: Monoid[A]): G[A] =
  foldMapA(fga)(identity)
```

foldA は foldMapA で実装されています。foldMap という関数もありましたので比較すると、

```scala
def foldMap[A, B](fa: F[A])(f: A => B)(implicit B: Monoid[B]): B
```

foldMap は`A => B`なのに対し foldMapA は`A => G[B]`、返り値も B ではなく`G[B]`になっています。つまり、foldMap の Applicative なコンテキストに包まれた版が、foldMapA であると言えそうです。

foldMap のときに例として同じ様な例を出しましたが、今回は円ドル変換するのに、Applicative なコンテキストに包まれて返ってくる場合を考えてみます。データベースが絡んだりすると、よくある処理になると思います。

```scala
case class Jpy(private val toLong: Long) extends AnyVal
case class Usd(private val toDouble: Double) extends AnyVal
object Usd {
  implicit val monoidUsd: Monoid[Usd] = Monoid[Double].imap(Usd(_))(_.toDouble)
}
class ExchangeService[F[_]: Applicative]{
  def toUsd(jpy: Jpy): F[Usd] = ???
}
```

今度は関数 f がアプリカティブなコンテキストに包まれた状態の Jpy のリストを返してくれる関数で、それをつかって`F[Usd]`を得ようと思っているとします。

```scala
class ApplicativeContext[F[_]: Applicative] {
  val exchange: ExchangeService[F] = new ExchangeService[F]()
  def f: List[Jpy] = ???
  def apply: F[Usd] = ???
}
```

関数 apply をどう実装すればよいでしょうか。

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

foldMapA を使わなかった場合はどういう実装が考えられるでしょうか。map とさきほど紹介した、foldA を使っての実装が考えられます。

```scala
def apply: F[Usd] = f.map(exchange.toUsd).foldA
```

map で`List[F[Usd]]`に変換してから foldA で`F[Usd]`にしているんですね。

### foldMapA を使うと・・・

その処理を一度に行うことができるのが foldMapA という関数です。以下のように実装できます。

```scala
def apply: F[Usd] = f.foldMapA(exchange.toUsd)
```

シンプルですね。コンテキストに包まれていても foldMap と同じ使い勝手で実装できるのは良いですね。

## collectFirstSomeM

```scala
def collectFirstSomeM[G[_], B](f: A => G[Option[B]])(implicit F: Foldable[F], G: Monad[G]): G[Option[B]] 
```

こちら、collectFirstSome のお尻に M がついていますが、collectFirstSome と比較すると、受け取る関数が更に Monad に包まれて返ってくるパターンの時に使えそうな関数として定義されています。いやそんな複雑なことある？？と思うかもしれないんですが、DB アクセスを副作用として扱う場合は結構簡単にそういう状況が出てくると思います。

現在私たちのプロジェクト内では doobie というライブラリを使って mysql のテーブルにアクセスしてレコードを取ってきます、その際、DB アクセスの副作用を F として抽象化して扱っていますが、ごく単純な select 文を実装したとしても 以下の様に`F[Option[_]]`の様な型として返ってくることが多いんですね。

```scala
class MonadContext[F[_] : Monad] {
  def findBy(accountId: AccountId): F[Option[Account]] = ??? // DB アクセス等をする。

  val accountIds: List[AccountId] = ???

  def apply: F[Option[Account]] = ???
}

```

さてこちらの apply 関数を「Id を一個ずつ findBy して最初に取得できたレコードを取ってくる関数」として実装する場合を考えてみましょう。

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

まずは collectFirstSomeM を使わない場合の実装について考えてみましょう。`F[Some[Account]]`が最初に見つかった時点で走査を止めることを考慮すると難しそうな気がするので、そこは置いておくとして、

```scala
def apply: F[Option[Account]] =
  accountIds.traverse(findBy).map(_.flatten.headOption)
```

traverse を使って`F[List[Option[Account]]]` にした後、flatten + headOption する感じにすれば少なくとも型は合いそうです。ただ全ての要素を走査するのがだいぶ無駄な処理になりそうで現実的ではありませんよね。

### collectFirstSomeM を使うと・・・

```scala
def apply: F[Option[Account]] = accountIds.collectFirstSomeM(findBy)
```

たったこれだけのことで済んでしまいます。シンプルで良いですね。

## findM

```scala
def findM[G[_], A](fa: F[A])(p: A => G[Boolean])(implicit G: Monad[G]): G[Option[A]]
```

標準関数として用意されている List::find とくらべて、第２引数として受け取る関数の返す結果と、この関数自体の返り値がそれぞれ Monad に包まれているかの違いがあることがわかると思います。

```scala
def find(p: A => Boolean): Option[A]
```

これまで見てきた関数とは違い、要素が Monoid ではないことも注目するポイントでしょうか。こちらの関数についても副作用を伴う判定で考えると ユースケースが見えてきやすいと思います。

```scala
class MonadContext[F[_] : Monad] {
  def isActive(accountId: AccountId): F[Boolean] = ??? // DB アクセス等をする。

  val accountIds: List[AccountId] = ???

  def apply: F[Option[AccountId]] = ???
}

```

今度は、データベースにアクティブとして存在する最初の ID を取得したい場合を想定します。

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

findM を使わない実装を考えてみると、collectFirstSomeM と同じ様な感じで、Traverse に定義された関数を使えば実装自体はできると思います。

```scala
def apply: F[Option[AccountId]] =
  accountIds.filterA(isActive).map(_.headOption)
```

```scala
def apply: F[Option[AccountId]] =
  accountIds
    .traverse(id => Functor[F].ifF(isActive(id))(id.some, none))
    .map(_.flatten.headOption)
```

あまり綺麗な感じの実装ではないですね。(そして、Foldable より強力な Traverse を使ってしまっていますね。)

### findM を使うと・・・

```scala
def apply: F[Option[AccountId]] = accountIds.findM(isActive)
```

この様な感じになると思います。こちらもシンプルで良いですね。

## foldM

```scala
def foldM[G[_], A, B](fa: F[A], z: B)(f: (B, A) => G[B])(implicit G: Monad[G]): G[B]
```

こちらも、M と付いていますので、何かが Monad であることを必要とするタイプの関数である必要があることがわかると思います。型定義をみてみると、標準で用意されている foldLeft に近いような感じがします。foldM のエイリアスとして foldLeftM という名前が用意されていることでもこれらの関数の関係が深いことがわかると思います。

```scala
def foldLeft[B](z: B)(op: (B, A) => B): B
```

findM と同じ様に第２引数として受け取る関数の返す結果と、この関数自体の返り値がそれぞれ Monad に包まれているかの違いがありますがほかは同じですね。これも findM と同じですが、要素が Monoid の型クラスのinstanceである必要がないことにも注目してください。

用途が似ている、foldA(や foldMapA)では要素が Monoid の型クラスのインスタンスであることが必要だったのですが、こちらの foldM の場合にはその制約がありません。制約がない代わりに、初期値と combine 的な何かを自分で実装する必要があるということでしょうか。

foldMapA のときに使用した Jpy, Usd を使っての実装例をもう一度持ってきましょう。ただし今回は Usd は Monoid として定義されていない場合を考えます。

```scala
case class Jpy(private val toLong: Long) extends AnyVal
case class Usd(private val toDouble: Double) extends AnyVal {
  def add(other: Usd): Usd = Usd(toDouble + other.toDouble)
}
object Usd {
  val empty: Usd = Usd(0.0)
}
class ExchangeService[F[_]: Applicative] {
  def toUsd(jpy: Jpy): F[Usd] = ???
}
```

このときに、以下の関数 apply を f と exchange を使って両替し畳み込むような処理として実装したいとします。

```scala
class MonadContext[F[_]: Monad] {
  val exchange: ExchangeService[F] = new ExchangeService[F]()
  def f: List[Jpy] = ???
  def apply: F[Usd] = ???
}
```

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

まず、foldM を使わなかった場合はどういう実装が考えられるかというと、

```scala
def apply: F[Usd] = f.map(exchange.toUsd).foldLeft(Usd.empty.pure[F])(_.map2(_)(_ add _))
```

この様に map で`F[List[Usd]]`にしたあとで、foldLeft を使ったりすれば実現できると思います。ですが、pure だったり、map2 だったりと、随分と複雑な実装になってしまっている気がしますね。

### foldM を使うと・・・

```scala
def apply: F[Usd] = f.foldM(Usd.empty)((acc, jpy) => exchange.toUsd(jpy).map(acc.add))
```

この様にシンプルに書くことが出来ました。

## foldMapM

```scala
def foldMapM[G[_], A, B](fa: F[A])(f: A => G[B])(implicit G: Monad[G], B: Monoid[B]): G[B]
```

foldMapM は foldMapA とほとんど同じ型定義になっています。引数で受け取る関数の返り値が  Monad で包まれているのか、Applicative で包まれているのかという違いしかなさそうです。

docs を見ると「foldMapA より効率的」みたいなことが書かれていたので、どちらも使える状況ならこちらを使っておくと良いのではないかと思います。例えば ValidatedNel を使っている場合は、foldMapA を使うことになるんでしょう。

```scala
def foldMapA[G[_], A, B](fa: F[A])(f: A => G[B])(implicit G: Applicative[G], B: Monoid[B]): G[B]
```

## existsM(forallM)

```scala
def existsM[G[_], A](fa: F[A])(p: A => G[Boolean])(implicit G: Monad[G]): G[Boolean]

def forallM[G[_], A](fa: F[A])(p: A => G[Boolean])(implicit G: Monad[G]): G[Boolean]
```

こちらも List などで標準に用意されている exists, forall の Monad 版ですね。標準と同じ様に短絡な処理になっているようです。findM のときと同じ様にデータベースにアクセスした結果`F[Boolean]`が返ってくるような関数 isActive がある場合に、複数のアカウント ID の中で一個でもアクティブなアカウントの ID が存在するかというのを知りたい場合を想定します。

```scala
class MonadContext[F[_] : Monad] {
  def isActive(accountId: AccountId): F[Boolean] = ??? // DB アクセス等をする。
  val accountIds: List[AccountId] = ???
  def apply: F[Boolean] = ???
}
```

こちらの関数 apply を実装しようと思います。

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

existsM を使わないで実装しようとすると、traverse を使って`F[List[Boolean]]`にしたあとで、F の中身を map すればできるでしょうか。

```scala
def apply: F[Boolean] = accountIds.traverse(isActive).map(_.exists(identity))
```

なんだか辛いですね。

### existM を使うと・・・

```scala
def apply: F[Boolean] = accountIds.existsM(isActive)
```

すっきりと実装することが出来ました。forallM も同じ感じで実装することが出来ます。

## foldK

```scala
def foldK[G[_], A](fga: F[G[A]])(implicit G: MonoidK[G]): G[A] =
  fold(fga)(G.algebra)
```

こちらは、MonoidK に関する関数で、fold を間接的に呼ぶような実装になっています。fold の定義を見てみると、F の中身の A が Monoid である必要がありましたね。

```scala
def fold[A](fa: F[A])(implicit A: Monoid[A]): A 
```

ですが、MonoidK ならば、algebra して Monoid のインスタンスを作ってからそれを使って fold してくれたらいいのになぁ。と思うと思います。そんなかゆいところに手が届くような関数なんですね。使いどころとして面白い例が docs に書かれていたので同じ様な例で実装例を紹介します。

```scala
val f: List[Set[Int]] = ???
def apply: Set[Int] = ???
```

`List[Set[Int]]`を`Set[Int]`にしたい場合、どういう実装が考えられるでしょうか。

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

まず、foldK を使わない場合で考えてみると、安直にいくと flatten + toSet したり、

```scala
def apply: Set[Int] = f.flatten.toSet
```

もう少しちゃんとしようとすると、fold で書いたりするでしょうか。

```scala
def apply: Set[Int] = f.fold(Set.empty[Int])(_ ++ _)
```

よくやりますよね。

### foldK を使うと・・・

foldK を使うと、スッキリと書くことが出来ます。

```scala
def apply: Set[Int] = f.foldK
```

とても良いですね。

## foldMapK

```scala
def foldMapK[G[_], A, B](fa: F[A])(f: A => G[B])(implicit G: MonoidK[G]): G[B] =
  foldRight(fa, Eval.now(G.empty[B])) { (a, evalGb) =>
    G.combineKEval(f(a), evalGb)
  }.value
```

foldA に foldMapA があるように、foldK にも foldMapK という一般化した関数が存在します。こちらは受け取る関数の返り値が MonoidK に包まれている値である必要があるんですね。

```scala
val f: List[String] = ???
def g(str: String): Set[Int] = ???
def apply: Set[Int] = ???
```

`List[String]`を返す関数 f と String を受け取って`Set[Int]`を返す関数 g を使って、関数 apply を実装したいとします。

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

まず foldMapK を使わない場合を考えてみると、map + foldK をすると思います。

```scala
def apply: Set[Int] = f.map(g).foldK
```

### foldMapK を使うと・・・

```scala
def apply: Set[Int] = f.foldMapK(g)
```

map + foldK を使うような場合は、foldMapK を使うとよさそうです。

## sliding**

```scala
def sliding2[A](fa: F[A]): List[(A, A)]
```

```scala
def sliding3[A](fa: F[A]): List[(A, A, A)]
```

こちらの関数 sliding2 ~ sliding22 まで定義されていて、その数に対応した Tuple の List になって返ってきます。返り値が List という具体的なクラスになっているのも注目するポイントでしょうか。

scala の標準では、sliding という関数がありますが、それと似ています。

```scala
def sliding(size: Int, step: Int): Iterator[C]
```

この sliding は List に対して使うと、

```scala
val value: Iterator[List[Int]] = List(1, 2, 3, 4).sliding(2)
```

`Iterator[List[A]]`というふうに返ってきます。cats で定義されている sliding2 ~ sliding22 は Tuple の List なので少し違いがありますね。

```scala
val value: List[(Int, Int)] = List(1, 2, 3, 4).sliding2
// List((1,2), (2,3), (3,4))
```

zip + tail で List を Tuple にするとき以下のように一度変数化する必要があると思います。

```scala
val ints = List(1, 2, 3, 4)
ints.zip(ints.tail).map { case (l, r) => l - r }
```

個人的に、この書き方が少し億劫に感じるので、

```scala
List(1, 2, 3, 4).sliding(2).map { case List(l, r) => l - r }
```

このように sliding を使って書く場合があります。ですが、これでも map の中の`case List(l, r)`と書くのが野暮ったいなと感じることが結構あったので、

```scala
List(1, 2, 3, 4).sliding2.map{ case (l, r) => l - r }
```

このように少しスッキリ書けるのはよさそうに思えます。(ただ、実務で sliding を使った記憶がないですが。。)

## partitionEither

```scala
def partitionEither[A, B, C](fa: F[A])(f: A => Either[B, C])(implicit A: Alternative[F]): (F[B], F[C])
```

こちらは Alternative::separateFoldable を Foldable 側から使いやすくした様な関数ですね。`A => Either[B, C]`を受け取って`(F[B], F[C])`を返す様になっています。

例えば、Int を受け取って偶数の場合は Right、そうでない場合は、Throwable になるような関数 f があり、Int のリストに対してそれを当てて、失敗と成功の結果をそれぞれリストで持ちたい場合を考えてみましょう。

```scala
def f(i: Int): Either[Throwable, Int] = 
  Either.cond(i % 2 == 0, i, new Throwable(s"$i is not even"))
val ints: List[Int] = ???
def apply: (List[Throwable], List[Int]) = ???
```

この関数 apply を実装することを考えてみましょう。

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

まず partitionEither を使わない場合の実装を考えてみましょう。 Scala 標準で partitionMap という今回の用途にぴったりの関数がありました。

```scala
def apply: (List[Throwable], List[Int]) = ints.partitionMap(f)
```

### partitionEither を使うと・・・

partitionEither を使ってみると、

```scala
def apply: (List[Throwable], List[Int]) = ints.partitionEither(f)
```

全く同じ感じの使い勝手になりました。少し名前がわかりやすいですかね・・・？

## partitionBifold

```scala
def partitionBifold[H[_, _], A, B, C](
  fa: F[A]
)(f: A => H[B, C])(implicit A: Alternative[F], H: Bifoldable[H]): (F[B], F[C])
```

こちらは、partitionEither を一般化して Either だけでなく Bifoldable に対して使えるようにした関数です。先ほど、partitionEither を使って実装したコードをそのまま partitionBifold に変更することも出来ます。

```scala
def apply: (List[Throwable], List[Int]) = ints.partitionBifold(f)
```

折角なので、Tuple2 を使った場合の例を見てみましょう。

```scala
List(2, 3).partitionBifold(i => i -> s"$i days")
// (List(2, 3),List(2 days, 3 days))
```

想像の通りの結果になったことでしょう。こちらの挙動は、map + unzip で等価なコードが実現できそうです。

```scala
List(2, 3).map(i => i -> s"$i days").unzip
```

Tuple2 に対して使う場合は、この 2 つの関数をまとめて実行できるような存在だと思っておけばよいでしょうか。

## partitionEitherM

```scala
def partitionEitherM[G[_], A, B, C](fa: F[A])(f: A => G[Either[B, C]])(implicit A: Alternative[F], M: Monad[G]): G[(F[B], F[C])]
```

partitionEither に M をつけた名前のこの関数ですが、partitionEither に比べて受け取る引数の結果と関数自体の返り値が Monad で包まれているようです。以下が partitionEither の定義です。

```scala
def partitionEither[A, B, C](fa: F[A])(f: A => Either[B, C])(implicit A: Alternative[F]): (F[B], F[C])
```

partitionEither に出てきた関数 f が`F[Either[Throwable, Int]]`と Monad に包まれた Either を返す様になってしまったとしても、

```scala
class MonadContext[F[_]: Monad] {
  def f(i: Int): F[Either[Throwable, Int]] = ???
  val ints: List[Int] = ???
  def apply: F[(List[Throwable], List[Int])] = ints.partitionEitherM(f)
}
```

この様に同じ感覚で実装をすることが出来ます。便利ですね。partitionEither に対する partitionEitherM があるように partitionBifoldM という関数の存在しますが省略させていただきます。

## Foldable の関数の感想

Foldable ではとても多くの関数を見てきました。これだけ関数が定義されていることが Foldable の力強さを物語っているようですね。これだけの関数を使いこなせれば、実装のアイディアの幅がとても広がるのではないでしょうか。

---

# Bifoldable

Bifunctor に続く Bi シリーズです。こちらも Either, Tuple2 の実例を通して挙動を確認していきましょう。

## bifold

```scala
def bifold[A, B](fab: F[A, B])(implicit A: Monoid[A], B: Monoid[B]): (A, B)
```

こちらは要素がどちらも Monoid の場合、Tuple2 にして返してくれるという関数のようです。Either と Tuple2 について、左側が String, 右側が Int の場合の挙動を見てみましょう。

```scala
1.asRight[String].bifold
// (,1)
"test".asLeft[Int].bifold
// (test,0)
("test", 1).bifold
// (test,1)
```

Either の場合は、Monoid.empty で補完された Tuple2 が返っており、Tuple2 に使った場合は値がそのまま返ってきています。これは、Either を Tuple2 に変換する関数だと思っておけば良いでしょうか。標準関数でそのような処理を用意したい場合は、

```scala
val stringOrInt: Either[String, Int] = ???
stringOrInt.fold(_ -> 0, "" -> _)
```

このように fold を使って書く必要があると思います。これと比べるとシンプルに感じるでしょうか。

## bifoldMap

```scala
def bifoldMap[A, B, C](fab: F[A, B])(f: A => C, g: B => C)(implicit C: Monoid[C]): C
```

こちらは、bifold を一般化した関数、、ではなく、返り値が Monoid である C になっていることから、右側と左側を合算した値が返りそうな関数であることが想像できると思います。Either と Tuple2 両方の挙動をみてみましょう。

```scala
1.asRight[String].bifoldMap(_.length, identity)
// 1
1.asRight[String].bifoldMap(_ => 100, identity)
// 1
"test".asLeft[Int].bifoldMap(_.length, identity)
// 4
"test".asLeft[Int].bifoldMap(_.length, _ => 100)
// 4
("test", 1).bifoldMap(_.length, identity)
// 5
("test", 1).bifoldMap(_ => 100, identity)
// 101
("test", 1).bifoldMap(_.length, _ => 100)
// 104
```

今回は String の場合は文字数に変換し、Int の場合はそのままという処理として実装しました。Either の場合は片方しかないので片方が処理された結果が返り、Tuple2 の場合は両方処理されて合算した結果が返ってきていると思います。

Either の方は標準関数の Either::fold と同じ様な(Monoid を要求するかどうかは違うけど)処理だと思っておけば良さそうです。以下が Either::fold の定義です。

```scala
def fold[C](fa: A => C, fb: B => C): C
```

Tuple2 で標準関数を使って同等の処理を書きたい場合は、一度変数化して`_1, _2`で取り出して処理を書くか、

```scala
val tuple: (String, Int) = ("test", 1)
tuple._1.length + tuple._2
```

変数化したくない場合は、pipe を使って処理を書くと思います。

```scala
("test", 1).pipe { case (l, r) => l.length + r }
```

こちらに比べるとシンプルに記述できるのではないかと思います。

## bifoldLeft

```scala
def bifoldLeft[A, B, C](fab: F[A, B], c: C)(f: (C, A) => C, g: (C, B) => C): C
```

こちらの関数は foldLeft の bi バージョンと言う感じですが、注目するポイントとしては Monoid を要求していない部分でしょうか。Either の挙動を見てみましょう。

```scala
1.asRight[String].bifoldLeft(0)(_ + _.length, _ + _)
// 1
1.asRight[String].bifoldLeft(0)((_, _) => 100, _ + _)
// 1
"test".asLeft[Int].bifoldLeft(0)(_ + _.length, _ + _)
// 4
"test".asLeft[Int].bifoldLeft(0)(_ + _.length, (_, _) => 100)
// 4
```

bifoldMap と同じ様に、片方が処理された結果が返ってくる事がわかると思います。Tuple2 を見てみましょう。

```scala
("test", 1).bifoldLeft(0)(_ + _.length, _ + _)
// 5
("test", 1).bifoldLeft(0)(_ + _.length, (_, _) => 100)
// 100
("test", 1).bifoldLeft(0)((_, _) => 100, _ + _)
// 101
```

こちらは、bifoldMap の結果と比較して、右側が固定値のケースに面白い違いがでました。右 -> 左の順番で処理を行うのですが、右の結果を無視して 100 を返すので全体の返り値としては 100 が変えるんですね。

```scala
def bifoldRight[A, B, C](fab: F[A, B], c: Eval[C])(f: (A, Eval[C]) => Eval[C], g: (B, Eval[C]) => Eval[C]): Eval[C]
```

bifoldRight という関数も用意されておりこちらは返り値の型が Eval であることを要求します。

## Bifoldable の関数の感想

Either と Tuple2 について、Bifoldable の関数を使った場合の挙動を見ていきました。個人的には Either から Tuple2 に変換してなんやかんやしたいケースが何回かあった気がするので、今度遭遇したらこちらを使ってシンプルにコーディングしたいと思います。

# Reducible

Foldable が fold(foldLeft, foldRight)を使える型クラスだったのと同じように Reducible という reduce(reduceLeft, reduceRight)を使える型クラスもあって、Foldable が List の拡張関数だとおもっておけばだいたい良さそうなのに対して、Reducible は NonEmptyList の拡張関数だと思っておけばだいたい良さそうな雰囲気を感じます。

## reduce

```scala
def reduce[A](fa: F[A])(implicit A: Semigroup[A]): A 
```

まずは reduce 関数ですが、要素が Semigroup であることを要求します。

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

Accounts という Semigroup の型クラスのインスタンスのクラスがあるとして、

```scala
val accountsNel: NonEmptyList[Accounts] = ???
def apply: Accounts = ???
```

Accounts を NonEmptyList として持っている場合に、一つの Accounts としてまとめたいとします。その場合 reduce を使って

```scala
def apply: Accounts = Reducible[NonEmptyList].reduce(accountsNel)
```

この様に実装することが出来ます。NonEmptyList は要素が empty であることを考慮する必要がないので、fold でなく reduce を使ってまとめ上げることができるんですね。Foldable::combineAll の Reducible 版といったところでしょうか。

### 蛇足ですが・・・

今回 Reducible に定義された reduce 関数を使うために上記の様に実装しましたが、NonEmptyList の関数として reduce も用意されていますので、実際には

```scala
def apply: Accounts = accountsNel.reduce
```

のように実装をしたほうが、同じ目的を果たしつつシンプルに書くことができると思います。

## Reducible の関数の感想

他にも Foldable で定義されている関数の Reducible 版のようなものがたくさん定義されていますが、使い勝手はほとんど同じだと思いますので一つだけ紹介させていただきました。

Foldable は List などのクラスに対して要素が Monoid の定義があれば使える関数がたくさん用意されていましたが、Reducible は NonEmptyList に対して要素が Semigroup であれば使える関数がたくさん用意されています。

foldMapA があれば reduceMapA もあるだろう、traverse_ があれば nonEmptyTraverse_ があるだろう。みたいな感じで、見比べてみると面白いかもしれません。

---

# Traverse

traverse できるでお馴染みの Traverse です。Traversable という名前は、scala が標準ですでに使っていますので、cats としては Traverse という型クラス名になったのかなと思います。

```scala
trait Traverse[F[_]] extends Functor[F] with Foldable[F] with UnorderedTraverse[F]
```

Traverse は Foldable であり、Functor でもあるんですね。Foldable と同様に List の拡張関数だと思っておけば一旦良いと思います。早速関数を見ていきましょう。

## sequence

```scala
def sequence[G[_]: Applicative, A](fga: F[G[A]]): G[F[A]] =
  traverse(fga)(ga => ga)
```

まずは sequence です。型定義を見ると`F[G[A]]`を`G[F[A]]`にする関数だというのがわかると思います。scala 標準でも`List[Future[A]]`を`Future[List[A]]`にすることができる、`Future::sequence`という関数がありますが、これを一般化した存在だと思えば良さそうです。

F が Traverse で G が Applicative である必要があることもわかると思います。まずは Option と List の組み合わせの挙動を見てみましょう。

```scala
List(1, 2, 3).some.sequence
// List(Some(1), Some(2), Some(3))

List.empty[Int].some.sequence
// List()

none[List[Int]].sequence
// List(None)
```

Some だった場合は、List の中身がすべて Some で包まれた結果として返り、none だった場合は、List(None) になっています。どうしてこの挙動になるかというのは、Option に定義された traverse の実装をみると理解が深まると思います。

```scala
def traverse[G[_]: Applicative, A, B](fa: Option[A])(f: A => G[B]): G[Option[B]] =
  fa match {
    case None    => Applicative[G].pure(None)
    case Some(a) => Applicative[G].map(f(a))(Some(_))
  }
```

None の場合は、G の pure(List でいうと、List())に包まれた None を返し、Some の場合は、G を map して中身を Some で包んでいますね。今度は順番を逆にして List と Option の組み合わせを見てみましょう。

```scala
List.empty[Option[Int]].sequence
// Some(List())

List(1.some, 2.some, 3.some).sequence
// Some(List(1, 2, 3))

List(1.some, 2.some, none).sequence
// None
```

List が空だった場合は Some(List()) で List の中身がすべて Some だった場合は、Some を外した要素を List としてもつ、Some で囲われた値が返りますね。面白いのは List の中身に none が混ざっていたときです。一個でも none が混ざると結果も none になるのですね。List の traverse 定義をみてみましょう。

```scala
def traverse[G[_], A, B](fa: List[A])(f: A => G[B])(implicit G: Applicative[G]): G[List[B]] =
  if (fa.isEmpty) G.pure(Nil)
  else
    G.map(Chain.traverseViaChain {
      val as = collection.mutable.ArrayBuffer[A]()
      as ++= fa
      wrapMutableIndexedSeq(as)
    }(f))(_.toList)
```

List が empty だった場合は、G の pure(Option でいうと Some())に包まれた Nil を返し、そうでない場合は・・・何やら Chain の traverse を呼び出して最後に toList していますね。これは、List の traverse 処理は素直に実装すると処理の効率が悪くなってしまうので、Chain というデータ構造として traverse したあとで List に変換することでそれを回避しているということだと思います。

詳細は省きますがおそらく List が空でない場合は、map2 を使って要素を丸めていくため、Option の挙動として none が一つでもあると全体が none が返るという挙動になっています。詳しくは、Chain::traverseViaChain の実装を追うと良いと思います。この様に、sequence の処理は使用するクラスの traverse 実装によって決まるので、Traverse の型クラスのインスタンスを一通り眺めておくといいかもしれません。

## Foldable::sequence_

```scala
def sequence_[G[_] : Applicative, A](fga: F[G[A]]): G[Unit]
```

sequence に`_`が付いたこの関数ですが、Traverse ではなく Foldable として定義されている関数になります。名前は似ていますが、どんな関数なんでしょうか。sequence と比較すると。

```scala
def sequence[G[_]: Applicative, A](fga: F[G[A]]): G[F[A]]
```

sequence は返り値が`G[F[A]]`なのに対して、sequence_ は`G[Unit]`になっています。中身が Unit なので用途としては、ログ出力などの副作用を返したい場合か、MonadError などのエラーを返したい場合が考えられると思います。

```scala
class ApplicativeContext[F[_]: Applicative: Logger] {
  def f: List[F[String]] = ???
  def apply: F[List[String]] = ???
}
```

たとえば、上記の関数 apply を関数 f を使って`List[F[String]]`を`F[List[String]]`にしたい場合は、sequence を使うと思います。

```scala
def apply: F[List[String]] = f.sequence
```

ですが例えば、関数 apply が返す値が`F[Unit]`の場合(使う側が`List[String]`という結果を必要としない場合)どの様に実装するでしょうか。

```scala
class ApplicativeContext[F[_]: Applicative: Logger] {
  def f: List[F[String]] = ???
  def apply: F[Unit] = ???
}
```

### Foldable::sequence_ を使わないと・・・

まず Foldable::sequence_ を使わない場合の実装を考えてみましょう。おそらく sequence したあとで中身を捨てる感じの実装をすると思います。

```scala
def apply: F[Unit] = f.sequence.void
```

void を使うと良さそうですね。

### Foldable::sequence_ を使うと・・・

sequence + void をいっぺんにやってくれる関数がまさに sequence_ です。

```scala
def apply: F[Unit] = f.sequence_
```

Traverse よりも制約が弱い Foldable で実現可能な点も興味深いですね。

## flatSequence

```scala
def flatSequence[G[_], A](fgfa: F[G[F[A]]])(implicit G: Applicative[G], F: FlatMap[F]): G[F[A]]
```

こちらは、sequence + flatten のようなことをやってくれる関数で、`F[G[F[A]]]`を`G[F[A]]`にしてくれます。F に対して flatten を使うので F が FlatMap の型クラスのインスタンスであることを要求します。`F[G[F[A]]]`を``G[F[F[A]]]``にできれば、中身を flatten することができそうですよね。

ログや副作用を F として実装していると、`List[F[List[A]]]`のような型になってしまう場合がよくあります。こういう場合はだいたい、後続処理では F として扱いたいことが多いと思うので「なんとかして`F[List]`にしたいなぁ」と思う場面が多いです。

```scala
class ApplicativeContext[F[_]: Applicative] {
  def f: List[F[List[Account]]] = ???
  def apply: F[List[Account]] = f.flatSequence
}
```

そんな場合は上記のように flatSequence を使うとスッキリ書けると思います。

## traverse

```scala
def traverse[G[_]: Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]]
```

次は型クラス名にもなっているこの traverse 関数です。さきほど紹介した sequence を一般化した関数で、実際に sequence は traverse + identity な関数を使って実装されています。

```scala
def sequence[G[_]: Applicative, A](fga: F[G[A]]): G[F[A]] =
  traverse(fga)(ga => ga)
```

イメージ的には map + sequence をやってくれるような関数でしょうか。

```scala
class ApplicativeContext[F[_]: Applicative] {
  def f: List[String] = ???
  def g(str: String): F[Account] = ???
  def apply: F[List[Account]] = ???
}
```

`List[String]`を返す関数 f と String を受け取って、`F[Account]`を返す関数 g があるとして、それらを使って`F[List[Account]]`を返す関数 apply を実装する場合を考えてみましょう。

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

traverse を使わない場合は、map + sequence で実装できると思います。

```scala
def apply: F[List[Account]] = f.map(g).sequence
```

### traverse を使うと・・・

```scala
def apply: F[List[Account]] = f.traverse(g)
```

この様に実装できます。便利ですね。

## Foldable::traverse_

```scala
def traverse_[G[_], A, B](fa: F[A])(f: A => G[B])(implicit G: Applicative[G]): G[Unit]
```

この関数は、sequence_ と同じ様に、Foldable に定義されている関数で、返り値が traverse に比べて`G[Unit]`になっているやつですね。

```scala
def traverse[G[_]: Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]]
```

先程の例で、`F[List[Account]]`を返す関数 apply を以下のように実装しました。

```scala
def apply: F[List[Account]] = f.traverse(g)
```

sequence_ と同じ様に、もしこれが`F[Unit]`を返す関数になる場合どの様に実装するでしょうか。

### Foldable::traverse_ を使わないと・・・

Foldable::traverse_ を使わない場合は、sequence_ と同じ様に結果を void で捨ててあげると思います。

```scala
def apply: F[Unit] = f.traverse(g).void
```

### Foldable::traverse_ を使うと・・・

こちらも sequence_ とほとんど同じですが、

```scala
def apply: F[Unit] = f.traverse_(g)
```

この様にシンプルに書くことが出来ます。些細なことですが、かゆいところに手が届く関数といったところでしょうか。

## traverseTap

```scala
def traverseTap[G[_]: Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[A]]
```

こちらは flatTap と同じ様に中間処理を挟み込みたい場合に使う関数なのでしょう。`A => G[B]`の関数を受け取っているのに返り値の型は`G[F[A]]`と B が登場しないことに注目してください。tap なのでわかりやすい例はやはりロギングでしょうか。

```scala
class ApplicativeContext[F[_]: Applicative: Logger] {
  def f: List[String] = ???
  def g(str: String): F[Unit] =
    Logger[F].error(str).whenA(str.contains("error"))
  def apply: F[List[String]] = ???
}
```

例えば、`List[String]`を返す関数 f と String を受け取って`"error"`が含まれている場合だけエラーログを吐く関数 g をつかって関数 apply を実装したいとします。

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

まず、traverseTap を使わない場合で考えると、traverse のときと同じ様に map + sequence を使うのに加え as でロギングの返り値を変えてあげると実装できそうです。

```scala
def apply: F[List[String]] = f.map(str => g(str).as(str)).sequence
```

ログを挟み込みたいだけなのになんだか仰々しいですね。

### traverseTap を使うと・・・

そこで traverseTap を使うと、

```scala
def apply: F[List[String]] = f.traverseTap(g)
```

シンプルに書くことが出来ました。

## flatTraverse

```scala
def flatTraverse[G[_], A, B](fa: F[A])(f: A => G[F[B]])(implicit G: Applicative[G], F: FlatMap[F]): G[F[B]]
```

こちらは名前の通り traverse + flatten という感じの関数になります。`A => G[F[B]]`を受け取って`G[F[B]]`として返します。traverse の時の例と似ていますが、今度は関数 g が`F[List[Account]]`を返すとします。

```scala
class ApplicativeContext[F[_]: Applicative] {
  def f: List[String] = ???
  def g(str: String): F[List[Account]] = ???
  def apply: F[List[Account]] = ???
}
```

この場合 apply を実装しようとするとどの様になるでしょうか。

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

flatTraverse を使わない場合を考えると、traverse をしたあとで、map + flatten などをすると実装できるでしょうか。

```scala
def apply: F[List[Account]] = f.traverse(g).map(_.flatten)
```

### flatTraverse を使うと・・・

flatTraverse を使う場合は以下のようになります。

```scala
def apply: F[List[Account]] = f.flatTraverse(g)
```

シンプルですね。

## mapWithIndex

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

名前の通り、map をするときに index 値と一緒に処理ができるような関数です。scala 関数では zipWithIndex という関数が馴染み深いと思いますが、そちらも Traverse に実装されています。cats バージョンの zipWithIndex は mapWithIndex + identity な関数で実装されています。

```scala
def zipWithIndex[A](fa: F[A]): F[(A, Int)] =
  mapWithIndex(fa)((a, i) => (a, i))
```

例えば、アルファベットの List があるとして、それを添字を追加した文字列に変更したい場合、どの様に実装するでしょうか。

```scala
val alphabets: List[Char] = ('a' to 'z').toList
```

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

まずは mapWithIndex を使わない場合を考えると、zipWithIndex + map で実装すると思います。

```scala
alphabets.zipWithIndex.map{ case (c, i) => s"$c$i" }
```

zip でタプルになった後に map するので case を使って書かなければいけないのがちょっとめんどくさいですね。

### mapWithIndex を使うと・・・

```scala
alphabets.mapWithIndex((c, i) => s"$c$i")
```

このように書くことが出来ます。

mapWithIndex の他には traverseWithIndexM という関数も用意されています。

```scala
def traverseWithIndexM[G[_], A, B](fa: F[A])(f: (A, Int) => G[B])(implicit G: Monad[G]): G[F[B]]
```

こちらは名前のとおり、traverse するときに index 値とともに処理を行うことができる様な関数になっています。受け取る関数の返り値が Monad であることを要求しているのが面白いポイントですね。実装例は割愛させていただきます。

---

## Traverse の関数の感想

traverse という強力な関数とそれを使って実装された関数をいくつかみていきました。型パズルをするにはなくてはならないような関数がたくさん発見できたと思います。Foldable に対して Reducible という NonEmpty なバージョンの型クラスがあった様に、Traverse にも NonEmptyTraverse という型クラスがあります。

これもまた Reducible と同じ様に NonEmptyList などが型クラスのインスタンスの例として挙げられますが、こちらも「存在する」のを知っているだけで一旦良さそうな気がするので説明等は割愛します。

# Bitraverse

Bifoldable に続く Bi シリーズのこちらの関数ですが、こちらもまた Either, Tuple2 の実例を通して挙動を確認していきましょう。

## bitraverse

```scala
def bitraverse[G[_]: Applicative, A, B, C, D](fab: F[A, B])(f: A => G[C], g: B => G[D]): G[F[C, D]]
```

traverse の bi バージョンのこちらですが、引数として受け取る２つの関数の返り値がどちらも Applicative に包まれている必要があります。わかりやすいのが Option だと思いますので、Either, Tuple2 と Option の組み合わせの挙動を見ていきましょう。まずは Either です。

```scala
1.asRight[String].bitraverse(_.some, _.some)
// Some(Right(1))
1.asRight[String].bitraverse(_ => none[String], _.some)
// Some(Right(1))
1.asRight[String].bitraverse(_.some, _ => none[Int])
// None
"test".asLeft[Int].bitraverse(_.some, _.some)
// Some(Left(test))
"test".asLeft[Int].bitraverse(_ => none[String], _.some)
// None
"test".asLeft[Int].bitraverse(_.some, _ => none[Int])
// Some(Left(test))
```

値が保持されている側の関数によって、traverse されていることがわかると思います。続いては Tuple2 です。

```scala
("test", 1).bitraverse(_.some, _.some)
// Some((test,1))
("test", 1).bitraverse(_ => none[String], _.some)
// None
("test", 1).bitraverse(_.some, _ => none[Int])
// None
```

どちらの結果も Some の場合だけ、Some として返ってくる事がわかると思います。面白いですね。bisequence も当然ありますが、だいたい想像できると思うので省略します。

## leftTraverse

```scala
def leftTraverse[G[_], C](f: A => G[C])(implicit F: Bitraverse[F], G: Applicative[G]): G[F[C, B]]
```

こちらは、left 側のみ traverse してくれる関数ですね。Either と Tuple2 の実例を見てみましょう。

```scala
1.asRight[String].leftTraverse(_.some)
// Some(Right(1))
1.asRight[String].leftTraverse(_ => none[String])
// Some(Right(1))
"test".asLeft[Int].leftTraverse(_.some)
// Some(Left(test))
"test".asLeft[Int].leftTraverse(_ => none[String])
// None
("test", 1).leftTraverse(_.some)
// Some((test,1))
("test", 1).leftTraverse(_ => none[String])
// None
```

想像した通りの結果になったのではないでしょうか。こちらも biSequence と同じ様に leftSequence という関数も存在しますが、割愛します。

## Bitraverse の関数の感想

Bifunctor, Bifoldable そして Bitraverse と Bi シリーズを見てきました。それぞれ Either, Tuple2 等の場合に取り回しがしやすくなるコードが発見できたのではないかと思います。

# TraverseFilter

```scala
trait TraverseFilter[F[_]] extends FunctorFilter[F]
```

続いては TraverseFilter です。こちらの型クラスは、FunctorFilter を継承していますね。

## filterA

```scala
def filterA[G[_], A](fa: F[A])(f: A => G[Boolean])(implicit G: Applicative[G]): G[F[A]]
```

こちらの関数は、引数として受け取る関数の返り値が Applicative に包まれている Boolean になっています。例えば DB アクセスを伴う場合によく起こると思いますが、

AccountId がデータベースに存在するか確かめるための関数 exists があるとします。返り値は`F[Boolean]`になっていますね。その関数を使ってアカウント一覧を存在するものだけにフィルタリングしてみたいとします。

```scala
class ApplicativeContext[F[_]: Applicative] {
  def exists(accountId: AccountId): F[Boolean] = ???
  val accounts: List[Account] = ???
  def apply: F[List[Account]] = ???
}
```

関数 apply を実装することを考えてみましょう。副作用をまとめた`F[List[Account]]`として取得したい場合を考えてみましょう。

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

まずは filterA を使わない場合を考えてみましょう。

```scala
def apply: F[List[Account]] =
  accounts
    .traverse(account => exists(account.id).map(account -> _))
    .map(_.collect { case (account, true) => account })
```

結構辛いですね。。もっとシンプルに書く方法はあると思うんですが、私が思いついたのは、traverse で`F[List[(Account, Boolean)]]`にした後で、true のものだけ Account を取得する感じの実装です。Boolean が F に包まれているだけなのに結構複雑な実装が必要になってしまうと思います。

### filterA を使うと・・・

```scala
def apply: F[List[Account]] = accounts.filterA(account => exists(account.id))
```

シンプルですね。この関数を知らない場合、実装がめんどくさくてしょうがないと思います。

## traverseFilter

```scala
def traverseFilter[G[_], A, B](fa: F[A])(f: A => G[Option[B]])(implicit G: Applicative[G]): G[F[B]]
```

こちらの関数は、ご覧の通り`A => G[Option[B]]`の関数を受け取って`G[F[B]]`を返す関数になります。今度は AccountId の一覧から、データベースに存在するアカウント一覧をとってきたい場合を考えてみましょう。

```scala
class ApplicativeContext[F[_]: Applicative] {
  def f(accountId: AccountId): F[Option[Account]] = ???
  val accountIds: List[AccountId] = ???
  def apply: F[List[Account]] = ???
}
```

accountIds を元に関数 f を使って、関数 apply を実装したい場合を考えてみます。

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

まずは traverseFilter を使わない場合の実装を考えて見ると、

```scala
def apply: F[List[Account]] = accountIds.traverse(f).map(_.flattenOption)
```

このように、traverse で`F[List[Option[Account]]]`にした後、flattenOption などを使って`F[List[Account]]`にするかと思います。

### traverseFilter を使うと・・・

traverseFilter を使うと、

```scala
def apply: F[List[Account]] = accountIds.traverseFilter(f)
```

このようになります。シンプルですね。sequenceFilter という traverseFilter を特殊化した関数も存在しますが説明は割愛させていただきます。

```scala
def sequenceFilter[G[_], A](fgoa: F[G[Option[A]]])(implicit G: Applicative[G]): G[F[A]] =
  traverseFilter(fgoa)(identity)
```

## traverseEither

```scala
def traverseEither[G[_], A, B, E](fa: F[A])(f: A => G[Either[E, B]])(g: (A, E) => G[Unit])(implicit G: Monad[G]): G[F[B]]
```

ものすごい複雑な定義になっていますね。。`A => G[Either[E, B]]`と`(A, E) => G[Unit]`を受け取って`G[F[B]]`を返す関数みたいです。なんのこっちゃって感じですね。。

```scala
class MonadContext[F[_]: Monad: Logger] {
  def f(accountId: AccountId): F[Either[Throwable, Account]] = ???
  val accountIds: List[AccountId] = ???
  def apply: F[List[Account]] = ???
}
```

先ほどと同じような例ですが、Monad のコンテキストにおいて、関数 f が`F[Option[Account]]`ではなく`F[Either[Throwable, Account]]`を返すとします。副作用とは別に失敗した理由を返したいケースってありますよね。

そのときに、エラーだった場合エラーログに吐き出しつつ、エラーじゃない結果を集めたいときにこの関数が使えそうです。関数 apply を実装すると、

```scala
def apply: F[List[Account]] =
  accountIds.traverseEither(f)((accountId, error) => Logger[F].error(s"${error.getMessage} by $accountId"))
```

このようになります。実装してみると用途がわかりやすくなりますね。コーディングの幅が広がる良い関数を発見できたと思います。

## TraverseFilter の関数の感想

個人的にはもともと filterA はとても使い勝手が良くて好きな関数として認識していましたが、他の関数も場面にマッチすると、とても簡潔にコードが書けるようになる強力な関数だと思いました。

---

# おわりに

Foldable から始まって Traverse, TraverseFilter まで非常に多くの関数をみてきました。cats を使ったコーディングをする上でとても強力な関数をたくさん発見できたと思います。

# まとめ

4 記事を通して、Functor ~ TraverseFilter までたくさんの型クラスに実装された関数を見てきました。

Qiita ではないのですが、[Cats の関数覚え書き](https://developers.microad.co.jp/entry/2021/12/13/120000)という記事を別途マイクロアド社の技術ブログに寄稿しまして、

- Alternative
- Align
- CoflatMap

という型クラスの関数について書かせていただいています。

これらの関数を見てきた感想としては「Scala のこれまでの実装は何でもかんでも map, flatMap を使ってコーディングしてきたんだなぁ」というものでした。cats によってより目的に沿った関数を使えるようになり、それがこれまでよりやりたいことを明確に表現できるようになることに繋がると思いました。

cats (や cats effect)を使っての実装は、scala の標準で私たちがコーディングしてきたものと比較して、副作用を`F[_]`として分離して構築していく部分に大きな違いがあります。

これまでは主に Unit な処理としてクラスの各所に書き捨てていたロギングや、データベースアクセス(コネクション)の成功失敗としての Either, Try、システム時間の取得、などさまざまな副作用について、F としてまとめあげたり F のままで中身をいじったりする必要があり、scala 標準に用意されている関数だけでは辛くなる部分が多々ありました。今回 cats が用意してくれている関数とその使い方を知ることができて、それらに立ち向かう力が身についたように思います。

ですが、今回見てきた型クラスは cats のごく一部であり、まだまだ勉強することはたくさんあります。今のところ「勉強しなきゃまずいな」と感じているものの例を挙げると、

- Ior, Validated, NonEmptyList など cats.data パッケージに定義されてる様々なデータ型
- cats effect 系のクラス

などがあります。今回書いた４つの記事のその先として今後、また書いていきたいと思っています。