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

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

はじめに

Cats の 型クラス階層で、Functor の下にDistributive というものがある。Traverse の双対で、簡略化した定義は以下のようなものになる。

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[α]]]] = ...
}

これについて少し調べて素振りコードを書いたので、紹介したい。

※ ソースはここに置いた。Cats は 2.0.0-M1 を使った。

distribute関数 と cosequence関数

Cats では、Function0、Function1、Nested、Kleisli、Tuple2Kについて、Distributive インスタンスが提供されている。

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

※ Haskell の Distributive と関数名が違うが、最後の方に補足した。

Function0

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

// 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, ?]を使った。

// 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 のようなモナドトランスフォーマーを敢えて作らなくても、大抵の場合こと足りるという（参考）。

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

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として使うことができる。

// 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を用いた。

// 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 については別記事に書いたが、簡略化した定義は以下のようなもので、これも Distributive のインスタンスが提供されている。ただしFもGも Distributive である必要がある。

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 => ?を使って試してみた。

// 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が提供されていて、以下のように合成できる。

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にそれぞれ対応する。

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

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 の矢印を逆にしたもの