こんにちは。RECRUIT Job for Student 2021 Summer で、スタディサプリ ENGLISH の開発を行なっていた有泉洵平です。

スタディサプリ ENGLISH のサーバサイドでは Extensible Effects を導入しています。それを扱うにあたり Monad, Monad Transformer, Extensible Effects を学んだため、この記事にまとめます。

また、RECRUIT Job for Student 2021 Summer に興味のある方は、そちらについても記事を書いたため、参考にしてください。

要約

• Monad とは、pure と flatMap というメソッドを持ち、Monad 則を満たすものである。
• 異なる Monad の型クラスは合成することができない。
• Monad Transformer を用いることで合成することができるが、型合わせが面倒になる。
• Extensible Effects を用いることで面倒な型合わせなしに合成することができる。

Monad

Monadとは

Monad (モナド) とは、pure と flatMap というメソッドを持ち、Monad 則¹⁾左単位元、右単位元、結合律のことを成立させるものである。
Monad 則についての詳細は省くが、以下のような Interface を満たすものと思えばよい。

trait Monad[M[_]] {
  def pure[A](a: A): M[A]
  def flatMap[A, B](ma: M[A])(f: A => M[B]): M[B]
}

この pure と flatMap という 2 つのプリミティブから、便利なメソッドを数多く作成することができる。

trait Monad[M[_]] {
  def pure[A](a: A): M[A]
  def flatMap[A, B](ma: M[A])(f: A => M[B]): M[B]
  def map[A, B](ma: M[A])(f: A => B): M[B] = flatMap(ma)(a => pure(f(a)))
  def flatten[A](mma: M[M[A]]): M[A] = flatMap(mma)(ma => ma)
  def ap[A, B](ma: M[A])(f: M[A => B]): M[B] = flatMap(ma)(a => map(f)(_(a)))
  ...
}

つまり、pure と flatMap を定義するだけで、様々なメソッドが使えるように抽象化されているのである。
様々なメソッドの中でも特に重要な点は、flatMap と map が定義されていて、 Monad のための syntax sugar である for 式が使えるということである。
例えば、flatMap と map を用いて書かれた以下のようなコードがあるとする。

monadA.flatMap(a =>
  monadB.map(b =>
    f(a, b)
  )
)

このコードと全く同じ意味を持つコードを for 式で書くと、以下のように逐次的に書くことができる。

for {
  a <- monadA
  b <- monadB
} yield f(a, b)

Monad の具体例

では、具体的な Monad を見ていこう。
Option, List, Either は Monad の Interface を満たすので Monad であると言える。

Option Monad

Option Monad は、値が存在しないかもしれない計算を表現できる。

val ma: Option[Int] = Some(1)
val mb: Option[Int] = Some(2)
val mc: Option[Int] = None
val res1: Option[Int] = for {
  a <- ma
  b <- mb
} yield a + b
val res2: Option[Int] = for {
  a <- ma
  c <- mc
} yield a + c
println(res1) // Some(3)
println(res2) // None

ma, mb はそれぞれ 1, 2 という値が存在するため、Some(3) が返る。一方で、mc は None で値は存在しないため、None が返るが、値が存在する場合と同じように記述することができる。

このように、値が存在しない場合でも、値が存在する場合と同じように扱えることがわかる。

Either Monad

Either Monad は、失敗するかもしれない計算を表現できる。

val ma: Either[String, Int] = Right(1)
val mb: Either[String, Int] = Right(2)
val mc: Either[String, Int] = Left("error")
val res1: Either[String, Int] = for {
  a <- ma
  b <- mb
} yield a + b
val res2: Either[String, Int] = for {
  a <- ma
  c <- mc
} yield a + c
println(res1) // Right(3)
println(res2) // Left("error")

ma, mb はそれぞれ 1, 2 という値が存在するため、Right(3) が返る。一方で、mc は Left("error") で失敗しているため、Left("error") が返るが、失敗してしない場合と同じように記述することができる。

このように、失敗する場合でも、失敗していない場合と同じように扱えることがわかる。

