アプリカティブファンクタとトラバーサブルファンクタ

by bloody_snow

1 / 65

モナド

unit/flatMapを持っている
結合律/同一律を持っている
ex. Option, List, Stream, State, Rand, Par, Gen, Parser, ...
強力なインターフェイス

アプリカティブファンクタ

モナドに関連する抽象概念
モナドより汎用的
モナドほど強力ではない

12.1 モナドの一般化

def sequence[A](lfa: List[F[A]]): F[List[A]] = 
  traverse(lfa)(fa => fa)

def traverse[A, B](la: List[A])(f: A => F[B]): F[List[B]] =
  la.foldRight(unit(List[B]()))((a, mbs) => map2(f(a), mbs)(_ :: _))

type X = List[A]
type Y = F[List[B]]

trait Monoid[X] {
  def foldRight[Y](z: Y)(f: (X, Y) => Y): Y
}

type X = A
type Y = List[B]
type Z = List[B]

def map2[X, Y, Z](mx: F[X], my: F[Y])(f: (X, Y) => Z): F[Z] =
  flatMap(mx)(x => map(my)(y => f(x, y)))

map2はflatMapを使って実装できる
unitとflatMapをプリミティブとしたものがMonad
unitとmap2からMonadのコンビネータのいくつかは実装できる
unitとmap2をプリミティブすると別の抽象化ができるんじゃね？ => アプリカティブファンクタ
(ただし、Monadほど強力ではなくなる)

12.2 アプリカティブトレイト

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

  // map2のCがB, map2のBは使っていない
  // mapはunitとmap2から実装できる
  def map[A, B](fa: F[A])(f: A => B): F[B] =
    map2(fa, unit(())((a, _) => f(a))

  def traverse[A, B](la: List[A])(f: A => F[B]): F[List[B]] =
    la.foldRight(unit(List[B]()))((a, mbs) => map2(f(a), mbs)(_ :: _))
}

mapはunitとmap2を使って実装できる
すべてのアプリカティブはファンクタである

12.1

def sequence[A](lfa: List[F[A]]): F[List[A]] =
  traverse(lfa)(fa => fa)

def replicateM[A](n: Int, fa: F[A]): F[List[A]] = {
  val lfa: List[F[A]] = List.fill(n)(fa)
  sequence(lfa)
}

def product[A, B](fa: F[A], fb: F[B]): F[(A, B)] = 
  map2(fa, fb)((a, b) => (a, b))

12.2

trait Applicative[F[_]] extends Functor[F] {
  def apply[A, B](fab: F[A => B])(fa: F[A]): F[B]
  def unit[A](a: => A): F[A]

  def map[A, B](fa: F[A])(f: A => B): F[B] = {
    val fab: F[A => B] = unit(f)
    apply(fab)(fa)
  }

  def map2[A, B, C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C] = {
    val g: A => (B => C) = f.curried
    val fbc: F[B => C] = map(fa)(g)
    apply(fbc)(fb)
  }

  def apply[A, B](fab: F[A => B])(fa: F[A]): F[B] = {
    val f: (A => B, A) => B = (g, x) => g(x)
    map2(fab, fa)(f)
  }
}

12.3

def map3[A, B, C, D](fa: F[A], fb: F[B], fc: F[C])(f: (A, B, C) => D): F[D] = {
  val g: A => B => C => D = f.curried
  val h: F[B => C => D] = apply(unit(g))(fa)
  val i: F[C => D] = apply(h)(fb)
  apply(i)(fc)

def map4[A, B, C, D, E](fa: F[A], fb: F[B], fc: F[C], fd: F[D])(f: (A, B, C, D) => E): F[E] = {
  val g: A => B => C => D => E = f.curried
  val h: F[B => C => D => E] = apply(unit(g))(fa)
  val i: F[C => D => E] = apply(h)(fb)
  val j: F[D => E] = apply(i)(fc)
  apply(j)(fd)
}

flatMapとunitからmapとmap2のデフォルト実装は提供できる
提供すれば Monad[F] ならば Applicative[F] を示せる
すべてのモナドはアプリカティブファンクタである

trait Monad[F[_]] extends Applicative[F] {
  def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B] = {
    val ffb: F[F[B]] = map(fa)(f)
    join(map(fa)(f))
  }

  def join[A](ffa: F[F[A]]): F[A] = flatMap(ffa)(fa => fa)

  def compose[A, B, C](f: A => F[B], g: B => F[C]): A => F[C] = { a: A =>
    val fb: F[B] = f(a)
    flatMap(fb)(g)
  }

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

  def map2[A, B, C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C] = {
    val fac: A => F[C] = a => map(fb)(b => f(a, b))
    flatMap(fa)(fac)
  }
}

