Functor, Applicative, Traversable, Monad について

FP in Scala を読みながら Funcor, Applicative, Traversable, Monad あたりの整理をしていきます。

Functor
Applicative
Traversable
Monad

環境:

Scala 2.12.7
Scalaz 7.2.27
Cats 1.6.0

1. Functor

Scala では Functor は以下のように表現されます。感覚としては型パラメータを 1 つ取り map が定義できるデータ構造には Functor を与えることができるという感じです。

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

例えば Option には以下のように Functor を定義できます。

trait OptionFunctor extends Functor[Option] {
  override def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa match {
    case None    => None
    case Some(v) => Some(f(v))
  }
}
object OptionFunctor extends OptionFunctor

scala> val f: Int => Int = _ + 1
scala> val fa: Option[Int] = Some(1)
scala> val F: Functor[Option] = OptionFunctor

scala> F.map(fa)(f)
res2: Option[Int] = Some(2)

上の定義から Functor は「F の中身に f を適用する」ものだと見れますが、別の見方をすれば「f: A => B から f’: F[A] => F[B] という関数を産み出す」ものでもあります。この場合 Functor は f を f’ に持ち上げる (lift) と言ったりします。

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

// change order of parameter lists
def mapAnother[A, B](f: A => B)(fa: F[A]): F[B] = map(fa)(f)

// partial application of mapAnother
def lift[A, B](f: A => B): F[A] => F[B] = mapAnother(f)

Functor Laws

Functor は以下の 2 つの法則を満たす必要があります。

trait Functor[F[_]] {
  ...

  trait FunctorLaws {
    def identityMorphisms[A](fa: F[A]): Boolean =
      map(fa)(identity) == fa

    def compositionMorphisms[A, B, C](fa: F[A])(f: B => C, g: A => B): Boolean =
      map(fa)(f compose g) == map(map(fa)(g))(f)
  }
}

Functor は単体で何か面白いことができるという感じではなさそうですが、これから出てくる Applicative や Monad を定義する前提となる型クラスです。

2. Applicative

以下のような 2 引数をとる関数を F[_] のもとで計算させようとする場合、Functor だけでは不可能なことに気が付きます。

scala> val f: Int => Int => Int = x => y => x + y
scala> val fa: Option[Int] = Some(1)
scala> val fb: Option[Int] = Some(2)

scala> F.map(fa)(f)
res3: Option[Int => Int] = Some($$Lambda$5655/795336053@52d356b9)

// Functor cannot apply fb: Option[Int] to res3: Option[Int => Int] ...

Applicative があればそれが可能になります。Applicative は

trait Applicative[F[_]] extends Functor[F] {
  def pure[A](a: => A): F[A]
  def ap[A, B](ff: F[A => B])(fa: F[A]): F[B]
}

あるいは

trait Applicative[F[_]] extends Functor[F] {
  def pure[A](a: => A): F[A]
  def map2[A, B, C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C]
}

と表されます。

これは換言すれば ap と map2 は互いに実装することができるということです。

trait Applicative[F[_]] extends Functor[F] {
  def pure[A](a: => A): F[A]

  def ap[A, B](ff: F[A => B])(fa: F[A]): F[B] =
    map2(ff, fa)((f, a) => f(a))

  def map2[A, B, C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C] =
    ap(ap(pure(f.curried))(fa))(fb)
}

定義を見るとわかるように Applicative を定義する場合 Functor も定義する必要があります (というより map は ap と pure から定義できるので、Applicative なら Functor でもある、という表現の方が正しいのかも)。

例えば Option の Applicative は以下のように実装されます。

trait OptionApplicative extends Applicative[Option] with OptionFunctor {
  override def pure[A](a: => A): Option[A] =
    Some(a)
  override def ap[A, B](ff: Option[A => B])(fa: Option[A]): Option[B] =
    for {
      f <- ff
      a <- fa
    } yield f(a)
}
object OptionApplicative extends OptionApplicative

これを使用して先程の例をもう一度試してみます。

scala> val f: Int => Int => Int = x => y => x + y
scala> val fa: Option[Int] = Some(1)
scala> val fb: Option[Int] = Some(2)

scala> val F: Applicative[Option] = OptionApplicative

scala> F.pure(f)
res4: Option[Int => (Int => Int)] = Some($$Lambda$5654/361077792@45bb6e87)

scala> F.ap(res4)(fa)
res6: Option[Int => Int] = Some($$Lambda$5655/795336053@233ef495)