List Monad

List Monad は、非決定的な値を扱う計算を表現できる。

val ma: List[Int] = List(1, 2)
val mb: List[Int] = List(3, 4)
val mc: List[Int] = Nil
val res1: List[Int] = for {
  a <- ma
  b <- mb
} yield a + b
val res2: List[Int] = for {
  a <- ma
  c <- mc
} yield a + c
println(res1) // List(4, 5, 5, 6)
println(res2) // Nil

ma, mb はそれぞれ 1 かもしれないし 2 かもしれない、3 かもしれないし 4 かもしれないが、値が定まっている場合と同じように記述することができる。

このように、非決定的であることを気にせず扱えることがわかる。

Monadの合成不可能性

以上で挙げた List や Option, Either 以外にも、Reader や Writer, State などの様々なMonadがある。
そして、それらを組み合わせて以下のように使いたいと思うのは自然だろう。

val ma: Option[Int] = Some(1)
val mb: Either[String, Int] = Right(2)
val res: ? = for {
  a <- ma // ma: Option[Int]
  b <- mb // mb: Either[String, Int]
} yield a + b
println(res) // expected 3

もちろんこれでは、<- の右側にきている ma と mb の型が異なっているため、コンパイルが通らない。

では、Monadを組み合わせて Option[Either[String, Int]] と統一してみてはどうだろうか。

val ma: Option[Int] = Some(1)
val mb: Either[String, Int] = Right(2)
// convert from Option[Int] to Option[Either[String, Int]]
val oea: Option[Either[String, Int]] = ma.map(Right(_))
// convert from Either[String, Int] to Option[Either[String, Int]]
val oeb: Option[Either[String, Int]] = Some(mb)
val res: Option[Either[String, Int]] = for {
  ea <- oea // ea: Either[String, Int]
  eb <- oeb // eb: Either[String, Int]
} yield ea + eb
println(res)

一見正常なコードのように見えるが、Monadの合成ができていないため、for 式で取り出した ea や eb は Int ではなく Either[String, Int] となってしまう。
したがって、正常なコードにするためには以下のようにしなければならない。

val ma: Option[Int] = Some(1)
val mb: Either[String, Int] = Right(2)
val oea: Option[Either[String, Int]] = ma.map(Right(_))
val oeb: Option[Either[String, Int]] = Some(mb)
val res: Option[Either[String, Int]] = for {
  ea <- oea // ea: Either[String, Int]
  eb <- oeb // eb: Either[String, Int]
} yield for {
  a <- ea // a: Int
  b <- eb // b: Int
} yield a + b
println(res) // Some(Right(3))

もちろんこれで問題はないが、このようにしてしまうとコードが冗長になり、可読性も落ちてしまう。
では、Monadを合成するためにはどのようにすればよいのだろうか。
それを解決するための手法が Monad Transformer である。

Monad Transformer

Monad Transformer とは、2 つの異なる Monad を合成する際に、片方の Monad を固定することで Monad を合成できるようにする手法である。
例えば、M[Either[String, Int]] のように、合成するMonadの片方を Either と決めてしまうことで、合成できるようにしている。

ここでは、Monad Transformer を実現するライブラリとして cats を用いるとする。

Monad Transformer では、M[Either[A, B]] という型を EitherT[M, A, B] と表し、M[Option[A]] という型は OptionT[M, A] と表す。
また、cats には Monad の型を合わせるために、様々なメソッドが存在する。
例えば、EitherT の liftF というメソッドは、F[A] という Functor²⁾map を持ち、Functor 則を満たすものである。任意の Monad は Functor であるため、Monad と読み替えてもよい。 を EitherT[F, A] に lift するものである。

import cats.data.EitherT
val ma: Option[Int] = Some(1)
val mma: EitherT[Option, String, Int] = EitherT.liftF(ma)

他にも、EitherT の fromEither というメソッドは、特定の Applicative³⁾pure と ap を持ち、Applicative 則を満たすものである。任意の Monad はApplicative であるため、Monad と読み替えてもよい。 を用いて、Either を EitherT に変換するものである。