12.3 モナドとアプリカティブファンクタの違い

モナドの最小限の演算

unit, flatMap
unit, compose
unit, map, join

unitとmap2はモナドの最小限の演算ではない。joinやflatMapはmap2とunitだけでは実装不可能

def join[A](f: F[F[A]]): F[A]

def unit[A](a: => A): F[A]
箱に入れるだけ
def map2[A, B, C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C]
箱から取り出して演算して箱に入れる
unitとmap2だけでは箱から取り出す操作が存在しない

12.3.1 OptionアプリカティブとOptionモナド

flatMap不要

val F: Applicative[Option] = ...

val depts: Map[String, String] = ... // 名前と部署
val salaries: Map[String, Double] = ... // 名前と給与
val o: Option[String] = 
  F.map2(depts.get("Alice"), salaries.get("Alice")(
    (dept, salary) => s"Alice in $dept makes $salary per year"
  )

flatMap必要

val F: Applicative[Option] = ...

val idsByName: Map[String, Int] = ... // IDと名前
val depts: Map[Int, String] = ... // IDと部署
val salaries: Map[Int, Double] = ... // IDと給与
val o: Option[String] = 
  idsByName.get("Bob").flatMap { id =>
    F.map2(depts.get(id), salaries.get(id))(
      (dept, salary) => s"Bob in $dept makes $salary per year"
    )
  }

12.3.2 ParserアプリカティブとParserモナド

flatMap不要

case class Row(date: Date, temperature: Double)

val F: Applicative[Parser] = ...
val d: Parser[Date] = ...
val temp: Parser[Double] = ...

val row: Parser[Row] = F.map2(d, temp)(Row(_, _))
val rows: Parser[List[Row]] = row.sep("\n")

flatMap必要

case class Row(date: Date, temperature: Double)

val F: Monad[Parser] = ...
val d: Parser[Date] = ...
val temp: Parser[Double] = ...

val header: Parser[Parser[Row]] = ...
val rows: Parser[List[Row]] = F.flatMap(header)(row => row.sep("\n"))

Applicative => 計算の構造が固定されており作用を並べていくだけ
Monad => 前の作用の結果に基づいて構造を動的に選択できる
Applicative => 計算のコンテキストに依存しない
Monad => 計算のコンテキストに依存させることができる
Monadでは作用はファーストクラスとなる。プログラムによって事前に選択されるのではなく、「解釈」時に生成できる。

12.4 アプリカティブファンクタの利点

traverseなどのコンビネータは前提ができるだけ少ない状態で実装するのが得策。データ型はflatMapよりもmap2を前提としたほうがよい。理由はApplicativeではあるがMonadではない型でtraverseが欲しければ毎回実装しないといけなくなる
ApplicativeはMonadほど強力ではないことでアプリカティブ作用のインタープリタに柔軟性をもたらす
アプリカティブファンクタは合成されますが、モナドは合成されない

12.4.1 モナドではないアプリカティブファンクタ

ストリームのアプリカティブ

val streamApplicative = new Applicative[Stream] {
  def unit[A](a: => A): Stream[A] = Stream.continually(a)
  def map2[A, B, C](a: Stream[A], b: Stream[B])(f: (A, B) => C): Stream[C] = {
    val ab: Stream[(a, b)] = a.zip(b)
    ab.map((a, b) => f(a, b))
  }
}

12.4

def sequence[A](lsa: List[Stream[A]]): Stream[List[A]]
  => traverse(lsa)(sa => sa)
  => lsa.foldRight(unit(List[A]()))((sa, sla) => map2(sa, sla)(_ :: _))

つまり

縦方向がList, 横方向がStream
(0, 0), (0, 1), (0, 2), ...
(1, 0), (1, 1), (1, 2), ...
...
(n, 0), (n, 1), ...

↓

縦方向がStream, 横方向がList
(0, 0), (1, 0), (2, 0), ... , (n, 0)
(0, 1), (1, 1), (2, 1), ... , (n, 1)
...

検証: エラーを蓄積するEither

12.5

def eitherMonad[E]: Monad[({type f[x] = Either[E, x]})#f] = new Monad[({type f[x] = Either[E, x]})#f] {
  def unit[A](a: => A): Either[E, x] = Right(a)
  def flatMap[A, B](eea: Either[E, A])(f: A => Either[E, B]) = eea match {
    case Right(a) => f(a)
    case Left(e) => Left(e)
  }
}

validName(field1).flatMap { f1 =>
  validBirthdate(field2).flatMap { f2 =>
    validPhone(field3).map { f3 =>
      WebForm(f1, f2, f3)
    }
  }
}

前段階が失敗すると後段は実行すらされない

map3(validName(field1),
  validBirthdate(field2),
  validPhone(field3)) { (f1, f2, f3) =>
    WebForm(f1, f2, f3)
  }

Monadの場合はflatMapがベースとなるのでLeftが来たタイミングでLeft(e)を返して処理を終了してしまう

sealed trait Validation[+E, +A]

case class Failure[E](head: E, tail: Vector[E] = Vector())
  extends Validation[E, Nothing]

case class Success[A](a: A) extends Validation[Nothing, A]

12.6

def validationApplicative[E]: Applicative[({type f[x] = Either[E, x]})#f] = new Applicative[({type f[x] = Either[E, x]})#f] {
  def unit[A](a: => A) =
  def map2[A, B, C](fa: Validation[E, A], fb: Validation[E, B])(f: (A, B) => C) =
    (fa, fb) match {
      case (Success(a), Success(b)) => Success(f(a, b))
      case (Failure(h1, t1), Failure(h2, t2)) => Failure(h1, t1 ++ Vector(h2) ++ t2)
      case (_, Failure(h, t)) => Failure(h, t)
      case (e@Failure(_, _), _) => e
    }
}

def validName(name: String): Validation[String, String] =
  if (name.nonEmpty) Success(name)
  else Failure("Name cannot be empty")

def validBirthdate(birthdate: String): Valication[String, Date] = try {
  import java.text._
  Success((new SimpleDateFormat("yyyy-MM-dd")).parse(birthdate))
} catch {
  Failure("Birthdate must be in the form yyyy-MM-dd")
}

def validPhone(phoneNumber: String): Validation[String, String] =
  if (phoneNumber.matches("[0-9]{10}")) Success(phoneNumber)
  else Failure("Phone number must be 10 digits")

def validWebForm(name: String, birthdate: String, phone: String): Validation[String, WebForm] =
  map3(validName(name), validBirthdate(birthdate), validPhone(phone))(WebForm(_, _, _))

12.5 アプリカティブの法則

12.5.1 左単位元と右単位元

ファンクタ則

map(v)(id) == v
map(map(v)(g))(f) == map(v)(f compose g) // f(g(x)) == (g ○ f)(x)

左単位元と右単位元の法則

def map[A, B](fa: F[A])(F: A => B): F[B] =
  map2(fa, unit(()))((a, _) => f(a))
  // map2(unit(()), fa)(_, a) => f(a))

map2(unit(()), fa)((_, a) => a) == fa
map2(fa, unit(()))((a, _) => a) == fa

12.5.2 結合性

def map3[A, B, C, D](fa: F[A], fb: F[B], fc: F[C])(f: (A, B, C) => D): F[D]

op(a, op(b, c)) == op(op(a, b), c)
compose(f, compose(g, h)) == compose(compose(f, g), h)

結合の順番は自由

def product[A, B](fa: F[A], fb: F[B]): F[(A, B)] = 
  map2(fa, fb)((a, b) => (a, b))

def assoc[A, B, C](p: (A, (B, C))): ((A, B), C) =
  p match { case (a, (b, c)) => ((a, b), c) }

product(product(fa, fb), fc) == map(product(fa, product(fb, fc)))(assoc)

product(fa, product(fb, fc)) => F[(A, (B, C))]

積の自然性

val F: Applicative[Option]

case class Employee(name: String, id: Int)
case class Pay(rate: Double, hoursPerYear: Double)

def format(e: Option[Employee], pay: Option[Pay]): Option[String] =
  F.map2(e, pay) { (e, pay) => s"${e.name} makes ${pay.rate * pay.hoursPerYear}"
}

val e: Option[Employee] = ...
val pay: Option[Pay] = ...
format(e, pay)

val F: Applicative[Option]

case class Employee(name: String, id: Int)
case class Pay(rate: Double, hoursPerYear: Double)

def format(e: Option[String], pay: Option[Double]): Option[String] =
  F.map2(e, pay) { (e, pay) => s"$e makes $pay" }

val e: Option[Employee] = ...
val pay: Option[Pay] = ...
format(F.map(e)(_.name), F.map(pay)(pay => pay.rate * pay.hoursPerYear))

map2する前に変換しても後に変換しても同じ

map2(a, b)(productF(f, g)) == product(map(a)(f), map(b)(g))

def productF[I, O, I2, O2](f: I => O, g: I2 => O2): (I, I2) => (O, O2) =
  (i, i2) => (f(i), g(i2))

12.7

左単位元と右単位元 => 明らか
結合性 => 明らか
自然性 => 明らか

ここまでやってきた我々にとっては明らか

12.8

def product[F[_], G[_]](F: Applicative[F], G: Applicative[G]): Applicative[({type f[x] = (F[x], G[x])})#f] = 
  new Applicative[({type f[x] = (F[x], G[x])})#f] {
    def unit[A](a: => A) = (F.unit(a), G.unit(a))
    def apply[A, B](fs: (F[A => B], G[A => B]))(p: (F[A], G[A])) =
      (F.apply(fs._1)(p._1), G.apply(fs._2)(p._2))
    def map2[A, B, C](fga: (F[A], G[A]), fgb: (F[B], G[B]))(f: (A, B) => C): (F[C], G[C]) =
      (F.map2(fga._1, fgb._1)(f), G.map2(fga._2, fgb._2)(f))
      // F.map2(fa: F[A], fb: F[B])(f: (A, B) => C): F[C]
  }

12.9

def compose[F[_], G[_]](F: Applicative[F], G: Applicative[G]): Applicative[({type f[x] = F[G[x]]})#f] = 
  new Applicative[({type f[x] = F[G[x]]})#f] = {
    def unit[A](a => A) = F.unit(G.unit(a))
    def map2[A, B, C](fga: F[G[A]], fgb: F[G[B]])(f: (A, B) => C) =
      F.map2(fga, fgb)((ga, gb) => G.map(ga, gb)(f))
  }

12.10

左単位元と右単位元 => 明らか
結合性 => 明らか
自然性 => 明らか

ここまでやってきた我々にとっては明らかと言わざるをえない・・・せやろ？

12.11

def compose[F[_], G[_]](F: Monad[F], G: Monad[G]): Monad[({type f[x] = F[G[x]]})#f] = 
  new Monad[({type f[x] = F[G[x]]})#f] = {
    def unit[A](a => A) = F.unit(G.unit(a))
    def flatMap[A, B](fga: F[G[A]])(f: A => F[G[B]]): F[G[B]] =
      F.flatMap(fga)(ga => G.flatMap(ga)(a => f(a) /// f(a)の型がF[G[B]]であってG[_]ではない
  }

12.6 トラバーサブルファンクタ

traverse, sequence, etc は flatMap に直接依存しない

def traverse[F[_], A, B](as: List[A])(f: A => F[B]): F[List[B]]
def sequence[F[_], A](fas: List[F[A]]): F[List[A]]

Listのような具体的な型コンストラクタが使用されていたときは「この型コンストラクタを抽象化したらどうなるか？」を考える
List以外のデータ型の一部はFoldable

12.12

def sequenceMap[K, V](ofa: Map[K, F[V]]): F[Map[K, V]] = 
  ofa.fold(unit(Map.empty[K, V])) { case (fMap, (k, fv)) =>
    map2(fMap, fv)((m, v) => m + (k -> v))
  }

List用, Map用, ... と記述するのはめんどくさい

trait Traverse[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](fga: F[G[A]]): G[F[A]] =
    traverse(fga)(ga => ga)
}

12.13

val listTraverse = new Traverse[List] {
  override def traverse[G[_], A, B](aList: List[A])(f: A => G[B])(implicit G: Applicative[G]): G[List[B]] =
    aList.foldRight(G.unit(List[B]())) { (a, gbList) => G.map2(f(a), gbList) { (b, bList) => b :: bList } }
}

val optionTraverse = new Traverse[Option] {
  override def traverse[G[_], A, B](oa: Option[A])(f: A => G[B])(implicit G: Applicative[G]): G[Option[B]] =
    oa.fold(G.unit(None)) { a => G.map(f(a))(Some(_)) }
}

case class Tree[+A](head: A, tail: List[Tree[A]])

val treeTraverse = new Traverse[Tree] {
  override def traverse[G[_], A, B](ta: Tree[A])(f: A => G[B])(implicit G: Applicative[G]): G[Tree[B]] =
    G.map2(f(ta.head), listTraverse.traverse(ta.tail) { a => traverse(a)(f) }) { (b, listTreeb) => Tree(b, listTreeb) }
}

List[Option[A]] => Option[List[A]]
- Traverse[List].sequence[Option, A, B]
- Noneが1つでも含まれるとNone
- それ以外の場合は元のListをSomeでラッピング
Tree[Option[A]] => Option[Tree[A]]
- Traverse[Tree].sequence[Option]
- Noneが1つでも含まれるとNone
- それ以外の場合は元のTreeをSomeでラッピング
Map[K, Par[A]] => Par[Map[K, A]]
- Traverse[Map[K, _]].sequence[Par]
- マップの全ての値を同時に評価する並列計算

sequenceやtraverseをベースとして多くの演算を汎用的に定義できる
トラバーサブルはデータ構造を受け取り、そのデータ構造に含まれるデータに関数を順番に適用して結果を生成する
foldMapとは違い元の構造を維持する

def foldMap[A, B](fa: F[A](f: A => B)(implicit B: Monoid[B]): B

参考

https://www.scala-lang.org/api/2.12.3/scala/collection/Traversable.html
https://www.scala-lang.org/api/2.12.3/scala/collection/Iterable.html

12.7 Traverseの使用

12.14

val idMonad = new Monad[Id] {
  def unit[A](a: => A) = a
  override def flatMap[A,B](a: A)(f: A => B): B = f(a)
}

trait Traverse[F[_]] extends Functor[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](fga: F[G[A]]): G[F[A]] =
    traverse(fga)(ga => ga)
  def map[A,B](fa: F[A])(f: A => B): F[B] =
    traverse[Id, A, B](fa)(f)(idMonad)
  // Id[F[B]] == F[B]
  // sequence(map(fa)(f)), sequenceが1つだけの箱(Id)
}

TraverseはFunctorの拡張
traverseはmapの一般化

12.7.1 モノイドからアプリカティブファンクタへ

traverseはmapの一般化
traverseでfoldMap/foldLeft/foldRightを表現できる

def traverse[G[_]:Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]]

type ConstInt[A] = Int

GをConstIntとして

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

def foldMap[A, B](as: List[A], m: Monoid[B])(f: A => B): B

完全に一致・・・・！

type Const[M, B] = M

implicit def monoidApplicative[M](M: Monoid[M]) =
  new Applicative[({type f[x] = Const[M, x]})#f] {
    def unit[A](a: => A): M = M.zero
    def map2[A, B, C](m1: M, m2: M)(f: (A, B) => C): M = M.op(m1, m2)
  }

trait Traverse[F[_]] extends Functor[F] with Foldable[F] {
  ...
  def foldMap[A, M](as: F[A])(f: A => M)(mb: Monoid[M]): M =
    traverse[({type f[x] = Const[M, x]})#f, A, Nothing](as)(f)(monoidApplicative(mb))
}

Functorはmapを持つ何か
FoldableはfoldRight/foldLeft/foldMap/concatenateを持つ何か
つまり、mapを持たないfoldMapを持つ何か

12.15

case class Iteration[A](a: A, f: A => A, n: Int) {
  def foldMap[B](g: A => B)(M: Monoid[B]): B = {
    def iterate(n: Int, b: B, c: A): B =
      if (n <= 0) b else iterate(n-1, g(c), f(a))
    iterate(n, M.zero, a)
  }
}

val iterationFunctor = new Functor[Iteration] {
  def map[A, B](fa: Iteration[A])(f: A => B): Iteration[B] = ???
  // g: B => B をどうやっても生成できないか・・・？
}

12.7.2 State を使った走査

case class State[S, +A](run: S => (A, S))
def get[S]: State[S, S] = State(s => (s, s)) // 渡された状態を値として返す
def set[S](s: S): State[S, Unit] = State(_ => ((), s)) // 新しい状態sを使って構築する

Stateは特に強力なアプリカティブファンクタ
Stateアクションを使ってコレクションでtraverseを実行すれば何らかの内部状態を管理する複雑な走査を実装できる

def traverseS[S, A, B](fa: F[A])(f: A => State[S, B]): State[S, F[B]] =
  traverse[({type f[x] = State[S, x]})#f, A, B](fa)(f)(Monad.stateMonad)

def zipWithIndex[A](ta: F[A]): F[(A, Int)] =
  traverseS(ta)((a: A) => (for {
    i: State[Int, Int] <- get[Int]
    _ <- set(i + 1)
  } yield (a, i))).run(0)._1

def toList[A](fa: F[A]): List[A] =
  traverseS(fa)((a: A) => (for {
    as <- get[List[A]]
    _ <- set(a :: as)
  } yield ()).run(Nil)._2.reverse

def mapAccum[S, A, B](fa: F[A], s: S)(f: (A, S) => (B, S)): (F[B], S) =
  traverseS(fa)((a: A) +> (for {
    s1 <- get[S]
    (b, s2) = f(a, s1)
    _ <- set(s2)
  } yield b)).run(s)

override def toList[A](fa: F[A]): List[A] =
  mapAccum(fa, List[A]())((a, s) => ((), a :: s))._2.reverse

def zipWithIndex[A](fa: F[A]): F[(A, Int)] =
  mapAccum(fa, 0)((a, s) => ((a, s), s + 1))._1

12.16

def reverse[A](fa: F[A]): F[A] =
  mapAccum(fa, toList(fa).reverse)((_, as) => (as.head, as.tail))._1

12.17

def foldLeft[A, B](fa: F[A])(z: B)(f: (B, A) => B): B =
  mapAccum(fa, z)((a, b) => ((), f(b, a)))._2

12.7.3 トラバーサブルな構造の場合

def zip[A, B](fa: F[A], fb: F[B]): F[(A, B)] =
  (mapAccum(fa, toList(fb)) {
    case (a, Nil) => sys.error("zip: Incompatible shapes.")
    case (a, b :: bs) => ((a, b), bs)
  })._1

def zipL[A, B](fa: F[A], fb: F[B]): F[(A, Option[B])] =
  (mapAccum(fa, toList(fb)) {
    case (a, Nil) => ((a, None), Nil)
    case (a, b :: bs) => ((a, Some(b)), bs)
  })._1

def zipR[A, B](fa: F[A], fb: F[B]): F[(Option[A], B)] =
  (mapAccum(fb, toList(fa)) {
    case (b, Nil) => ((None, b), Nil)
    case (b, a :: as) => ((Some(a), b), as)
  })._1

12.7.4 走査の融合

12.18

def fuse[G[_], H[_], A, B](fa: F[A])(f: A => G[B], g: A => H[B])
                          (implicit G: Applicative[G], H: Applicative[H]): (G[F[B]], H[F[B]]) =
  traverse[({type f[x] = (G[x], H[x])})#f, A, B](fa)(a => (f(a), g(a)))(G product H)

12.7.5 入れ子の走査

12.19

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

12.7.6 モナドの合成

Applicativeは文脈が存在しない(前の計算結果が次に実行される計算に影響をおよぼさない)ので常に合成可能
Monadは文脈が存在する(前の計算結果が次に実行される計算に影響をおよぼす)ので汎用的には合成できない

12.20

def composeM[G[_], H[_]](implicit G: Monad[G], H: Monad[H], T: Traverse[H]):
  Monad[({type f[x] = G[H[x]]})#f] = new Monad[({type f[x] = G[H[x]]})#f] {
    def unit[A](a: => A): G[H[A]] = G.unit(H.unit(a))
    override def flatMap[A,B](mna: G[H[A]])(f: A => G[H[B]]): G[H[B]] =
      G.flatMap(mna)(na => G.map(T.traverse(na)(f))(H.join))
}

表現力や威力と引き換えに合成性とモジュール性を一部残っているのがモナド
モナドの合成は合成用に構築されたカスタムモナドを使って解決するのが一般的
これはモナドトランスフォーマーと呼ばれる

case class OptionT[M[_], A](value: M[Option[A]])(implicit M: Monad[M]) {
  def flatMap[B](f: A => OptionT[M, B]): OptionT[M, B] =
    OptionT(value.flatMap {
      case None => M.unit(None)
      case Some(a) => f(a).value
    })
}

12.8 まとめ

Monadを一般化してApplicativeとTraverseという抽象インターフェイスを発見した
Applicativeは表現力はモナドよりも劣るが合成性が高い
Traverseはsequenceとtraverseを一般化した結果
アロー、カテゴリー(圏)、コモナド・・・・