🥰

cats の Applicative・Monad・Parallel

2022/11/23に公開

https://blog.ojisan.io/monad-applicative

Either でいいざー(ただし対応する Monad を持たないような Applicative の実装が存在するならば)

或いは、Applicative と Parallel のお気持ち.

まず、以下のルールを覚えておこう.

ある F[_] について MonadApplicative が存在するとき、MonadApplicative の種々の実装は一致する必要がある.
(本当はもう少し細かいルールがあるが分かりやすさのため簡略化)

あるいは このブログの言葉を借りて

すべてのMonadは、ちゃんと定義すれば Functor かつ Applicative になります。

と言ってもいい.

一方であるF[_] について Monad が存在しないとき、Applicative はシーケンシャル(逐次的)にもパラレルにも実装できる. シーケンシャルとパラレルとはどういうことだろうか. それは以下の例を見てもらいたい.

以下の product の実装はどちらも有効である(わかりやすさのために Either モナドを使い、エラー型を String で書いている). 前者がシーケンシャル、後者がパラレルな実装である.
(なお本当の product のシグネチャは def product(fa:F[A],fb:F[B]) : F[(A,B)])

シーケンシャルな実装では fb が評価されるかどうかは fa が成功するかどうかに依存している. fa match case Left(e) の部分では fb の値について知り得ない.

ap_sequential.scala
type Error = String
type ErrorOr[T] = Either[Error,T]
def product(fa:ErrorOr[A],fb:ErrorOr[B]): ErrorOr[(A,B)] = fa match
  case Left(e) => Left(e)
  case Some(a) =>
    fb match
      case Some(b) => Some((a,b))
      case Left(e) => Left(e)

一方、パラレルな実装では fa と fb が評価されるかどうかはお互いに依存していない.

ap_parallel.scala
type Error = String
type ErrorOr[T] = Either[Error,T]
def product(fa:ErrorOr[A],fb:ErrorOr[B]): ErrorOr[(A,B)] = (fa,fb) match
  case (Right(a),Right(b)) => Some((a,b))
  case (Right(a),Left(e)) => Left(e)
  case (Left(e), Right(b)) => Left(e)
  case (Left(ea), Left(eb)) => Left(ea+eb)

F[_]Monad があるとき、Applicative の実装は Monad と一貫性を持たせるため、シーケンシャルになる(「ある F[_] について...種々の実装は一致する必要がある」を思い出そう)

for {
  a <- fa
  b <- fb
} yield (f(a,b))

f <*> fa <$> fb

が一致するイメージだ.(<*>ap のエイリアス)

cats の Either・Validated の product を調べてみよう.

type Error = String
type ErrorOr[T] = Either[Error,T]
(Left(value = "oops1"):ErrorOr[String]).product(Left(value="oops2"))
// => Left(value = "oops1")
type Invalid = String
type InvalidOr[T] = Validated[Invalid,T]
("oops1".invalid:InvalidOr[String]).product("oops2".invalid) 
// => Invalid(e = "oops1oops2")

実際、上の Eitherproductoops1oops2 ではなく oops1 を返している.
EitherValidatedMonad があるかくらいしか大きな違いがないことを思い出せば、 Monad があってもなくても Applicative があれば product を実装できるが、Monad がある場合は一貫性のために挙動が変わることが推測できる.

さて.
では、今ある F[_] について、Monad が存在するが、シーケンシャルな Applicative とパラレルな Applicative の両方があって(つまり、対応する Monad が存在するような Applicative と対応する Monad が存在しないような Applicative)、それらをうまく切り替えたいとしたらどうすればいいだろうか.

よくあるシチュエーションは、 Monad を持たない Validated ではなく Monad を持つEither を使い、なおかつエラーを蓄積したい場合である.

either_mapN.scala
type Error = String
type ErrorOr[T] = Either[Error,T]
val data : (ErrorOr[String],ErrorOr[Striing]) = (
  Left(value = "oops1"),
  Left(value = "oops2")
)
// def mapN[Z](f: (A0, A1) => Z)(implicit functor: cats.Functor[F], implicit semigroupal: cats.Semigroupal[F]): F[Z]
data.mapN((a,b) => a + b )
// => Left(value = "oops1")
// mapN は内部で Applicative を使っている.
// もしこれが Validated であれば、(Monad がないので) Applicative の
// 実装はパラレルな実装になっていていいはずであり(実際そうなっているので)mapN でエラーを蓄積するような実装が可能なはずである.
// しかしここでは Either モナドを使っているためシーケンシャルな実装になっている. 
// fa が失敗であればその後の処理が中断されるので fb が失敗したときの値
// `oops2` を知り得ないので Left にエラーを蓄積できない.

Either について対応する Monad を持たないような Applicative を実装することは可能である(あるいは、そのように Applicative を定義すればパラレルな Applicative として利用できる).
あとは対応する Monad を持つ Applicative ともたないものを差し替えるために Parallel が存在する. Parallel を要求する関数は対応する Monad が存在しないような Applicative のインスタンスを利用して計算を行う.

type Error = String
type ErrorOr[T] = Either[Error,T]
val data : (ErrorOr[String],ErrorOr[Striing]) = (
  Left(value = "oops1"),
  Left(value = "oops2")
)
// def mapN[Z](f: (A0, A1) => Z)(implicit functor: cats.Functor[F], implicit semigroupal: cats.Semigroupal[F]): F[Z]
data.mapN((a,b) => a + b )
// => Left(value = "oops1")
// mapN は内部で Applicative を使っている.
// もしこれが Validated であれば、(Monad がないので) Applicative の
// 実装はパラレルな実装になっていていいはずであり(実際そうなっているので)mapN でエラーを蓄積するような実装が可能なはずである.
// しかしここでは Either モナドを使っているためシーケンシャルな実装になっている. 
// fa が失敗であればその後の処理が中断されるので fb が失敗したときの値
// `oops2` を知り得ないので Left にエラーを蓄積できない.

// NOTE: NonEmptyParallel は empty が存在しない弱い `Parallel`
// def parMapN[Z](f: (A0, A1) => Z)(implicit p: cats.NonEmptyParallel[M]): M[Z]
data.parMapN((a,b) => a + b )
// => Left(value = "oops1oops2")
// パラレルな実装の場合、fa の失敗と fb の失敗は独立しているので、
// 計算は fa が失敗したときの値、fb が失敗したときの値の両方にアクセスできる. 
// よって Left にエラーを蓄積できる.

なお、上の例では Left を String にしたが、実際のコードではエラーを蓄積して後から取り出しやすいように Either[NonEmptyList,Int] のように NonEmptyList を使うことが多い.

以上のように、Parallel は対応する Monad を持たないような Applicative へのブリッジのようなメンタルモデルを持っている. あるいは対応する Monad を持たないような Applicative があることを示す証拠として定義されていると考えてもいいかもしれない.

終わりに

この Parallel に関係してそうなことをタイムリーに Kory さんが Twitter で言及していた.

自然変換や自然同型については詳しくないので勉強したい...(しろ)

https://twitter.com/Kory__3/status/1595048236028682248

参考

https://kazu-yamamoto.hatenablog.jp/entry/20101211/1292021817
https://stackoverflow.com/questions/23342184/difference-between-monad-and-applicative-in-haskell

Discussion