Distributive という地味な型クラス 〜 Traverse の双対

Traverse の双対である Distributive という Cats の型クラスについて

## はじめに
Cats の [型クラス階層](https://cdn.rawgit.com/tpolecat/cats-infographic/master/cats.svg)で、Functor の下に`Distributive` というものがある。`Traverse` の**双対**で、簡略化した定義は以下のようなものになる。

```scala
trait Distributive[F[_]] extends Functor[F] {
  def distribute[G[_]: Functor, A, B](ga: G[A])(f: A => F[B]): F[G[B]]
  def cosequence[G[_]: Functor, A](ga: G[F[A]]): F[G[A]] = ...
  def compose[G[_]](implicit G0: Distributive[G]): Distributive[λ[α => F[G[α]]]] = ...
}
```
これについて少し調べて素振りコードを書いたので、紹介したい。

※ ソースは[ここ](https://gist.github.com/yasuabe/a4634be0d1ecfdf63e5558097eca4657)に置いた。Cats は 2.0.0-M1 を使った。

## distribute関数 と cosequence関数
Cats では、`Function0`、`Function1`、`Nested`、`Kleisli`、`Tuple2K`について、`Distributive` インスタンスが提供されている。

それぞれについて `distribute` と `cosequence` を使った簡単なサンプルコードを書いてみる。`cats.syntax.distributive` で提供されている distributive 構文も、適宜使用する。

※ [Haskell の Distributive](https://www.stackage.org/haddock/lts-9.11/distributive-0.5.3/Data-Distributive.html) と関数名が違うが、最後の方に補足した。

### Function0
`Distributive`インスタンスが提供されているもののうち一番シンプルなもの。

```scala
// F = () => ?
val d0 = Distributive[() => ?]

// G = List, A = Char, B = String
// G[A] = List[Char], F[B] = () => String, F[G[B]] = () => List[String]
val afb0: Char => () => String = c => () => s"<$c>"
val ga0 = List('a', 'b')

d0.distribute(ga0)(afb0).apply // List(<a>, <b>)
ga0.distribute(afb0).apply     // List(<a>, <b>)

// G = List, A = Char
// G[F[A]] = List[() => Char], F[G[A]] = () => List[Char]
val gfa0 = List.fill(3)(() => '7')

d0.cosequence(gfa0).apply            // List(7, 7, 7)
gfa0.cosequence[() => ?, Char].apply // List(7, 7, 7)

```

### Function1
パラメータを一つ受け取る関数の型`Function1`も`Distributive`になる。ここでは`Function1[Int, ?]`を使った。

```scala
// F = Int => ?
val d1 = Distributive[Int => ?]

// G = Option, A = Char, B = String
// G[A] = Option[Char], F[B] = Int => String, F[G[B]] = Int => Option[String]
val afb1: Char => Int => String = c => n => c.toString * n
val ga1 = Option('a')

d1.distribute(ga1)(afb1).apply(3) // Some(aaa)
ga1.distribute(afb1).apply(3)     // Some(aaa)

// G = Option, A = String
// G[F[A]] = List[() => Char], F[G[A]] = () => List[Char]
val gfa1: Option[Int => String] = Option(n => "a" * n)

d1.cosequence[Option, String](gfa1).apply(3) // Some(aaa)
d1.cosequence[Option, String](None).apply(3) // None
gfa1.cosequence[Int => ?, String].apply(4)   // Some(aaaa)
```

### Nested
あまり馴染みのないデータタイプだけど、`Option[List[T]]`のような型を操作するときに、この`Nested`を使えば、ListT のようなモナドトランスフォーマーを敢えて作らなくても、大抵の場合こと足りるという（[参考](https://github.com/typelevel/cats/blob/master/docs/src/main/tut/faq.md#listt)）。

簡略化した定義は以下のようなもの。

```scala
final case class Nested[F[_], G[_], A](value: F[G[A]]) {
  def mapK[H[_]](f: F ~> H): Nested[H, G, A] = Nested(f(value))
}
```
これも以下のように`Distributive`として使うことができる。

```scala
// F = Nested[() => ?, Int => ?, A]
type FN[A] = Nested[() => ?, Int => ?, A]
val dn = Distributive[FN]

// G = Option, A = Char, B = String
// G[A] = Option[Char], F[B] = Int => String, F[G[B]] = Int => Option[String]
val afbn: Char => FN[String] = c => Nested(() => c.toString * _)
val gan = Option('a')

dn.distribute(gan)(afbn).value()(5) // Some(aaaaa)
gan.distribute(afbn).value()(3)     // Some(aaa)

dn.distribute(gan)(afbn)
  .map(_.map(s => s"<$s>")) // <-- (a)
  .value()(3)               // Some(<aaa>)

// G = List, A = String
// G[F[A]] = List[FN[String]], F[G[A]] = FN[List[String]]
val gfan: List[FN[String]] = List(Nested(() => "n" * _), Nested(() => "m" * _))
val nested = dn.cosequence[List, String](gfan)

nested.value()(3)                      // List(nnn, mmm)
nested.map(os => s"<$os>").value()(2)  // <List(nn, mm)>
gfan.cosequence[FN, String].value()(2) // List(nn, mm)

val func0ToId: Function0 ~> Id = new (Function0 ~> Id) {
  override def apply[A](fa: () => A) = fa()
}
gan.distribute(afbn).mapK(func0ToId).value(3) // Some(aaa)
```

`Nested`の動きをみるコードも若干書いてみた。(a)行のとおり、一個の`map`関数で、`Nested`内の2層の Functor の中の値を操作できる。また最後の行では、`mapK`に`Function0`から`Id`への自然変換を与えて、`value.apply().apply(n)`の中間の`apply()`を外している。


### Kleisli

おなじみの`Kleisli`も`Distributive`インスタンスが提供されているが、ただし`Kleisli[F[_], A, B]`の`F`も`Distributive`である必要がある。ここでは`Function0`を用いた。

```scala
// F = Kleisli[() => ?, Int, A]
type FK[A] = Kleisli[() => ?, Int, A]
val dk = Distributive[FK]

// G = Option, A = Char, B = String
// G[A] = Option[Char], F[B] = Int => String, F[G[B]] = Int => Option[String]
val afbk: Char => FK[String] = c => Kleisli(n => () => c.toString * n)
val gak = Option('a')
dk.distribute(gak)(afbk).run(7)() // Some(aaaaaaa)
gak.distribute(afbk).run(7)()     // Some(aaaaaaa)

// G = Option, A = String
// G[F[A]] = Option[FK[String]], F[G[A]] = FK[Option[String]]
val gfak: Option[FK[String]] = Option(Kleisli(n => () => "k" * n))
dk.cosequence[Option, String](gfak).run(8)() // Some(kkkkkkkk)
dk.cosequence[Option, String](None).run(8)() // None

gfak.cosequence[FK, String].run(6)() // Some(kkkkkk)
```

### Tuple2K
`Tuple2K` については[別記事](https://qiita.com/yasuabe2613/items/8e8940b85634bf916610#tuple2k)に書いたが、簡略化した定義は以下のようなもので、これも `Distributive` のインスタンスが提供されている。ただし`F`も`G`も `Distributive` である必要がある。

```scala
final case class Tuple2K[F[_], G[_], A](first: F[A], second: G[A]) {
  def mapK[H[_]](f: G ~> H): Tuple2K[F, H, A] = Tuple2K(first, f(second))
}
```
product になる一対の`Distributive`ファンクタは、`Int => ?`と`Boolean => ?`を使って試してみた。

```scala
// F = Tuple2K[Int => ?, Boolean => ?, A]
type FT[A] = Tuple2K[Int => ?, Boolean => ?, A]
val dt = Distributive[FT]

// G = Option, A = Char, B = String
// G[A] = Option[Char], F[B] = Int => String, F[G[B]] = Int => Option[String]
val afbt: Char => FT[String] = c => Tuple2K(c.toString * _, b => s"<$c, $b>")
val gat = Option('a')

dt.distribute(gat)(afbt).first(2) // Some(aa)
gat.distribute(afbt).second(true) // Some(<a, true>)

// G = Option, A = String
// G[F[A]] = Option[FK[String]], F[G[A]] = FK[Option[String]]
val gfat: Option[FT[String]] = Option(Tuple2K(n => s"<n>", b => s"<$b>"))

dt.cosequence[Option, String](None).first(2) // None
gfat.cosequence[FT, String].second(false)    // Some(<false>)
```

## compose関数
`Distributive`には`compose`が提供されていて、以下のように合成できる。

```scala
type TC[A] = Int => Double => A
val composed: Distributive[TC] = Distributive[Int => ?].compose[Double => ?]
def f(o: Option[TC[String]]) = composed.cosequence[Option, String](o).apply(3)(0.14)

f(Option(n => d => s"π ≒ ${n + d}")) // Some(π ≒ 3.14)
f(None)                              // None
```

`Distributive[Int => ?]`と`Distributive[Double => ?]`から合成した`Distributive[Int => Double => ?]`の`cosequence`に
`Option[Int => Double => String]`を与えると、型`Int => Double => Option[String]`の結果が得られる。

## Traverse の双対

冒頭で書いた通り、`Distributive`は`Traverse`の双対で、`distribute`が`traverse`に、`cosequence`が`sequence`にそれぞれ対応する。

コードで表現すると以下のようになる。

```scala
val h: Double => Int => String = d => n => s"${n+d}"
val o = Option(0.14)

val s1 = Distributive[Int => ?].distribute[Option,   Double, String](o)(h)
val t1 = Traverse    [Option]  .traverse  [Int => ?, Double, String](o)(h)

assert(s1(3) == t1(3)) // 共に Some(3.14)

val of: Option[Int => String] = Option(n => s"n = $n")

val s2 = Distributive[Int => ?].cosequence[Option,   String](of)
val t2 = Traverse    [Option]  .sequence  [Int => ?, String](of)

assert(s2(100) == t2(100)) // 共に Some(n = 100)
```

### 補足: Haskell と Scalaz との対応表
`F` を `Distributive`、`G` を `Functor` とすると、Haskell、Cats、Scalaz で以下のように対応する。

| 入力型           | 結果型   | Haskell     |  Cats    | Scalaz    | メモ |
| ------          | ------  | ------      | :-----: | ------     | ------ |
| G[A], A→F[B]    | F[G[B]] | collect     |distributive|distributive||
| G[F[A]]         | F[G[A]] | distributive|cosequence|cosequence||
| G[A]→B, G[F[A]] | F[B]    | cotraverse  |  ---  | cotraverse | traverse の矢印を逆にしたもの|