scala> F.ap(res6)(fb)
res7: Option[Int] = Some(3)

無事 f を lift して Some(3) という値を手に入れることができました。

Product and Compose

型クラスの中には G[_], H[_] に対して型クラスの定義が与えられるならばその積 (product) type f[C] = (G[C], H[C]) や合成 (compose) type f[C] = G[H[C]] に対する定義も導出できるというものが存在します。そのようなものの例は Haskell の Data.Functor.Product や Data.Functor.Compose で提供されるものです。

Applicative もそうした型クラスの一つであり、積 (product) は以下のように定義されます。

def product[G[_], H[_]](implicit G: Applicative[G],
                        H: Applicative[H]): Applicative[({ type f[C] = (G[C], H[C]) })#f] =
  new Applicative[({ type f[C] = (G[C], H[C]) })#f] {
    override def pure[C](a: => C): (G[C], H[C]) =
      (G.pure(a), H.pure(a))
    override def ap[C, D](ff: (G[C => D], H[C => D]))(fa: (G[C], H[C])): (G[D], H[D]) =
      (G.ap(ff._1)(fa._1), H.ap(ff._2)(fa._2))
  }

scala> val a = Applicative.product(OptionApplicative, OptionApplicative)
scala> val x = (Option(1), Option(2))
scala> val y =(Option(2), Option(3))

scala> a.map2(x, y)((fst, snd) => fst + snd)
res5: (Option[Int], Option[Int]) = (Some(3),Some(5))

Applicative の合成 (compose) の定義です。

def compose[G[_], H[_]](implicit G: Applicative[G], H: Applicative[H]): Applicative[({ type f[C] = G[H[C]] })#f] =
  new Applicative[({ type f[C] = G[H[C]] })#f] {
    override def pure[A](a: => A): G[H[A]] =
      G.pure(H.pure(a))
    // implement map2 or ap
    override def map2[A, B, C](ga: G[H[A]], gb: G[H[B]])(f: (A, B) => C): G[H[C]] =
      G.map2(ga, gb)((ha, hb) => H.map2(ha, hb)(f))
    override def ap[A, B](gf: G[H[A => B]])(fa: G[H[A]]): G[H[B]] =
      G.ap(G.map(gf)(hf => (ha: H[A]) => H.ap(hf)(ha)))(fa)
  }

scala> val a = Applicative.compose(OptionApplicative, OptionApplicative)

scala> val x = a.pure(1)
x: Option[Option[Int]] = Some(Some(1))
scala> val y = a.pure(2)
y: Option[Option[Int]] = Some(Some(2))

scala> a.map2(x, y)(_ + _)
res0: Option[Option[Int]] = Some(Some(3))

Applicative Laws

以下は Applicative が満たすべき法則です。様々な表現の仕方があるようですが、Haskell の Control.Applicative パッケージの定義を参考にしました。

trait Applicatie[F[_]] extends Functor[F] {
  ...

  trait ApplicativeLaws {
    // pure id <*> v = v
    def identity[A](fa: F[A]): Boolean =
      ap(pure((a: A) => a))(fa) == fa

    // pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
    def composition[A, B, C](fa: F[A => B], fb: F[B => C], fc: F[A]): Boolean = {
      def compose[X, Y, Z](f: X => Y, g: Y => Z): X => Z = g compose f
      ap(ap(ap(pure((compose[A, B, C] _).curried))(fa))(fb))(fc) == ap(fb)(ap(fa)(fc))
    }

    // pure f <*> pure x = pure (f x)
    def homomorphism[A, B](f: A => B, a: A): Boolean =
      ap(pure(f))(pure(a)) == pure(f(a))

    // u <*> pure y = pure ($ y) <*> u
    def interchange[A, B](f: F[A => B], a: A): Boolean =
      ap(f)(pure(a)) == ap(pure((g: A => B) => g(a)))(f)
  }
}

With Scalaz

Scalaz で定義されている Applicative を利用してみます。

独自に定義した Applicative と異なり、Scalaz では ap にあたる定義が Apply という別 trait で与えられています。

package scalaz

trait Apply[F[_]] extends Functor[F] with ApplyParent[F] { self =>
  def ap[A,B](fa: => F[A])(f: => F[A => B]): F[B]
  ...
}

package scalaz

trait Applicative[F[_]] extends Apply[F] with ApplicativeParent[F] { self =>
  def point[A](a: => A): F[A]
  // alias for point
  final def pure[A](a: => A): F[A] = point(a)
  ...
}

利用例:

scala> import scalaz.Applicative, scalaz.std.option._

scala> val f: (Int, Int) => Int =  _ + _
f: (Int, Int) => Int = $$Lambda$5716/1068560501@6a87218e

scala> val F: Applicative[Option] = implicitly
F: scalaz.Applicative[Option] = scalaz.std.OptionInstances$$anon$1@327fbcbc

scala> F.apply2(F.pure(1), F.pure(2))(f)
res20: Option[Int] = Some(3)

With Cats

Cats でも Applicative を利用してみます。

Scalaz と同様 ap にあたる定義は Apply trait で定義されています。

package cats

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

package cats

@typeclass trait Applicative[F[_]] extends Apply[F] with InvariantMonoidal[F] { self =>
  def pure[A](x: A): F[A]
  ...
}

利用例:

scala> import cats.Applicative, cats.instances.option._, cats.syntax.apply._, cats.syntax.applicative._

scala> val F: Applicative[Option] = implicitly
F: cats.Applicative[Option] = cats.instances.OptionInstances$$anon$1@e30d611

scala> val f: Int => Int => Int = x => y => x + y
f: Int => (Int => Int) = $$Lambda$5868/630792925@345136fd

scala> F.pure(f).ap(F.pure(1)).ap(F.pure(2))
res10: Option[Int] = Some(3)

3. Traversable

Scala 標準ライブラリの scala.concurrent.Future には traverse, sequence というメソッドがありますが、これを一般化した型クラスが Traversable です。標準ライブラリには既に同名の trait が存在しているのでここでは FP in Scala にならって Traverse として定義します。

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

traverse から map や foldMap といった関数が定義できるので Traverse であれば F[_] は Functor や Foldable 型クラスも提供できます。この導出は少し難しいのですが、それぞれ traverse にどのような Applicative を渡すかが肝になります。

Functor の map については Id といういわばもらった値を包むだけというデータ構造を使用します。

Id の定義:

case class Id[A](value: A)

trait IdApplicative extends Applicative[Id] {
  override def map[A, B](fa: Id[A])(f: A => B): Id[B] = Id(f(fa.value))
  override def pure[A](a: => A): Id[A] = Id(a)
  override def ap[A, B](ff: Id[A => B])(fa: Id[A]): Id[B] = Id(ff.value(fa.value))
}

object IdApplicative extends IdApplicative

Id を利用した map の定義:

  override def map[A, B](fa: F[A])(f: A => B): F[B] =
    traverse(fa)(a => Id(f(a)))(IdApplicative).value

Foldable の foldMap については与えられる Monoid について Applicative を定義します。Applicative[F] を定義するには F が型パラメータを 1 つ受け取れないといけないので、 M にあえて Const[M, B] という型エイリアスをつけているようです。

Applicative for Monoid:

type Const[M, B] = M

implicit def monoidApplicative[M](M: Monoid[M]): Applicative[({ type f[A] = Traverse.Const[M, A] })#f] =
  new Applicative[({ type f[A] = Const[M, A] })#f] {
    override def pure[A](a: => A): M = M.zero
    override def ap[A, B](ff: M)(fa: M): M = M.append(ff, fa)
  }

monoidApplicative を利用した foldMap の実装:

  override def foldMap[A, M](fa: F[A])(f: A => M)(implicit m: Monoid[M]): M =
    traverse[({ type f[x] = Const[M, x] })#f, A, Nothing](fa)(f)(monoidApplicative(m))

List に対する Traverse の定義例は以下のようになります。

trait ListTraverse extends Traverse[List] {
  override def map[A, B](fa: List[A])(f: A => B): List[B] = fa.map(f)
  override def traverse[G[_]: Applicative, A, B](fa: List[A])(f: A => G[B]): G[List[B]] = {
    val G: Applicative[G] = implicitly
    fa.foldRight(G.pure(List.empty[B]))((a, acc) => G.map2(f(a), acc)(_ :: _))
  }
}
object ListTraverse extends ListTraverse

使用例:

// Defined above
scala> implicit val OptionApplicative: Applicative[Option] = OptionApplicative

scala> ListTraverse.traverse(List(1, 2, 3))(x => Option(x+1))
res2: Option[List[Int]] = Some(List(2, 3, 4))

scala> ListTraverse.traverse(List(1, 2, 3))(x => if (x % 2 == 0) Some(x) else None)
res3: Option[List[Int]] = None

Product and Compose

Applicative と同様 Traverse も積 (product), 合成 (compose) が可能です。

Traversable の積 (product):

  def product[G[_], H[_]](implicit G: Traverse[G], H: Traverse[H]): Traverse[({ type f[C] = (G[C], H[C]) })#f] =
    new Traverse[({ type f[C] = (G[C], H[C]) })#f] {
      override def traverse[F[_]: Applicative, A, B](fa: (G[A], H[A]))(f: A => F[B]): F[(G[B], H[B])] = {
        val fgb: F[G[B]] = G.traverse(fa._1)(f)
        val fhb: F[H[B]] = H.traverse(fa._2)(f)
        implicitly[Applicative[F]].map2(fgb, fhb)((x, y) => (x, y))
      }
    }

Traversable の合成 (compose):

  def compose[G[_], H[_]](implicit G: Traverse[G], H: Traverse[H]): Traverse[({ type f[C] = G[H[C]] })#f] =
    new Traverse[({ type f[C] = G[H[C]] })#f] {
      override def traverse[F[_]: Applicative, A, B](fa: G[H[A]])(f: A => F[B]): F[G[H[B]]] =
        G.traverse(fa)(ha => H.traverse(ha)(f))
    }

Traversable Laws

Traversable にも満たすべき法則がありますが、ここでは Haskell の Data.Traversable パッケージを参照としてお茶を濁します。

4. Monad

Monad の定義例です。定義のようにすべての Monad は Applicative でもあります。

trait Monad[F[_]] extends Applicative[F] {
  def unit[A](a: => A): F[A]
  def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]
}

例えば Option に対する Monad は以下のように定義できます。

trait OptionMonad extends Monad[Option] with OptionApplicative {
  def unit[A](a: => A): Option[A] =
    Some(a)
  def flatMap[A, B](fa: Option[A])(f: A => Option[B]): Option[B] =
    fa.flatMap(f)
}
object OptionMonad extends OptionMonad

scala> val M = Monad.OptionMonad

scala> M.flatMap(M.unit(1))(x => Some(x+1))
res2: Option[Int] = Some(2)

Monad Laws

Monad が満たすべき法則です。Haskell の Control.Monad パッケージを参考にしました。

trait Monad[F[_]] extends Applicative[F] {
    ...

  trait MonadLaws extends ApplicativeLaws {
    // return a >>= k  =  k a
    def leftIdentity[A, B](a: A, f: A => F[B]): Boolean =
      flatMap(unit(a))(f) == f(a)

    // m >>= return  =  m
    def rightIdentity[A, B](a: A, f: A => F[B]): Boolean =
      flatMap(f(a))(x => unit(x)) == f(a)

    // m >>= (\x -> k x >>= h)  =  (m >>= k) >>= h
    def associativity[A, B, C](fa: F[A], f: A => F[B], g: B => F[C]): Boolean =
      flatMap(fa)(a => flatMap(f(a))(g)) == flatMap(flatMap(fa)(f))(g)
  }

慣れるまでは associativity の実装がわかりにくく感じます。FP in Scala では Kleisli 射 A => F[B] という形の関数を用いた表記も示しているのでそれをやってみます。

import scala.language.higherKinds

/**
  * Representation of a function `A => F[B]`
  * ref. scalaz.Kleisli
  * ref. cats.data.Kleisli
  */
case class Kleisli[F[_], A, B](run: A => F[B]) { self =>
  def compose[C](k: Kleisli[F, C, A])(implicit M: Monad[F]): Kleisli[F, C, B] =
    Kleisli(c => M.flatMap(k.run(c))(self.run))

  // alias for compose
  def <=<[C](k: Kleisli[F, C, A])(implicit M: Monad[F]): Kleisli[F, C, B] =
    compose(k)

  def andThen[C](k: Kleisli[F, B, C])(implicit M: Monad[F]): Kleisli[F, A, C] =
    k.compose(this)

  // alias for andThen
  def >=>[C](k: Kleisli[F, B, C])(implicit M: Monad[F]): Kleisli[F, A, C] =
    andThen(k)
}

使用例:

scala> implicit val M: Monad[Option] = OptionMonad
scala> val f: Kleisli[Option, Int, Int] = Kleisli(x => Some(x+1))
scala> val g: Kleisli[Option, Int, Int] = Kleisli(x => Some(x*2))
scala> val h: Kleisli[Option, Int, Int] = Kleisli(x => Some(x+2))

scala> val composed1 = (f <=< g ) <=< h

scala> val composed2 = f <=< (g <=< h)

scala> composed1.run(4)
res6: Option[Int] = Some(13)

scala> composed2.run(4)
res7: Option[Int] = Some(13)

Monad Laws の書き換え:

    // return a >>= k  =  k a
    def leftIdentity[A, B](a: A, f: A => F[B])(implicit M: Monad[F]): Boolean =
      (Kleisli(f) <=< Kleisli(unit)).run(a) == f(a)

    // m >>= return  =  m
    def rightIdentity[A, B](a: A, f: A => F[B])(implicit M: Monad[F]): Boolean =
      (Kleisli((b: B) => unit(b)) <=< Kleisli(f)).run(a) == f(a)

    // m >>= (\x -> k x >>= h)  =  (m >>= k) >>= h
    def associativity[A, B, C, D](f: A => F[B], g: B => F[C], h: C => F[D])(implicit M: Monad[F]): Boolean =
      ((Kleisli(h) <=< Kleisli(g)) <=< Kleisli(f)) == (Kleisli(h) <=< (Kleisli(g) <=< Kleisli(f)))

associativity はこれ同じなのか? と疑問に思いますが、はじめに示した

    def associativity[A, B, C](fa: F[A], f: A => F[B], g: B => F[C]): Boolean =
      flatMap(flatMap(fa)(f))(g) == flatMap(fa)(a => flatMap(f(a))(g))

を以下のように書き換えても意味は変わらないはずです。

    // change type parameters A, B, and C to B, C, D respectively
    // then, argument fa: F[B] is converted to f: A => F[B]
    def associativity3[A, B, C, D](f: A => F[B], g: B => F[C], h: C => F[D]): Boolean =
      ((a: A) => flatMap(flatMap(f(a))(g))(h)) ==
        ((a: A) => flatMap(f(a))(a => flatMap(g(a))(h)))

ここから flatMap を Kleisli に変換していけば同じ式が出てきそうです。

Product and Compose

Monad については積 (product) に対する Monad は導出できます。

def product[G[_], H[_]](implicit G: Monad[G], H: Monad[H]): Monad[({ type f[C] = (G[C], H[C]) })#f] =
  new Monad[({ type f[C] = (G[C], H[C]) })#f] {
    override def unit[A](a: => A): (G[A], H[A]) =
      (G.unit(a), H.unit(a))
    override def flatMap[A, B](fa: (G[A], H[A]))(f: A => (G[B], H[B])): (G[B], H[B]) =
      (G.flatMap(fa._1)(f andThen (_._1)), H.flatMap(fa._2)(f andThen (_._2)))
  }

合成 (compose) については一般にはできません。ただ各 Monad について Monad Transformer と呼ばれるものを定義し、合成のような形で扱うという方法はあります。Monad Transformer は初見うっとなる概念なのですが下記のスライドが個人的には雰囲気を掴むのにとてもよかった覚えがあります。

IO (Maybe a)というタイトルでモナド変換子について学んだことを話した - #LT駆動

With Scalaz

Scalaz の Monad を利用してみます。

独自に定義した Monad とは違い、 flatMap 定義は Monad ではなく Bind trait で定義されます。これは flatMap は提供できるが unit にあたる実装を定義できない場合があるためのようです。

package scalaz

trait Bind[F[_]] extends Apply[F] with BindParent[F] { self =>
  def bind[A, B](fa: F[A])(f: A => F[B]): F[B]
  ...
}

package scalaz

trait Monad[F[_]] extends Applicative[F] with Bind[F] { self =>
  ...
}

利用例:

scala> import scalaz.Monad, scalaz.std.option._, scalaz.syntax.monad._

scala> def foo[F[_]](implicit M: Monad[F]): F[Int] =
     |   M.point(1).flatMap(x => M.point(x+1))

scala> foo[Option]
res0: Option[Int] = Some(2)

With Cats

Cats の Monad を利用してみます。

Scalaz と同様 Cats でも flatMap は Monad ではなく FlatMap trait で定義されます。

package cats

@typeclass trait FlatMap[F[_]] extends Apply[F] {
  def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]
  ...
}

package cats

@typeclass trait Monad[F[_]] extends FlatMap[F] with Applicative[F] {
    ...
}

利用例:

scala> import cats.Monad, cats.instances.option._, cats.syntax.flatMap._

scala> def foo[F[_]](implicit M: Monad[F]): F[Int] =
     |   M.pure(1).flatMap(x => M.pure(x+1))

scala> foo[Option]
res0: Option[Int] = Some(2)