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

# モナド

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

----

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

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

----

# 12.1 モナドの一般化

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

```scala
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)(_ :: _))
```

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

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

```scala
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 アプリカティブトレイト

```scala
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を使って実装できる
- すべてのアプリカティブはファンクタである

----

```scala: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))
```

----

```scala: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)
  }
}
```

----

```scala: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] を示せる
- すべてのモナドはアプリカティブファンクタである

---

```scala
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だけでは実装不可能

----

```scala
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不要

```scala
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必要

```scala
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不要

```scala
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必要

```scala
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 モナドではないアプリカティブファンクタ

----

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

```scala
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))
  }
}
```

----

```scala: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

```scala: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)
  }
}
```

----

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

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

----

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

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

----

```scala
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]
```

----

```scala: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
    }
}
```

----

```scala
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 左単位元と右単位元

### ファンクタ則

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

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

```scala
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 結合性

```scala
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)
```

結合の順番は自由

----

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

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

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

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

# 積の自然性

```scala
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)
```

----

```scala
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する前に変換しても後に変換しても同じ

```scala
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))
```

----

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

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

----

```scala: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]
  }
```

----

```scala: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))
  }
```

----

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

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

----

```scala: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 に直接依存しない

```scala
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

----

```scala: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用, ... と記述するのはめんどくさい

```scala
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)
}
```

----

```scala: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とは違い元の構造を維持する

```scala
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の使用

```scala: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を表現できる

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

```scala
type ConstInt[A] = Int
```

GをConstIntとして

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

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

完全に一致・・・・！

----

```scala
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を持つ何か

```scala: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 を使った走査

```scala
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を実行すれば何らかの内部状態を管理する複雑な走査を実装できる

----

```scala
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)
```

```scala
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
```

----

```scala
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
```

----

```scala
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
```

----

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

----

```scala: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 トラバーサブルな構造の場合

```scala
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
```

----

```scala
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 走査の融合

```scala: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 入れ子の走査

```scala: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は文脈が存在する(前の計算結果が次に実行される計算に影響をおよぼす)ので汎用的には合成できない

```scala: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))
}
```

----

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

```scala
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を一般化した結果
- アロー、カテゴリー(圏)、コモナド・・・・