import cats.data.EitherT
val mb: Either[String, Int] = Right(2)
val mmb: EitherT[Option, String, Int] = EitherT.fromEither[Option](mb)

これらを使うと、以下のようにMonadを組み合わせることができる。

import cats.data.EitherT
val ma: Option[Int] = Some(1)
val mb: Either[String, Int] = Right(2)
val res: EitherT[Option, String, Int] = for {
  a <- EitherT.liftF(ma) // a: Int
  b <- EitherT.fromEither[Option](mb) // b: int
} yield a + b
println(res) // EitherT(Some(Right(3)))

これで、Either と Option という異なる 2 つの Monad を合成することができた。
しかし、合成する Monad の数が多くなると型のネスト数が増えていき、以下のように liftF などのメソッドを多用した型合わせゲームとなってしまう。

import cats.data.EitherT
import cats.data.OptionT
val ma: Option[Int] = Some(1)
val mb: Either[String, Int] = Right(2)
val mc: List[Int] = List(3, 4)
type EitherTListStringOrA[A] = EitherT[List, String, A]
val res: OptionT[EitherTListStringOrA, Int] = for {
  a <- OptionT.fromOption[EitherTListStringOrA](ma)
  b <- {
    val le: EitherTListStringOrA[Int] = EitherT.fromEither[List](mb)
    OptionT.liftF[EitherTListStringOrA, Int](le)
  }
  c <- {
    val le: EitherTListStringOrA[Int] = EitherT.liftF(mc)
    OptionT.liftF[EitherTListStringOrA, Int](le)
  }
} yield a + b + c
println(res) // OptionT(EitherT(List(Right(Some(6)), Right(Some(7)))))

このような Monad Transformer の欠点を解決するための方法が Extensible Effects(Eff) である。

Extensible Effects

ここでは、Eff を実現するためのライブラリとして atonos-eff を用いるとする。

Eff を用いて、上の例と同様に 3 つの異なる Monad を合成するコードを書くと以下のようになる。

import org.atnos.eff.Eff
import org.atnos.eff.Fx
import org.atnos.eff.all._
import org.atnos.eff.syntax.all._
import org.atnos.eff.|=
val ma: Option[Int] = Some(1)
val mb: Either[String, Int] = Right(2)
val mc: List[Int] = List(3, 4)
type EitherString[A] = Either[String, A]
type Stack = Fx.fx3[Option, EitherString, List]
type _eitherString[R] = EitherString |= R
def program[R: _option : _eitherString : _list]: Eff[R, Int] =
  for {
    a <- fromOption(ma)
    b <- fromEither(mb)
    c <- fromList(mc)
  } yield a + b + c
val res: List[Either[String, Option[Int]]] =
  program[Stack]
  .runOption
  .runEither
  .runList
  .run
println(res) // List(Right(Some(6)), Right(Some(7)))

このコードの詳細な説明は行わないが、大きなポイントは以下の 3 つである。

1. R: _option : _eitherString : _list によって、各計算を Eff で使えるようにしている。
2. R の部分に計算を押し込むことで、型合わせの必要性をなくしている。
3. 計算は runXXX という interpreter によって実行される。

型合わせをしなくてもよくなっていることは、program メソッドの中にある for 式を見てもらえればわかるだろう。
また、for 式は計算を組み立てているだけで、実際には計算は interpreter によって実行されるため、 Interpreter の実行順序によって、型のネストの順番を変更させることができるといったメリットもある。
例えば、上の例では List[Either[String, Option[Int]]] を取得しているが、Option[Either[String, List[Int]]] を取得したければ、runOption や runEither、runList の順番を入れ替えるだけでよい。

val res: Option[Either[String, List[Int]]] = 
  program[Stack]
    .runList
    .runEither
    .runOption
    .run
println(res) // Some(Right(List(6, 7)))

参考文献

• cats
• atnos-eff
• Monad Transformers Down to Earth
• Scala + CleanArchitecture に Eff を組み込んでみた