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

この記事は MicroAd Advent Calendar 2021 の 22 日目の記事です。

記事としては
- Cats の関数覚え書き(Functor, Apply, Applicative, FlatMap)
- Cats の関数覚え書き(ApplicativeError, MonadError)
- 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

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

使用するクラスについて

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

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

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

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

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

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

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

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

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

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 を使わないで書くと、

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

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

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

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

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

Foldable

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

combineAll

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

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

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

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

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

combineAll を使わないと・・・

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

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

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

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

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

combineAll を使うと・・・

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

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 を使うことが出来ます。

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

便利ですね。

combineAllOption

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

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

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 関数のようなものを実装する必要がありますね。

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

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

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

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

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

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

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

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

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

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

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

combineAllOption を使うと・・・

def apply: Option[Accounts] = accountsList.combineAllOption

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

collectFold

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

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

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) として処理を書いたり、

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

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

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

collectFold を使うと・・・

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

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

collectFoldSome

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 の総額を出したいという場合、

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 じゃない場合は、

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

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

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

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

collectFoldSome を使うと・・・

accountIds.collectFoldSome(moneyById.get)

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

reduceLeftToOption

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

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

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

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

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

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

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

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

reduceLeftToOption を使わないと・・・

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

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

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

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

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

reduceLeftToOption を使うと・・・

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

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

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

minimumOption, maximumOption

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

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 として抽象化されている場合に使うケースが出てくるのかなと思っています。

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

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

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

get

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

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

collectFirstSome

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

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

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

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

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

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

collectFirstSome を使わないと・・・

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

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

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

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

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

collectFirstSome を使うと・・・

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

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

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

foldMap

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

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

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

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

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

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

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

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

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

foldMap を使わないと・・・

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

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 で両替しながら畳み込むなどすると思います。

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

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

foldMap を使うと・・・

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

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

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

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

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

intercalate

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

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

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

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

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

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

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

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 が修理代金だな・・・」みたいに計算すると思います。

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

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

intercalate を使わないと・・・

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

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 の実装としては以下のようになるかと思います。

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 の型クラスのインスタンスにしましょう。

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

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

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

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

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

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 の定義になります。

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

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

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

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

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

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

foldMapA

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]になることが出来ます。

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

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

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 なコンテキストに包まれて返ってくる場合を考えてみます。データベースが絡んだりすると、よくある処理になると思います。

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]を得ようと思っているとします。

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

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

foldMapA を使わないと・・・

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

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

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

foldMapA を使うと・・・

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

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

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

collectFirstSomeM

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[_]]の様な型として返ってくることが多いんですね。

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]]が最初に見つかった時点で走査を止めることを考慮すると難しそうな気がするので、そこは置いておくとして、

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

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

collectFirstSomeM を使うと・・・

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

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

findM

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

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

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

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

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 に定義された関数を使えば実装自体はできると思います。

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

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

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

findM を使うと・・・

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

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

foldM

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 という名前が用意されていることでもこれらの関数の関係が深いことがわかると思います。

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 として定義されていない場合を考えます。

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 を使って両替し畳み込むような処理として実装したいとします。

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

foldM を使わないと・・・

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

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

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

foldM を使うと・・・

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

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

foldMapM

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 を使うことになるんでしょう。

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

existsM(forallM)

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 が存在するかというのを知りたい場合を想定します。

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 すればできるでしょうか。

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

なんだか辛いですね。

existM を使うと・・・

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

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

foldK

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

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

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

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

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

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

foldK を使わないと・・・

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

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

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

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

よくやりますよね。

foldK を使うと・・・

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

def apply: Set[Int] = f.foldK

とても良いですね。

foldMapK

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 に包まれている値である必要があるんですね。

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 をすると思います。

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

foldMapK を使うと・・・

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

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

sliding**

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

partitionEither

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 のリストに対してそれを当てて、失敗と成功の結果をそれぞれリストで持ちたい場合を考えてみましょう。

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 という今回の用途にぴったりの関数がありました。

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

partitionEither を使うと・・・

partitionEither を使ってみると、

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

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

partitionBifold

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 に変更することも出来ます。

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

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

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

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

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

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

partitionEitherM

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 の定義です。

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 を返す様になってしまったとしても、

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

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

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

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

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

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

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

bifoldMap

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 両方の挙動をみてみましょう。

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 の定義です。

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

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

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

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

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

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

bifoldLeft

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

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

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 を見てみましょう。

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

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

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

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

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

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 の型クラスのインスタンスのクラスがあるとして、

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

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

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

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

蛇足ですが・・・

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

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 という型クラス名になったのかなと思います。

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

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

sequence

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 の組み合わせの挙動を見てみましょう。

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 の実装をみると理解が深まると思います。

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 の組み合わせを見てみましょう。

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 定義をみてみましょう。

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_

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

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

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

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

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

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

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

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

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

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

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

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

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

Foldable::sequence_ を使うと・・・

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

def apply: F[Unit] = f.sequence_

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

flatSequence

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]にしたいなぁ」と思う場面が多いです。

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

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

traverse

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

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

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

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

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 で実装できると思います。

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

traverse を使うと・・・

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

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

Foldable::traverse_

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

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

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

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

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

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

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

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

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

Foldable::traverse_ を使うと・・・

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

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

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

traverseTap

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 なのでわかりやすい例はやはりロギングでしょうか。

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 でロギングの返り値を変えてあげると実装できそうです。

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

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

traverseTap を使うと・・・

そこで traverseTap を使うと、

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

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

flatTraverse

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]]を返すとします。

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 などをすると実装できるでしょうか。

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

flatTraverse を使うと・・・

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

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

シンプルですね。

mapWithIndex

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

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

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

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

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

mapWithIndex を使わないと・・・

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

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

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

mapWithIndex を使うと・・・

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

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

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

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

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 です。

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 です。

("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

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

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

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

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

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

filterA

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]になっていますね。その関数を使ってアカウント一覧を存在するものだけにフィルタリングしてみたいとします。

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 を使わない場合を考えてみましょう。

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 を使うと・・・

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

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

traverseFilter

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 の一覧から、データベースに存在するアカウント一覧をとってきたい場合を考えてみましょう。

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 を使わない場合の実装を考えて見ると、

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

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

traverseFilter を使うと・・・

traverseFilter を使うと、

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

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

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

traverseEither

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]]を返す関数みたいです。なんのこっちゃって感じですね。。

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 を実装すると、

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 の関数覚え書きという記事を別途マイクロアド社の技術ブログに寄稿しまして、

• 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 系のクラス

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