Help us understand the problem. What is going on with this article?

シンプルな型 Pair[A]=(A, A) でいろいろな型クラスを実装してみる

とても簡単でわかりやすいデータ型 Pair[A]=(A, A) (同じ型の値のペア)について、Functor, Applicative, Monad, Traverse などを実装して型クラスを理解する Cats 入門者向け記事。

はじめに

たとえば (10, 20) というデータに、「2倍する」という関数を適用すると、直感的には (20, 40) になると考えるのが自然ではないだろうか。たぶん高校数学などでも「ベクトルのスカラー倍」のような形でなじみがある計算ではないかと思う。

同様に("abc", "de")に「文字列の長さ」という関数を適用すると(3, 2) が得られるのも、なんとなく自然な類推ではないだろうかと思う。

考え方としては、ペアの両方の値に同じ関数を単純に適用しているだけなのだけど、(1)ペアになっている値は同じ型であり、(2)関数を適用したあともペアであることは保たれるという暗黙の前提に注意して、ちょっと抽象的に書いてみると以下のようになる。

f: A → B と Pair[A] から、Pair[B] を得た。 あるいは f: A→B から、Pair[A] → Pair[B] を得た。

これと同じ形の操作を、Scala 標準のデータ型でも ListOption などの map として提供しているが、この共通性を Cats では Functor という型クラスに抽象化して、統一的な操作を提供している。この Functor として正式に認められるためには、Cats が要請するルールセットを ListOption と同様に満たさなければいけないが、後にみるように Pair もちゃんとそれを充足する。

実は Pair は、Functor 以外にもいろいろな型クラスインスタンスが書ける。実際に書いてみると、成立する型クラスが思っていたよりも多くて、面白かったので紹介したい。

進め方

対象

Cats にはいくつかの型クラス群があるが、F[_] を型パラメータにとる以下の階層に含まれるものについて、Pair のインスタンスを作ってみた1。先に結論を書いてしまうと、緑のティックが付いているものが型クラスのインスタンスが定義できたもので、赤のクロスが付いているものができなかったものになる2

cats-typeclasses.png

意外と多いと思ったのではないだろうか(自分はそうだった)。この後、一つずつ確認してみる。

趣向

  • もともと Cats の型クラス階層は、「非力だが制約の少ない」型クラスを頂点として、薄皮をかさねるように「強力だが制約の多い」型クラスに至るように構成されているが、この記事でもそれをなぞって少しずつ進める。
  • 実装コードを ??? で伏せたクイズのような形にして、実装例は畳み込んでおいた。一瞬考えてから実装例を見てみると、Pair でどう実装するかだけではなく、それぞれの型クラス固有の要請についての理解につながるのではないかと思う。3
  • 一番かんたんで自明な Functor を 1、個人的に一番難しかった FlatMap#tailRecM を 5として、難度を表示しておいた。といっても、たかが二つの値のペアなので、難度=5 でもある程度考えれば分かるレベルだと思う。
  • 型クラスごとに Cats が提供するルールセットを使って、それぞれの法則を Discipline テストで検証した。ただし、ルールセットを個別に解説するのはこの記事ではやめておいた4

実装

以下の型 Pair から、いろいろな型クラスを実装してみる。

type Pair[A] = (A, A)

たとえば Functor なら以下のようなものになる。

trait PairFunctor extends Functor[Pair] { ... }

さらに、以下のように Discipline を使ったテストも書く。ただしこの記事には載せずリンクだけ貼っておく。

class PairFunctorTests extends AnyFunSuite with Discipline {
  implicit val p: Functor[Pair] = new PairFunctor {}
  checkAll("Pair.FunctorLaws", FunctorTests[Pair].functor[Int, Int, String])
}
  • Scala は 2.13.1、Cats は 2.0.0 を使った。
  • 型クラスのインスタンス群のソースはここ
  • 型クラスのインスタンス群のテストコードはここ

Functor まわり

ここでは Invariant, Functor, Contravariant インスタンスを作ってみる。

Invariant

