5
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@yasuabe2613

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

5
Last updated at Posted at 2019-10-26

とても簡単でわかりやすいデータ型 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 標準のデータ型でも List や Option などの map として提供しているが、この共通性を Cats では Functor という型クラスに抽象化して、統一的な操作を提供している。この Functor として正式に認められるためには、Cats が要請するルールセットを List や Option と同様に満たさなければいけないが、後にみるように 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 DisciplineSuite:
  given 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 => B か B => 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 コーディングでも頻繁に使う map が Functor に関連していて、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以下、InvariantSemigroupal、InvariantMonoidal、ContravariantSemigroupal、ContravariantMonoidalを見てみる。

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

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

trait PairInvariantSemigroupal
  extends InvariantSemigroupal[Pair] with PairSemigroupal with PairInvariant

InvariantMonoidal

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

trait PairInvariantMonoidal extends InvariantMonoidal[Pair] with PairInvariantSemigroupal:
  def unit: (Unit, Unit) = ???
実装例
def unit: (Unit, Unit) = ((), ())
`Unit` の値がわからなければ、もしかすると悩んだかもしれない。

ContravariantSemigroupal, ContravariantMonoidal

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

Applivative 〜 Monad など

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

Apply

Functor と Semigroupal を合成して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 を知っていれば、Applicative の pure がないものと考えることもできる（Semigroup が empty のない 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

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

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

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

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

trait PairCommutativeApply extends CommutativeApply[Pair] with PairApply

Applicative

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

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

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

pure の実装は、例えば List やOption ならば、与えられた 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)
サイズ２固定のコレクションを `a` でフィルするようなイメージの直感的な実装で、Discipline テストがちゃんと通る。

CommutativeApplicative

CommutativeApply と Applicative を合成すると 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 の場合、以下を実装すればよい。どう書けるだろうか？(難度=４)

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 なら以下を実装すればよいが、どうなるだろうか？(難度=５)

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

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

trait PairCommutativeFlatMap extends CommutativeFlatMap[Pair] with PairFlatMap with PairCommutativeApply

Monad

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

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

CommutativeMonad

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

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

Foldable〜Traverse まわり

Cats 型クラス階層の頂点の一つに UnorderedFoldable がある。階層の下の方には、わりとよく使われる Foldable や Traverse が含まれるが、ここでは Pair[A]=(A, A) をサイズ２固定のコレクション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 とするには以下を実装すればよいが、どうかけるだろうか？(難度=３)

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

UnorderedFoldable に foldLeft と foldRight を付け加えると 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

Foldable の non empty 版が Reducible で、下記シグネーチャの reduceLeftTo、reduceRightTo が追加される。

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 では、少なくとも１つの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)))
`reduceRightTo` の `Eval.later` は`Eval.now` でも問題ない（多分。少なくとも Discipline 的にはグリーン）。

Traverse

Foldable、UnorderedTraverse、Functor を継承して、さらにメソッド 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] が得られるが、どう書けるだろうか？（難度=２）

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になる。nonEmptyTraverse は traverse と似ているが、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 からの継承ラインのうち、Apply、Traverse 以外のものについて。

CoflatMap

すでに見た FlatMapは A => 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]] が得られるようなメソッド distributiveを Functorに追加すると、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] Pair[A] → G[Pair[B]] Applicative
Distributive[Pair] A → Pair[B] G[A] → Pair[G[B], G[B] Functor

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

trait PairDistributive extends Distributive[Pair] with PairFunctor:
  def distribute[G[_], A, B](ga: G[A])(f: A => (B, B))(using Functor[G]): (G[B], G[B]) = ???
実装例
def distribute[G[_], A, B](ga: G[A])(f: A => (B, B))(using Functor[G]): (G[B], G[B]) =
  val gpb: G[(B, B)] = ga map f
  (gpb.map(_._1), gpb.map(_._2))
`G` が Functor であることを利用して、`ga`、`f` から `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個だけとるしかない。どのように書けるだろうか。(難度=２)

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 ユーザ：「Applicative と FlatMap を継承した Monad トレイトの実装で、Discipline テストの実行結果がグリーンになるものですが、なにか問題でも？」
  • サンプルコードを Scala 3 に変更

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

  2. もとの画像はここ ↩

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

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

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

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

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

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

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

5
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
5
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?