Iota で Free モナドの合成を少しだけシンプルにする

Free monad の ADT合成を少しだけ簡単にするライブラリ Iota の紹介。

## はじめに
2016年11月ごろに読んだ『[Functional Reactive Domain Modeling](https://www.manning.com/books/functional-and-reactive-domain-modeling)』(以下、FRDM)で、DDD のコーディングに **Free モナド** を使う手法が紹介されていた。当時は、Free モナドといっても「なんか 『[FP in Scala](https://www.manning.com/books/functional-programming-in-scala)』 に載ってたトランポリンが何かあれするやつだっけ？」くらいのイメージしかなかったが、FRDM ではわかりやすい解説でビジネスロジックでの Free モナドの有用性がすぐにわかった。

とはいっても、それなりに複雑な現実のドメインのコードでの活用を考えると、いくつか不安点が残った。その中の一つに「代数（ADT）が多くなった場合、型を合成するコードがややこしくなりそう」というものがあったが、Iota というライブラリを使うとある程度解消できそうだとわかったので、cats の `Free` の復習をかねて紹介する。

## Iota で解決したい問題
cats ドキュメントの [Composing Free monads ADTs](https://typelevel.org/cats/datatypes/freemonad.html#composing-free-monads-adts) のコード例だと「代数」がたった二つなので、`EitherK`, `InjectK`, `FunctionK#or` あたりを使ってれば事足りるように見えるが、少し代数を増やそうとすると、とたんにややこしさが急増する。

まず `EitherK` の合成が、ADT を AlgeX, AlgeY, AlgeZ のたった三つにした時点で 、すでに以下のように読みにくい。

```scala
type AlgeAll[A] = EitherK[AlgeX, EitherK[AlgeY, AlgeZ, ?], A]
```

さらに、これを実行するインタプリタも合成することになるが、、cats のサンプルに倣って FunctionK#orで単純につなげると結合が逆になってしまう。

```scala
val x2Id: (AlgeX ~> Id) = ???
val y2Id: (AlgeY ~> Id) = ???
val z2Id: (AlgeZ ~> Id) = ???
val all2Id = x2Id or y2Id or z2Id
// 欲しい型は右結合の
// FunctionK[EitherK[AlgeX, EitherK[AlgeY, Alge, _], _], Id]なのに
// 得られるのは左結合の
// FunctionK[EitherK[EitherK[AlgeX, AlgeY, _], Alge, _], Id]になる
```

カッコでくくって型アノテーションを明示すれば右結合にできないこともないが、コードがごちゃごちゃするので悩ましい。

調べてみると [Iota](https://github.com/frees-io/iota) というライブラリが良さそうだとわかった。「任意の数の型の *disjunction* 」のための小さなライブラリで、Cats 用と Scalaz 用がそれぞれ提供されている。ここでは Cats 版を使ってみる。

## 試行
cats ドキュメントの [Composeing Free monads ADTs](https://typelevel.org/cats/datatypes/freemonad.html#composing-free-monads-adts) サンプルを改編して、Iota を試してみた 。

### 代数
Free monad を使ったコーディング作法ではいわゆる代数(algebra)をまず定義することになる。ベースにする [cats のサンプルコード](https://typelevel.org/cats/datatypes/freemonad.html)では、`Interact` と `DataOp` の2つだけだったが、複雑さを加えるため三つめの代数 `KVStoreOp` を追加する。

```scala
sealed trait Interact[A]
case class Ask(prompt: String) extends Interact[String]
case class Tell(msg: String)   extends Interact[Unit]

sealed trait DataOp[A]
case class AddCat(a: String) extends DataOp[Unit]
case class GetAllCats()      extends DataOp[List[String]]

sealed trait KVStoreOp[A]
case class GetCat(k: String)            extends KVStoreOp[Option[String]]
case class PutCat(k: String, v: String) extends KVStoreOp[Unit]
```

これらの代数を使う側では、`Free[CatsApp, _]` として一まとめに合成して扱うが、そのために役立つのが Iota　の `:::` 演算子で、`F[_]` となるような「型の余積」を作る。[^shapeless_coproduct]

```scala
import iota.TListK.:::
import iota.{CopK, TNilK}

type CatsApp[A] = CopK[Interact ::: DataOp ::: KVStoreOp ::: TNilK, A]
```
`EitherK` を入れ子にすることを想像すると格段にスッキリしているのが分かる。

[^shapeless_coproduct]: shapeless の `Coproduct` や `:+:` と似ている

### リフト
代数を Free monad にリフトするコードは以下のようになる。もとの [cats のサンプル ](https://typelevel.org/cats/datatypes/freemonad.html#composing-free-monads-adts)で `EitherK` を使っているところを、Iota の `CopK` に替えている以外はほぼ同じ。

```scala
import cats.free.Free.inject
import scala.language.higherKinds
class Interacts2[G[α] <: iota.CopK[_, α]](implicit I: CopK.Inject[Interact, G]) {
  def ask(prompt: String): Free[G, String] = inject[Interact, G](Ask(prompt))
  def tell(msg: String):   Free[G, Unit]   = inject[Interact, G](Tell(msg))
}
object Interacts {
  implicit def interacts[F[α] <: iota.CopK[_, α]](implicit I: CopK.Inject[Interact, F]): Interacts2[F] =
    new Interacts2[F]
}

class DataSource[F[α] <: iota.CopK[_, α]](implicit I: CopK.Inject[DataOp, F]) {
  def addCat(a: String): Free[F, Unit]         = inject[DataOp, F](AddCat(a))
  def getAllCats:        Free[F, List[String]] = inject[DataOp, F](GetAllCats())
}
object DataSource {
  implicit def dataSource[F[α] <: iota.CopK[_, α]](implicit I: CopK.Inject[DataOp, F]): DataSource[F] =
    new DataSource[F]
}

class KVStore[F[α] <: iota.CopK[_, α]](implicit I: CopK.Inject[KVStoreOp, F]) {
  def getCat(k: String):            Free[F, Option[String]] = inject[KVStoreOp, F](GetCat(k))
  def putCat(k: String, v: String): Free[F, Unit]           = inject[KVStoreOp, F](PutCat(k, v))
}
object KVStore {
  implicit def kvStore[F[α] <: iota.CopK[_, α]](implicit I: CopK.Inject[KVStoreOp, F]): KVStore[F] =
    new KVStore[F]
}
```
ちなみに、この手のボイラープレートをマクロで生成するツールに [Freestyle](http://frees.io/docs/) [^freestyle]というものもある。

[^freestyle]: コード量は大幅に減るが、自動生成される型やメソッドについてかなり慣れがいるのと、現時点（2017年12月ごろ）では`IntelliJ`の`Scala`プラグインとの相性がまだあまりよくなさそう。

### 合成された代数を使う側
以下のようなドメイン層サービスを考えてみる。
1. ユーザに猫の名前を聞いて、
2. それをデータベースに追加して、
3. キーバリューストアにあるか見に行って、
4. まだなかったら追加して、
5. データベースから現時点の全ての猫を引いてきて、
6. 文字列にして返す

```scala
object CatsService {
  def doSomething[A](implicit I: Interacts[CatsApp], D: DataSource[CatsApp], K: KVStore[CatsApp])
    : Free[CatsApp, Unit] = {
    for {
      cat <- I.ask("kitty's name?")
      _   <- D.addCat(cat)
      s   <- K.getCat(cat)
      _   <- s.fold(K.putCat("name", cat))(_ => Free.pure(()))
      all <- D.getAllCats
      _   <- I.tell(all.toString)
    } yield ()
  }
}
```

###実行-テスト
実際にはアプリケーションサービスから実行することになるが、ここではテストコーディングを想定して `State` モナドで実行してみる。

まず `List` を「状態」として持つ `State` のエイリアス `Operations` を以下のように定義する。

```scala
type Operations[T] = State[Chain[Any], T]
import State.modify

def add[T](fa: Any)(f: => T = ()): Operations[T] =
  modify[Chain[Any]](_ :+ fa).map(_ => f)
```

また、代数ごとの個別インタープリターは、Catsの「自然変換」[^not_a_natural_transformation]`FunctionK`（の型エイリアス `~>` ）を使って以下のように定義する。

[^not_a_natural_transformation]: 圏論の「自然変換」とは厳密には違うが、なんとなく "natural transformation" と言われることが多い。

```scala
implicit val kvToStateInterpreter: Interact ~> Operations =
  new (Interact ~> Operations) {
    override def apply[A](fa: Interact[A]): Operations[A] = fa match {
      case Ask(_)  => add(fa)("mike")
      case Tell(_) => add(fa)()
    }
  }
implicit val dataOpStateIntpr: DataOp ~> Operations =
  new (DataOp ~> Operations) {
    override def apply[A](fa: DataOp[A]) = fa match {
      case AddCat(_)    => add(fa)()
      case GetAllCats() => add(fa)(List("kuro", "tama", "uni"))
    }
  }
implicit val kbStoreStateIntpr: KVStoreOp ~> Operations =
  new (KVStoreOp ~> Operations) {
    override def apply[A](fa: KVStoreOp[A]) = fa match {
      case PutCat(_, _) => add(fa)()
      case GetCat(_)    => add(fa)(None)
    }
  }
```

テスト用インタープリター全体を組み上げるには、以下のように `CopK.FunctionK.of` を使ってこれらを合成する。結果として、上で `:::` を使って合成した代数 `CatsApp` に対応する自然変換 `CatsApp ~> Operations` が得られる。

```scala
val catAppStateInterpreter: CatsApp ~> Operations = CopK.FunctionK.of(
  kvToStateInterpreter, dataOpStateIntpr, kbStoreStateIntpr)
```

以下のように実行すると、最終計算結果と仮実行された「代数」のリストが `State` の `value` で取れるので、テストコードで確認できる。

```
CatsService.doSomething.foldMap(catAppStateInterpreter).run(List.empty[Any]).value
// res0: (List[Any], Unit) = (List(
//   Ask(kitty's name?),
//   AddCat(mike),
//   GetCat(mike),
//   PutCat(name,mike),
//   GetAllCats(),
//   Tell(List(kuro, tama, uni))),
// ())
```

さらに工夫すれば、代数の「呼び出し」を記録するだけじゃなく振る舞い=出力値も指定できる様にして、BDDツールみたいなシナリオベースのテストも書ける。(← [書いてみた](https://qiita.com/yasuabe1362/items/911b925bc2c67c3dd6f9) 2017/12/07)

## 結論
Free モナドを実戦で導入するときには検討してみるといいかもしれない。

## 補足
- Cats は `v2.0.0`、Iota は `0.3.10` を使った
- 実際に動くソースは、IntelliJ の Scala Worksheet として[ここ](https://gist.github.com/yasuabe/584798aea7807bd9d4e834b4ab4e92cb)に置いた 
- 2019/10/05 に ライブラリの版を更新して記事を刷新した
  - 今のところ Iota 側での Scala 2.13 対応予定は無いようなので、2.12.8 で据え置いた。