知名度があまり高くないかもしれないが、このInvariant は Cats の型クラス群の頂点の一つで、階層的に Functor の一つ上に当たる。したがって、モナド、アプリカティブ、Traverse など Functor の下層にある型クラス群は、自動的に Invariant の性質も持っていることになる。

と言ってもむずかしいものではなく、A => BB => A か、どちらかの関数があれば F[A] => F[B] が得られるような性質を表現できればよくて、Scala コードとしては下記のシグネーチャの imap を書くことになる。

trait Invariant[F[_]] {
  def imap[A, B](fa: F[A])(f: A => B)(g: B => A): F[B]
  ...

Pair なら以下を実装することになるが、どう書けるだろうか?(難度=2)

trait PairInvariant extends Invariant[Pair] {
  def imap[A, B](fa: (A, A))(f: A => B)(g: B => A): (B, B) = ???
}

実装例
def imap[A, B](fa: (A, A))(f: A => B)(g: B => A): (B, B) = fa match {
  case (a1, a2) => (f(a1), f(a2))
}


簡単だけど、もしかすると g をどうやって使えばよいか悩んだかもしれない。単に捨てるだけでよくて、これで Discipline テストがちゃんと通る。

Functor

Invariant を継承して、以下のシグネーチャの map を追加すると Functor ができあがる。

trait Functor[F[_]] extends Invariant[F] {
  def map[A, B](fa: F[A])(f: A => B): F[B]
  ...

Option や List などの操作で、普通の Scala コーディングでも頻繁に使う mapFunctor に関連していて、Cats の型クラスの中でも特に馴染み深いものだと思う。

Pair なら以下の map を実装すればよい。どう書けるだろうか?(難度=1)

trait PairFunctor extends Functor[Pair] with PairInvariant {
  def map[A, B](fa: (A, A))(f: A => B): (B, B) = ???
}

実装例
override def map[A, B](fa: (A, A))(f: A => B): (B, B) = fa match {
  case (a1, a2) => (f(a1), f(a2))
}


冒頭に書いたスカラー倍の問題そのもので、これは簡単だと思う。結局、Invariant と同じになる。

Contravariant

Invariant に下記のような contramap を追加すると、Contravariant になる。

trait Contravariant[F[_]] extends Invariant[F] {
  def contramap[A, B](fa: F[A])(f: B => A): F[B]
  ...

ただし B => A から (A, A) => (B, B) を得るのは無理なので、どうやらContravariant[Pair] は実装できない5

Semigroupal まわり

F[_] をあつかう型クラスの頂点の一つに、Semigroupal がある。ここでは Semigroupal以下、InvariantSemigroupalInvariantMonoidalContravariantSemigroupalContravariantMonoidalを見てみる。

Semigroupal

Semigroupal は、F[_] の中で型の積を作るような操作を提供する。以下のシグネーチャの product メソッドを実装する。

trait Semigroupal[F[_]] {
  def product[A, B](fa: F[A], fb: F[B]): F[(A, B)]
  ...

Pair の場合は以下を実装すれば良いが、どうなるだろうか。(難度=2)。

trait PairSemigroupal extends Semigroupal[Pair] {
  def product[A, B](fa: (A, A), fb: (B, B)): ((A, B), (A, B)) = ???
}

実装例
def product[A, B](fa: (A, A), fb: (B, B)): ((A, B), (A, B)) = (fa, fb) match {
  case ((a1, a2), (b1, b2)) => ((a1, b1), (a2, b2))
}


素朴に _1同士、_2同士をペアにすれば良い。行列の転置のような操作になる。

InvariantSemigroupal

SemigroupalInvariant を合わせるとInvariantSemigroupal となるが、ここまでに作った PairSemigroupalPairInvariant を合成するだけでよくて、Discipline が要求する ルールセットも自然と満たされる。

trait PairInvariantSemigroupal
  extends InvariantSemigroupal[Pair] with PairSemigroupal with PairInvariant

InvariantMonoidal

InvariantSemigroupalunit: F[Unit] を追加した型クラスが InvariantMonoidal となる。Pair の場合、型(Unit, Unit)の値を作ればよいが、どう書けるだろうか?(難度=2)

trait PairInvariantMonoidal extends InvariantMonoidal[Pair] with PairInvariantSemigroupal {
  def unit: (Unit, Unit) = ???
}

実装例
def unit: (Unit, Unit) = ((), ())


Unit の値がわからなければ、もしかすると悩んだかもしれない。

ContravariantSemigroupal, ContravariantMonoidal

ContravariantSemigroupalContravariant を継承するが、上で見たように Contravariant[Pair] は定義できない。このため ContravariantSemigroupal[Pair] も定義できず、またContravariantSemigroupal[Pair] を継承するContravariantMonoidal[Pair] も定義できないということになる。

Applivative 〜 Monad など

ここまでに見た、FunctorSemigroupal から新たな型クラス Apply が定義でき、その下の型クラス階層に ApplicativeMonad といった有名な型クラスが構成される。ここでも一歩ずつ順に見てみる。

Apply

FunctorSemigroupal を合成して6、さらに F[A => B] から F[A] => F[B] が得られる性質を付け加えると Apply になる。簡潔にした実装は以下のようなもの。

trait Apply[F[_]] extends Functor[F] with InvariantSemigroupal[F] {
  def ap[A, B](ff: F[A => B])(fa: F[A]): F[B]
  ...

後述の Applicative を知っていれば、Applicativepure がないものと考えることもできる(Semigroupempty のない Monoid と理解できるのと同様に)。

Pairの場合、以下を実装すればよい。どう書けばよいだろか(難度=3)?

trait PairApply extends Apply[Pair] with PairFunctor {
  def ap[A, B](ff: (A => B, A => B))(fa: (A, A)): (B, B) = ???
}

実装例
def ap[A, B](ff: (A => B, A => B))(fa: (A, A)): (B, B) = (ff, fa) match {
  case ((f1, f2), (a1, a2)) => (f1(a1), f2(a2))
}


関数のペアと型Aのペアで、_1同士と _2同士を自然に適用する。ちなみに (f2(a1), f1(a2)) と書くと、コンパイルすることはできるが、Discipline テストで失敗する。

CommutativeApply

上述の通り ApplySemigroupalを継承しているが、Semigroupal#productApply#apを組み合わせると、下記のようなシグネーチャをもつ map2 が得られる。

def map2[A, B, Z](fa: F[A], fb: F[B])(f: (A, B) => Z): F[Z]

この map2 が可換となるような ApplyCommutativeApply となる。

ただし Pair の場合は、自然と可換性が成立して Discipline テストも成功する。

trait PairCommutativeApply extends CommutativeApply[Pair] with PairApply

Applicative

AF[_] の文脈にのせる操作 pureApply に追加したものが、Applicative になる。だから、もし「Applicative とは何か?」と聞かれるようなことがあったら、Scala+Cats 的には「Apply に pure を付け加えたものですが、なにか問題でも?」と、簡潔に答えることができる。

細部を省略したシグネーチャは以下のようなものになる(※ pure(()) により unitが提供できるので、実際の実装ではInvariantMonoidal も継承する形になっている)。

trait Applicative[F[_]] extends Apply[F] {
  def pure[A](x: A): F[A]
  ...

pure の実装は、例えば ListOption ならば、与えられた a:A について、それぞれ List(a)Some(a) だが、Pair の場合はどうだろうか?(難度=3)

trait PairApplicative extends Applicative[Pair] with PairApply {
  def pure[A](a: A): (A, A) = ???
}

実装例
def pure[A](a: A): (A, A) = (a, a)


サイズ2固定のコレクションを a でフィルするようなイメージの直感的な実装で、Discipline テストがちゃんと通る。

CommutativeApplicative

CommutativeApplyApplicative を合成すると CommutativeApplicative になる。Pair の場合、単に多重継承するだけで、それぞれの法則が満たされるようになる。特に追加のメソッドを実装する必要もない。

trait PairCommutativeApply extends CommutativeApply[Pair] with PairApply

FlatMap

だんだんモナドに近づいてきた。

Cats では、Applyに下記シグネーチャの flatMap, tailRecM を付け加えると FlatMapとなる7

trait FlatMap[F[_]] extends Apply[F] {
  def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]
  def tailRecM[A, B](a: A)(f: A => F[Either[A, B]]): F[B]
}

別々に見てみる。まず flatMapから。

おさらいすると、F[A] => F[B]を得る前提として A => B が使えるのが Functor、さらにF[A => B]も使えるのが Apply(Applicative)だった。ここでさらに A => F[B] も使えるのが FlatMap(そして後述のMonad) になる。

Pair の場合、以下を実装すればよい。どう書けるだろうか?(難度=4)

trait PairFlatMap extends FlatMap[Pair] with PairApply {
  def flatMap[A, B](fa: (A, A))(f: A => (B, B)): (B, B) = ???
...

実装例
def flatMap[A, B](fa: (A, A))(f: A => (B, B)): (B, B) = map(fa)(f) match {
  case ((b1, _), (_, b2)) => (b1, b2)
}


fa:(A,A) の二つの A値にそれぞれ f を関数適用すると(map)、得られる型は ((B,B),(B,B)) となるから、これを(B, B)にする必要がある。言い換えると Pair[Pair[B]] を平らにして Pair[B] にしている訳で、これが FlatMap の "flat" たるゆえんでもあるが、ここでは両端の要素だけを残すことで実現している。値を捨てちゃって良いのだろうかと心配になるが、これでちゃんと Discipline テストも通る。

次に tailRecM を見てみる。これは代数や圏論からの要請というより、スタックセーフを実現するための実装上の仕組みで、シグネーチャを再掲すると下のようなものだった。

def tailRecM[A, B](a: A)(f: A => F[Either[A, B]]): F[B]

関数f の使い方としては、f(a) の結果が Right 値なら結果に含めて、Left値なら再び f を適用して計算を継続するようにすればいい。ただし、うまく末尾再帰を構成してスタックオーバーフローを防ぐ必要がある。

Pair なら以下を実装すればよいが、どうなるだろうか?(難度=5)

trait PairFlatMap extends FlatMap[Pair] with PairApply {
...
  def tailRecM[A, B](a: A)(f: A => (Either[A, B], Either[A, B])): (B, B) = ???

実装例

先に失敗例を示すと以下のようになる。
def tailRecM[A, B](a: A)(f: A => (Either[A, B], Either[A, B])): (B, B) = f(a) match {
  case (Right(b1), Right(b2)) => (b1,                 b2)
  case (Left(a1),  Right(b2)) => (tailRecM(a1)(f)._1, b2)
  case (Right(b1), Left(a2))  => (b1,                 tailRecM(a2)(f)._2)
  case (Left(a1),  Left(a2))  => (tailRecM(a1)(f)._1, tailRecM(a2)(f)._2)
}

この実装だと、計算結果の値自体には問題がないが、末尾再帰にならないのでスタックセーフティが得られない。実際にスタックオーバーフローが発生するのは、この FlatMap のルールセットではなくて次のモナドのルールセットだけど、tailRecM の実装なのだからちゃんと tailrec にしておきたい。

末尾再帰を構成したスタックセーフな実装例は、以下のようなものになる。

def tailRecM[A, B](a: A)(f: A => (Either[A, B], Either[A, B])): (B, B) = {
  @scala.annotation.tailrec
  def first(a: A): B = f(a) match {
    case (Right(b), _) => b
    case (Left(a),  _) => first(a)
  }
  @scala.annotation.tailrec
  def second(a: A): B = f(a) match {
    case (_, Right(b)) => b
    case (_, Left(a))  => second(a)
  }
  (first(a), second(a))
}


CommutativeFlatMap

ApplyApplicative に、それぞれ対応する CommutativeApplyCommutativeApplicative があったように、FlatMap にも CommutativeFlatMap がある。Pair の場合、CommutativeFlatMap[Pair] も、FlatMapCommutativeApplicative を継承するだけで、自然とDiscipline のルールセットを満たすようになる。

trait PairCommutativeFlatMap extends CommutativeFlatMap[Pair] with PairFlatMap with PairCommutativeApply

Monad

ApplicativeFlatMap を合成すると、それだけで Monad になってしまう。具体的には、Applicative#pure と、FlatMap#flatMap(と tailRecM)があれば Monad になって、Discipline が提供する「モナド則」も自然と満たされる。

数学的にモナドを理解しようとすると、よく知られている「モナドとは自己函(ry」にしても、随伴とかを使った構成にしても、それなりに段階を踏んで理解を積み上げていく必要があるけど、Scala+Cats での Monad は、ここまでで見たように単に ApplicativeFlatMap を多重継承したトレイトにすぎず、予めお膳立てされた Discipline ルールセットについてテスト実行がグリーンになりさえすれば、プログラミング技術としては十分だったりする。

CommutativeMonad

ApplyApplicativeFlatMap に、それぞれ対応する Commutative版 があったように、Monad にも CommutativeMonad がある。Pair の場合も、下記のような継承構成で自然と Discipline のルールセットを満たす可換性が得られる。

trait PairCommutativeMonad extends CommutativeMonad[Pair]
  with PairMonad
  with PairCommutativeFlatMap
  with PairCommutativeApplicative

Foldable〜Traverse まわり

Cats 型クラス階層の頂点の一つに UnorderedFoldable がある。階層の下の方には、わりとよく使われる FoldableTraverse が含まれるが、ここでは Pair[A]=(A, A) をサイズ2固定のコレクション8と捉えてインスタンスが作れるか試してみる。

UnorderedFoldable

UnorderedFoldable では、以下のようなシグネーチャのメソッドを実装する。

def unorderedFoldMap[A, B: CommutativeMonoid](fa: F[A])(f: A => B): B

B が可換モノイドであることに注意して、Pair の場合ならば以下を実装すればよい。どのように書けるだろうか?(難度=3)

trait PairUnorderedFoldable extends UnorderedFoldable[Pair] {
  def unorderedFoldMap[A, B: CommutativeMonoid](fa: (A, A))(f: A => B): B = ???
}

実装例
def unorderedFoldMap[A, B: CommutativeMonoid](fa: (A, A))(f: A => B): B = fa match {
  case (a1, a2) => f(a1) |+| f(a2)
}


CommutativeMonoid の意味が、単位元と可換な二項演算をもつことだとわかれば簡単だと思う。空がありうるようなF[_]、たとえば List や Option なら単位元も利用することになるが、Pair の場合、空はありえないので二項演算のみを利用する。

UnorderedTraverse

UnorderedFoldable に、以下のようなシグネーチャの unorderedTraverse を追加すると、UnorderedTraverse になる。

trait UnorderedTraverse[F[_]] extends UnorderedFoldable[F] {
  def unorderedTraverse[G[_]: CommutativeApplicative, A, B](sa: F[A])(f: A => G[B]): G[F[B]]
  ...

後述の Traverse#traverse と似ているが、G の型制約が CommutativeApplicative となっていて、Traverse が要請するApplicativeより厳しいために、その分逆に型クラスとしては自由度が高く、型クラス階層で上の方に位置している。

Pair をUnorderedTraverse とするには以下を実装すればよいが、どうかけるだろうか?(難度=3)

trait PairUnorderedTraverse extends UnorderedTraverse[Pair] with PairUnorderedFoldable {
  def unorderedTraverse[G[_]: CommutativeApplicative, A, B](sa: (A, A))(f: A => G[B]): G[(B, B)] = ???
}

実装例
def unorderedTraverse[G[_]: CommutativeApplicative, A, B](sa: (A, A))(f: A => G[B]): G[(B, B)] =
  sa match {
    case (a1, a2) => f(a1) product f(a2)
  }
}


CommutativeApplicative を階層上の上にたどると Semigroupal に突き当たるので、そのメソッド product を使って G[(B, B)]を作れば良い。

Foldable

UnorderedFoldablefoldLeftfoldRight を付け加えると Foldable になる。

trait Foldable[F[_]] extends UnorderedFoldable[F] {
  def foldLeft[A, B](fa: F[A], b: B)(f: (B, A) => B): B
  def foldRight[A, B](fa: F[A], lb: Eval[B])(f: (A, Eval[B]) => Eval[B]): Eval[B]
  ...
}

まず foldLeft から。Pair ならば以下を実装すればよいが、どうなるだろうか?(難度=2)

trait PairFoldable extends Foldable[Pair] {
  def foldLeft[A, B](fa: (A, A), b: B)(f: (B, A) => B): B = ???
  ...
}

実装例
def foldLeft[A, B](fa: (A, A), b: B)(f: (B, A) => B): B = fa match {
  case (a1, a2) => f(f(b, a1), a2)
}


普通の Scala コードの List操作などから、簡単に類推できるのではないだろうか。

次に foldRight。こちらは Eval を使うので難度が高まる。遅延評価させるために、あえて導入している Eval なので、単に型合わせだけしてコンパイルを通しただけでは、Discipline テストで失敗する可能性がある。Pair の場合、以下を実装すればよいがどうなるか?(難度=4)

trait PairFoldable extends Foldable[Pair] {
  ...
  def foldRight[A, B](fa: (A, A), lb: Eval[B])(f: (A, Eval[B]) => Eval[B]): Eval[B] = ???
}

実装例
def foldRight[A, B](fa: (A, A), lb: Eval[B])(f: (A, Eval[B]) => Eval[B]): Eval[B] =
  fa match {
    case (a1, a2) => Eval.defer(f(a1, Eval.defer(f(a2, lb))))
  }


右から畳み込む操作自体は全然むずかしいものではないが、Eval.defer に気づかないとなかなか Discipline テストが通らないかもしれない。例えば f(a1, f(a2, lb)) のようにしてしまうと、lazy であることを要求するいくつかのルールが満たされなくなる。

Reducible

Foldablenon empty 版が Reducible で、下記シグネーチャの reduceLeftToreduceRightTo が追加される。

trait Reducible[F[_]] extends Foldable[F] { self =>
  def reduceLeftTo[A, B](fa: F[A])(f: A => B)(g: (B, A) => B): B
  def reduceRightTo[A, B](fa: F[A])(f: A => B)(g: (A, Eval[B]) => Eval[B]): Eval[B]
  ...

foldLeft/Right では初期値を明示的に与えていたが、reduceLeft/RightTo では、少なくとも1つのA型値があることを前提にしているので、初期値の代わりに f: A=>Bを与える。Pair の場合は以下を実装すればよいがどうなるか?(難度=3)

trait PairReducible extends Reducible[Pair] with PairFoldable {
  def reduceLeftTo[A, B](fa: (A, A))(f: A => B)(g: (B, A) => B): B = ???
  def reduceRightTo[A, B](fa: (A, A))(f: A => B)(g: (A, Eval[B]) => Eval[B]): Eval[B] = ???
}

実装例
def reduceLeftTo[A, B](fa: (A, A))(f: A => B)(g: (B, A) => B): B = fa match {
  case (a1, a2) => g(f(a1), a2)
}
def reduceRightTo[A, B](fa: (A, A))(f: A => B)(g: (A, Eval[B]) => Eval[B]): Eval[B] = fa match {
  case (a1, a2) => g(a1, Eval.later(f(a2)))
}


reduceRightToEval.laterEval.now でも問題ない(多分。少なくとも Discipline 的にはグリーン)。

Traverse

FoldableUnorderedTraverseFunctor を継承して、さらにメソッド traverse を付け加えると、おなじみの Traverse になる。traverse のシグネーチャは以下のようなものだった。

trait Traverse[F[_]] extends Functor[F] with Foldable[F] with UnorderedTraverse[F] {
  def traverse[G[_]: Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]]
  ...
}

Pair の場合、下の未実装部分を書き足せば Traverse[Pair] が得られるが、どう書けるだろうか?(難度=2)

trait PairTraverse extends Traverse[Pair] with PairFunctor with PairFoldable {
  def traverse[G[_]: Applicative, A, B](fa: (A, A))(f: A => G[B]): G[(B, B)] = ???
}

実装例
override def traverse[G[_]: Applicative, A, B](fa: (A, A))(f: A => G[B]): G[(B, B)] =
  fa match {
    case (a1, a2) => f(a1) product f(a2)
  }


unorderedTraverse と同じ実装で良いが、G の型制約が traverse の方がゆるいので、traverse の定義で unorderedTraverse を使うことはできない。逆に、unorderedTraverse の定義で traverse を使うことは可能。

NonEmptyTraverse

Traverse にメソッド nonEmptyTraverse を追加すると、型クラスNonEmptyTraverseになる。nonEmptyTraversetraverse と似ているが、F[_]NonEmpty であることがわかっているため、型パラメータ Gの制約が少し弱まり、Applicativeから Applyになる。

Pair を NonEmptyTraverse にするには下記を実装すればよいが、どう書けるだろうか?(難度=2)

trait PairNonEmptyTraverse extends NonEmptyTraverse[Pair] with PairReducible {
  def nonEmptyTraverse[G[_]: Apply, A, B](fa: (A, A))(f: A => G[B]): G[(B, B)] = ???
}

実装例
def nonEmptyTraverse[G[_]: Apply, A, B](fa: (A, A))(f: A => G[B]): G[(B, B)] = fa match {
  case (a1, a2) => f(a1) product f(a2)
}


もともと traverse でも Applicative#pure は使っていなかったので、結局まったく同じコードで済む。

CoflatMap、Distributive など

Functor からの継承ラインのうち、ApplyTraverse 以外のものについて。

CoflatMap

すでに見た FlatMapA => F[B]から F[A] => F[B]を得るものだったが、これと逆の F[A] => Bから F[A] => F[B] を得る性質を Functorに追加すると、CoflatMapとなる。

trait CoflatMap[F[_]] extends Functor[F] {
  def coflatMap[A, B](fa: F[A])(f: F[A] => B): F[B]
  ...

Pair の場合、以下の未実装部分を書けばよいが、どうなるだろうか?(難度=3)

trait PairCoflatMap extends CoflatMap[Pair] with PairFunctor {
  def coflatMap[A, B](fa: (A, A))(f: ((A, A)) => B): (B, B) = ???
}

実装例
def coflatMap[A, B](fa: (A, A))(f: ((A, A)) => B): (B, B) = {
  val x = f(fa)
  (x, x)
}


A のペアからfによって得られる B は1個だけだが、Applicative#pureと同じような考え方でタプルを埋めると、それで Discipline のルールセットも満たされる。

Comonad, Bimonad

Monad の双対である Comonad を得るには、上で書いた flatMap の双対の coflatMapと、あとは pure: A => (A, A) の双対の extract: (A, A) => Aが書ければよい。

単純に考えると、_1_2を返せば良さそうに思えるが、しかし実はこれだと Comonad のルールセットを満たせない(例えば、coflatMap と extract を組み合わせると、元の (A, A) に復元できるといったプロパティがある)。なので Comonad[Pair] は成立しない。従ってまた、Comonad を継承とする Bimonad も成立しない。

Distributive

A => F[B] から G[A] => F[G[B]] が得られるようなメソッド distributiveFunctorに追加すると、Distributive になる。

trait Distributive[F[_]] extends Functor[F] {
  def distribute[G[_]: Functor, A, B](ga: G[A])(f: A => F[B]): F[G[B]]
  ...

Traverse の双対になっていて9、以下のような対応関係がある。

型クラス この射から この射を得る G の条件
Traverse[Pair] A => G[B] (A, A) => G[(B, B)] Applicative
Distributive[Pair] A => (B, B) G[A] => (G[B], G[B]) Functor

Scala コードとしては以下の未実装部分を補えばよいが、どうなるか?(難度=3)

trait PairDistributive extends Distributive[Pair] with PairFunctor {
  def distribute[G[_], A, B](ga: G[A])(f: A => (B, B))(implicit G: Functor[G]): (G[B], G[B]) = ???
}

実装例
def distribute[G[_], A, B](ga: G[A])(f: A => (B, B))(implicit G: Functor[G]): (G[B], G[B]) = {
  val gpb: G[(B, B)] = ga map f
  (gpb.map(_._1), gpb.map(_._2))
}


G が Functor であることを利用して、gaf から G[Pair[B]] を得てから、内箱と外箱を入れ替えて Pair[G[B]] とすればいい。

SemigroupK など

おさらいすると、Cats の K のつく型クラスは、任意の型パラメータで成立する操作、つまりF[A] なら A にかかわらずF[_]の性質のみで成立する操作を提供するものだった。例えば List[A] なら、型 A が何であろうとリストの連結という二項演算があり、空リストという単位元がある。これを Pair の場合でみてみる。

SemigroupK

SemigroupK は、二つのF[A] をあわせて一つのF[A] にするメソッド combineK を持つ。

trait SemigroupK[F[_]] {
  @simulacrum.op("<+>", alias = true)
  def combineK[A](x: F[A], y: F[A]): F[A]
  ...

SemigroupK なら二組の (A, A) をあわせて一組の (A, A) にするから、4つの A値を 2個にすることになる。A について前提を置かないのが、「Kのつくクラス」なので、A同士を合成することはできない。したがって半分すてて 2個だけとるしかない。どのように書けるだろうか。(難度=2)

trait PairSemigroupK extends SemigroupK[Pair] {
  def combineK[A](x: (A, A), y: (A, A)): (A, A) = ???
}

実装例
def combineK[A](x: (A, A), y: (A, A)): (A, A) = (x, y) match {
  case ((x1, _), (_, y2)) => (x1, y2)
}


2個の A値の取りかたは associatiive law が成立すればいい。実は上のとり方だけが正解ではなくて、x や y をそのまま返したりしても、Discipline テストは上手く行く。逆に失敗するパターンを探してみると、SemigroupK の結合律の理解の助けになるかもしれない。

MonoidK, Alternative

Monoid が単位元を提供するのと似たように MonoidK は「空」を提供する。これも型パラメータに依存しないものが求められ、たとえば List なら 空リスト、Option なら Noneでよいが、Pair の場合は単位元に相当するものはない。したがって MonoidK[Pair] は成立しないとわかる。

またさらに MonoidK に依存する(継承する)Alternative も、Pair では成立しないことになる。

おわりに

  • 質問者:「モナドとはなんですか?」
  • この記事を読んだ Cats ユーザ:「ApplicativeFlatMap を継承した Monad トレイトの実装で、Discipline テストの実行結果がグリーンになるものですが、なにか問題でも?」

  1. A を型パラメータにとる Eq系、Monoid系、F[_,_]を型パラメータにとる BiFunctorArrow 系、あるいは F[_] でも Cats Effect や Cats MTL に含まれるものもあるが、ここでは扱わない。 

  2. もとの画像はここ 

  3. 『Learn Better』という一般向けの学習理論の本によれば、ただ読むだけという行為は、どれだけマーカーを引こうが、あるいは何度読み返そうが、学習効果はぜんぜん薄いというのが、心理学でも脳科学でも無数のエビデンスに支持された結論らしい。そこで同書では本の中の要所要所に、小テストを入れて理解と記憶の定着を支援していたが、この記事でもそれにならって、「学習」を「活動」につなげるためにクイズ形式を取り入れてみた。 

  4. 【理由1】かなり数が多い、【理由2】あらかじめ法則を知悉していなくても、テストがコケたときに調べるくらいがコスパが良い、【理由3】自分も含め、ほとんどのプログラマは数学徒ほど証明や法則が好きではない(たぶん)。 

  5. Contravariant に馴染みがない人は、逆にどういうF[_]Contravariant になるのか考えてみると理解が深まるかもしれない。 

  6. 図では Semigroupal だけど、実装上は InvariantSemigroupal。 

  7. 個人的には、代数的性質から要請される flatMap と、実装都合の tailRecM が同じトレイトに含まれるのは、異なる関心事が混在してしまっている気がする。Scalaz ではたしかちゃんと分離されていた。 

  8. Shapeless の Sized で固定サイズのコレクションを表現することもできる。 

  9. 以前、調べてみた記事を書いた。 

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした