Cats のなんか地味なデータタイプ5選（練習問題付き）

Cats 提供のデータタイプから、よく見かけるけどあまり使ったことがない、あるいは何となく知ってる気がするけどよく分かってない気もするような、地味なものを5選。

選んだのは、Chain、Const、Eval、Ior、Nested。[^data-type-choice]

それぞれについて、簡単なメモと、忘れたころに復習できるような練習問題を書いた。

Cats/Cats Effect のバージョンは `2.0.0-RC1`。[kind-projector](https://github.com/typelevel/kind-projector) も適宜併用。

## Chain／NonEmptyChain
- prepend だけじゃなく、append も $O(1)$ で処理できる、効率的なデータコレクション
- Writer のログとか、Validated や Ior の Left 側など、Monoid が求められているところで List や Vector に替えてこの Chain を使うと、良いパフォーマンスが得られるという。

#### 練習問題 1
下のコードでコンパイルできない行が3つある。どれか。

```scala
import cats.{ Semigroup, Monoid }
def x1[A] = implicitly[Semigroup[Chain[A]]]
def x2[A] = implicitly[Semigroup[NonEmptyChain[A]]]
def x3[A] = implicitly[Monoid[Chain[A]]]
def x4[A] = implicitly[Monoid[NonEmptyChain[A]]]

import cats.{ Semigroupal, SemigroupK, MonoidK }
def y1 = implicitly[Semigroupal[Chain]]
def y2 = implicitly[Semigroupal[NonEmptyChain]]
def y3 = implicitly[SemigroupK[Chain]]
def y4 = implicitly[SemigroupK[NonEmptyChain]]
def y5 = implicitly[MonoidK[Chain]]
def y6 = implicitly[MonoidK[NonEmptyChain]]

import cats.{ CoflatMap, Comonad }
def z1 = implicitly[CoflatMap[Chain]]
def z2 = implicitly[CoflatMap[NonEmptyChain]]
def z3 = implicitly[Comonad[Chain]]
def z4 = implicitly[Comonad[NonEmptyChain]]
```


<details><summary>答え</summary><div>
- **x4**: NonEmpty〜 だから単位元がないので Monoid にならない
- **y6**: x4 と同様
- **z3**: 空の `Chain`からは値が取り出しようがないので `Comonad` にならない（`extract`が書けない）
</div>
`NonEmptyTraverse`や`TraverseFilter`についても同様に理解できる。

## Const
- `Const[A, X]` は、型A の値を保持するが、型X の方は実質的な値を持たず、型合わせにしか使わないファントムタイプ
- Scala 標準の `Function.const`[^scala-const]の考え方を、型に敷衍したようなもの
- `Const[A, ?]` を `F[?]` として捉えて、いろんな型クラスを導く使い方が多い。
- 下の練習問題は [Cats のドキュメント](https://typelevel.org/cats/api/cats/data/Const.html)からの引用をベースにした。

[^scala-const]: `def const[T, U](x: T)(y: U): T = x`

#### 練習問題 1
以下の簡単な [Lens](http://functional-wizardry.blogspot.com/2014/02/lens-implementation-part-1.html) は、`modifyF` と適当な函手を組み合わせると、それを使って `set` も `get` も書けるという知見にもとづいて、`set` だけ書いている。つづけて未実装の `get` と `Functor[Const[X, ?]]` を完成させたい。どう書くか？

```scala
implicit def constFunctor[X]: Functor[Const[X, ?]] = ???

trait Lens[S, A] {
  def modifyF[F[_]: Functor](s: S)(f: A => F[A]): F[S] // これだけあれば get も set も書ける
  def modify(s: S)(f: A => A): S = modifyF[Id](s)(f)
  def set(s: S, a: A): S = modify(s)(_ => a)
  def get(s: S): A = ???
}
```
<details><summary>実装例</summary><div>

```scala
implicit def constFunctor[X]: Functor[Const[X, ?]] = new Functor[Const[X, ?]] {
  def map[A, B](fa: Const[X, A])(f: A => B): Const[X, B] = Const(fa.getConst)
}
trait Lens[S, A] {
  ...
  def get(s: S): A = modifyF[Const[A, ?]](s)(Const(_)).getConst
}
```
</div></details>

#### 練習問題 2
下のような書きかけの `Traverse` がある[^traverse_excuse]。`traverse` を使って `foldMap` を書くにはどうするか。 `Applicative[Const[X, ?]]` も実装する必要がある。

```scala
implicit def constApplicative[X: Monoid]: Applicative[Const[X, ?]] = ???
trait Traverse[F[_]] {
  def traverse[G[_]: Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]]
  def foldMap[A, B: Monoid](fa: F[A])(f: A => B): B = ???
}

```
[^traverse_excuse]: 本来、`Traverse` は `Foldable` を継承しているが割愛した。

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

```scala
implicit def constApplicative[X: Monoid]: Applicative[Const[X, ?]] = new Applicative[Const[X, ?]] {
  import cats.syntax.semigroup._
  def pure[A](x: A): Const[X, A] = Const(Monoid[X].empty)
  def ap[A, B](ff: Const[X, A => B])(fa: Const[X, A]): Const[X, B] =
    Const(ff.getConst |+| fa.getConst) // AとかBとかA=>Bとか全然関係ないのがポイント
}
trait Traverse[F[_]] {
  ...
  def foldMap[A, B: Monoid](fa: F[A])(f: A => B): B =
    traverse[Const[B, ?], A, Nothing](fa)(a => Const(f(a))).getConst
}
```
別解: 上の `Applicative` 実装では [Catsの解説](https://typelevel.org/cats/datatypes/const.html#example-2-traverse)を参考にしたが、実際の Cats実装では以下のような感じになっている。

```scala
  def pure[A](x: A): Const[X, A] = Const.empty
  def ap[A, B](ff: Const[X, A => B])(fa: Const[X, A]): Const[X, B] =
    ff.retag[B] combine fa.retag[B]
```

</div></details>

## Eval
- トランポリンを使って同期評価をコントロールするモナド(コモナドのインスタンスもある)
- 評価戦略として、now、later、always がある
  - Now: 即時評価。`val`のようなもの。
  - Later: 遅延評価。`lazy val` のようなもの[^eval-later-advantage]。
  - Always: 随時評価。`def` のようなもの。
- 値を取り出すにはメソッド`value`を使う。評価戦略と評価実行との間に以下のような関係がある。

|               | now  | later | always |
|:-:|:-:|:-:|:-:|
| Eval 生成時    |  ○   |   ×   |   ×
| value 初回     |  ×   |   ○   |   ○
| value 2回目以降 |  ×  |   ×   |   ○

[^eval-later-advantage]: ガーベジコレクションや排他ロックの面で、lazy val にない利点があるという。

#### 練習問題
下の `StackUnsafeMutualRecursion` は、相互再帰を使って自然数の偶奇を判定する。ただし、ちょっと大きめの数を与えるとすぐに `StackOverflowError` が送出されてしまう。

相互再帰の形を残したまま、`Eval` を使ってスタックセーフするにはどうするか？ ([Catsの Eval のサンプル](https://typelevel.org/cats/datatypes/eval.html#chaining-lazy-computations)を若干改変)

```scala
object StackUnsafeMutualRecursion {
  def even(n: Int): Boolean = n == 0 || odd(n - 1)
  def odd(n: Int):  Boolean = n > 0  && even(n - 1)
}
// StackUnsafeMutualRecursion.even(199999) → java.lang.StackOverflowError が投げられる

import cats.syntax.flatMap._
object StackSafeMutualRecursion {
  import Eval._
  def even(n: Int): Eval[Boolean] = ???
  def odd(n: Int):  Eval[Boolean] = ???
}
StackSafeMutualRecursion.even(199999).value
// false
```

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

```scala
def even(n: Int): Eval[Boolean] = now(n == 0).ifM(True,  odd(n - 1))
def odd(n: Int):  Eval[Boolean] = now(n == 0).ifM(False, even(n - 1))
```
</div></details>

## Ior
- 日本語で言えば、「A、B のどちらか、またはどちらも」といった意味の型。
- `Either[A, B]` では `Left[A]` か `Right[B]` かどちらかだったが、`Ior[A, B]` ではさらに `Both[A, B]` も加わる。
- **I**nclusive-**or** の略で、Either と同様に右バイアス[^exclusize-or]。

#### 練習問題
文字列リストの各要素を整数として解釈し、その合計を返す関数を書こうとしている。ただし、整数に変換できない文字列は、2個までは許容、3個以上はエラーとする。またエラーとなった文字列も、結果に含めておきたい。

- 空リスト ⇒ Right(0)
- ['5', '-1', '-2'] ⇒ Right(2)
- ['5', '-I', '-2'] ⇒ Both(['-I'], 3)
- ['S', '-I', '-Z'] ⇒ Left(['S', '-I', 'S'])

下のコードで、未実装の関数 `tryToInt`、`empty`、`combine` を完成して、`foldLeft` と組み合わせると、期待通りの関数`sum`が得られる。どんなふうに書けるか？

```scala
import cats.data.{ Ior, NonEmptyChain => Nec }
import cats.implicits._
import scala.util.Try

type StrNec = Nec[String]

def tryToInt(s: String): StrNec Ior Int = ???
val empty: StrNec Ior Int = ???
val combine: (StrNec Ior Int, StrNec Ior Int) => StrNec Ior Int = ???

def sum(l: List[String]): StrNec Ior Int =
  l.foldLeft(empty)((acc, e) => combine(acc, tryToInt(e)))
```
<details><summary>実装例</summary><div>

```scala
def tryToInt(s: String): StrNec Ior Int =
  Try(s.toInt).fold(_ => Ior.leftNec(s), Ior.right)

val empty: StrNec Ior Int = Ior.right(0) // 0 の代りに Monoid[Int].empty でも可

val combine: (StrNec Ior Int, StrNec Ior Int) => StrNec Ior Int = {
  case (Ior.Both(l1, _), Ior.Left(l2)) if l1.length == 2 => Ior.left(l1 ++ l2)
  case (x@Ior.Left(_), _) => x
  case (x, y) => x combine y
}
```
</div>

#### おまけ問題
上例では、関数に `empty`、`combine` といったモノイドぽい名前を与えているが、実際に implicit なモノイドとして構成すると、`foldMap` を使って少しシンプルに書ける。あえてそうしなかった理由があるが何か？

<details><summary>答え</summary><div>
下のように書いても動くことは動くが、[モノイド則](https://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%8E%E3%82%A4%E3%83%89#%E5%AE%9A%E7%BE%A9)を満たさないので紛らわしいから[^monoid_disciplie]。

```scala
implicit val unlawfulMonoid: Monoid[StrNec Ior Int] = new Monoid[StrNec Ior Int] {
  def empty: cats.data.Ior[StrNec,Int] = 〜
  def combine(x: StrNec Ior Int, y: StrNec Ior Int): StrNec Ior Int = 〜
}
def sum(l: List[String]): StrNec Ior Int = l foldMap tryToInt
```
[^monoid_disciplie]: ScalaCheck + Discipline でテストを書けば、どういう値でどの法則を満たさないのか報告してくれて、とても便利。
</div>


## Nested
- 入れ子になったエフェクトを一体にして扱うためのデータタイプ
- `x: F[G[A]]` に対する `x.map(_.map(f))` と同じことが、`n: Nested[F, G, A]`なら `n.map(f).value` と書ける
- モナドトランスフォーマーに似ているが、もっと一般的に、`F[_]`、`G[_]` の型クラスから `Nested[F[_], G[_], ?]`の型クラスインスタンスが導出される
- 導出される型クラスとそのルールは、[Cats のドキュメント](https://typelevel.org/cats/datatypes/nested.html)でも一部紹介されているが、[実際は](https://github.com/typelevel/cats/blob/master/core/src/main/scala/cats/data/Nested.scala)もっといろんな型クラスインスタンスが定義されている[^nested-distributive]。
 
[^nested-distributive]: Nested の Distributive インスタンスについて以前[この記事](https://qiita.com/yasuabe2613/items/956402d8fdd06341e56f#nested)に書いた

#### 練習問題
下記コードの `createUser` は、与えられた名前から `User(id, name)` を生成するが、ID 生成の不純なロジックを`F[_]: Sync`にくるんでいるのと、名前の空文字チェックのために結果を `ValidatedNec` に入れているために、結果型でエフェクトがネストしている。

この`createUser`を使って、「文字列のリスト」から 「`User` のリスト」を生成したい。`Nested`を使う版、使わない版の両方の `createUsers`を書いてみよう。

```scala
import cats.data.{ ValidatedNec, Nested, Validated }
import cats.effect.{ Sync, IO }
import scala.util.Random
import cats.implicits._

case class User(id: Int, name: String)
type ErrorsOr[X] = ValidatedNec[String, X]

def generateId[F[_]: Sync]: F[Int] = Sync[F].delay(new Random().nextInt)

def validateName(s: String): ErrorsOr[User] =
  Validated.condNec(s.nonEmpty, name, s"empty string")

def createUser[F[_]: Sync](name: String): F[ErrorsOr[User]] =
  validateName(name).map(n => generateId.map(User(_, n))).sequence

def createUsers[F[_]: Sync](ui: List[String]): F[ErrorsOr[List[User]]] = ???
```
<details><summary>実装例</summary><div>

```scala
// Nested 使わない版
def createUsers[F[_]: Sync](ui: List[String]): F[ErrorsOr[List[User]]] =
  ui.traverse(n => createUser(n)).map(_.sequence)

// Nested 使う版
def createUsers[F[_]: Sync](ui: List[String]): F[ErrorsOr[List[User]]] =
  ui.traverse(n => Nested(createUser[F](n))).value

createUsers[IO](List("Alice", "Bob")).unsafeRunSync()
// res0: ErrorsOr[List[User]] = Valid(List(User(-800596771,Alice), User(2036091365,Bob)))
createUsers[IO](List("", "Bob")).unsafeRunSync()
// res1: ErrorsOr[List[User]] = Invalid(Chain(empty string))
```
</div>

[^data-type-choice]: [Cats のデータタイプの解説](https://typelevel.org/cats/datatypes.html)から選んだ。ContT などは地味ではなくむしろ注目を浴びてるし、Id・Reader・Writer・State・Klisli は定番すぎるし、Validated などは割と使われている気がするしで、この記事では選外とした。別の機会に書くかもしれない。

[^exclusize-or]: 昔の Cats には、右バイアス exclusive-or を表す `Xor` という型があったが、Scala 標準の Either が右バイアスになったので無くなった（[issue 1192](https://github.com/typelevel/cats/issues/1192)）。