関数型デザインに共通する構造 ~ FP in Scala 第10-12章

Jul 7, 2019 09:35 · 903 words · 5 minute read

“Scala関数型デザイン＆プログラミング ―Scalazコントリビューターによる関数型徹底ガイド”（原題: Functional Programming in Scala）“Part III 関数型デザインに共通する構造”を読んだときのメモ。

Monoid モノイド

何らかの型 A
2項連想演算 op(a1: A, a2: A): A

が与えられ、Monoid 則と呼ばれる次の2つの条件

結合律
- 任意の x: A, y: A, z: A に対し op(op(x, y), z) == op(x, op(y, z))
単位元 zero の存在
- 任意の x: A に対し、 op(x, zero) == x と op(zero, x) == x

を満たすとき、組（A, op, zero）を Monoid という。

trait を使った表現

trait Monoid[A] {
  def op(a1: A, a2: A): A
  def zero: A
}

Semigroup（半群）という代数構造は、Monoid から単位元の存在という条件を除いたものである。任意の Monoid は単位元を持つ Semigroup とも言える。なので Cats の Monoid は Semigroup を継承している。

例

String 型と結合 + と空文字列 ""
List[A] 型と結合 :: と空リスト Nil
Int 型と加算 + と 0
Int 型と乗算 * と 1
Boolean 型と論理積 && と True
Boolean 型と論理和 || と False
endofunction A => A と op(f, g) => f compose g と (a: A) => a

嬉しいこと

問題を並列計算可能なブロックに分割できる

何かしらの Monoid のシーケンス型（例 List[Monoid[A]]）を考える。この型の畳み込み fold は平衡畳み込みが可能である。

単純な要素から複雑な計算を組み立てるために Monoid を合成できること

型 A と型 B がそれぞれ、 Monoid[A] と Monoid[B] を形成できる場合、タプル型 (A, B) も Monoid を形成できる。これを積（product）と呼ぶ。よって foldMap[A, タプル] と Monoid の積を使うことで、複数の計算を同時に実行できる。例えば List[Int] に対してリストの要素数と各要素の和を1回の走査で計算可能である。

また複雑な計算の例として Map をマージする mapMergeMonoid が紹介されている。ネストした Map のマージがシンプルに書ける。

Foldable フォルダブル

List, Tree, Stream, IndexedSeq など畳み込み可能な型の抽象。

trait を使った表現

trait Foldable[F[_]] {
  def foldRight[A, B](as: F[A])(z: B)(f: (A, B) => B): B
  def foldLeft[A, B](as: F[A])(z: B)(f: (B, A) => B): B
  def foldMap[A, B](as: F[A])(f: A => B)(mb: Monoid[B]): B
}

Cats の Foldable は foldLeft と foldRight の実装が必要

Functor ファンクタ/関手

map を実装する型。プログラミング言語によっては Mappable とも呼ばれている。

次の2つの Functor 則を満たす。

恒等関数で map すると自分自身を返す。
- 任意のファンクタ fa に対し、 fa.map(a => a) == fa
ファンクタを f で map してから g で map した結果は、 f と g の合成関数で map した結果と同じである。
- fa.map(f).map(g) == fa.map(f andThen g)

別の書き方をすると、それぞれ次のようになる。

map(fa)(a => a) == fa
map(map(fa)(f))(g) == map(fa)(f andThen g)

trait を使った表現

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

Cats の Functor

嬉しいこと

FP in Scala には map をベースにして純粋に定義できる有益な演算はそれほど多くない とある。

唯一の例として distribute と codistribute が紹介されている。

distribute[A, B](fab: F[(A, B)]): (F[A], F[B])
codistribute[A, B](e: Either[F[A], F[B]]): F[Either[A, B]]

Monad モナド

FP in Scala には flatMappable とも呼んでもよいとあるように、Monad は flatMap を備えた構造である。なお flatMap と unit から map を実装できるため、すべての Monad は Functor である。

Monad 則という次の条件を満たすことが条件

結合律
- x.flatMap(f).flatMap(g) == x.flatMap(a => f(a).flatMap(g))
- 別の書き方をすれば
  - flatMap(flatMap(x)(f))(g) == flatMap(x)(a => flatMap(f(a)(g))
同一律
- 左単位元 flatMap(x)(unit) == x
- 右単位元 flatMap(unit(y))(f) == f(y)

この flatMap を使った Monad 則の書き方はあまり明白ではない。これらは以下に示す compose 関数をつかって書き下すと Monoid 則と似た表現になり理解しやすい。

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

結合律
- compose(compose(f, g), h) == compose(f, compose(g, h))
同一律
- 左単位元 compose(f, unit) == f
- 右単位元 compose(unit, f) == f

A => F[B] 型の関数はクライスリ射（Kleisli Arrow）、compose はクライスリ合成と呼ばれる。

flatMap の結合律と compose の結合律が等価であることを証明する。

   左辺
== compose(compose(f, g), h)
== a => flatMap(compose(f, g)(a))(h)             // compose の実装（定義？）より
== a => flatMap((x => flatMap(f(x)(g)))(a))(h)   // compose の実装より
== a => flatMap(flatMap(f(a)(g)))(h)             // 関数 x => flatMap(f(x)(g) に a を適用して
== a => flatMap(f(a))(b => flatMap(g(b))(h))     // flatMap の結合律より
== a => flatMap(f(a))(compose(g, h))             // compose の実装より
== compose(f, compose(g, h))                     // compose の実装より
== 右辺

flatMap の左単位元の同一律と compose の左単位元の同一律が等価であることを証明する。

   左辺
== compose(f, unit)
== a => flatMap(f(a))(unit)                      // compose の実装より
== a => f(a)                                     // flatMap の左単位元の同一律より
== f
== 右辺

flatMap の右単位元の同一律と compose の右単位元の同一律が等価であることを証明する。

   左辺
== compose(unit, f)
== a => flatMap(unit(a))(f)                      // compose の実装より
== a => f(a)                                     // flatMap の右単位元の同一律より
== f
== 右辺

trait を使った表現

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

unit と flatMap の組み合わせだけが最小のコンビネータというわけではなく、unit と compose の組み合わせもあるし、map, unit, join の組み合わせもある。map, unit, join を使った Monad 則も検索すれば出てくる。

嬉しいこと

変数を定義してバインドするためのコンテキストを提供し、変数置換を実行する。
for 内包表記で命令形プログラムのようなことが可能になる。

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

map2 と unit をプリミティブにもつ構造。map2 は flatMap から実装できるので全ての Monad は Applicative Functor。同様に map は map2 から実装できるので Applicative Functor はその名の通り Functor である。逆に Applicative Functor は関数 join[A](f: F[F[A]]): F[A] のように F のレイヤを削除する（平坦化する）ことはできないので、 Monad とは限らない。

Applicative 則

右単位元の法則
- map2(fa, unit(()))((a, _) => a) == fa
左単位元の法則
- map2(unit(()), fa)((_, a) => a) == fa
結合性
- product(product(fa, fb), fc) == map(product(fa, product(fb, fc))) { case (a, (b, c)) => ((a, b), c)
積の自然性
- map2(a, b)((i1, i2) => (f(i1), g(i2))) == product(map(a)(f), map(b)(g))

trait を使った表現

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]

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

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

apply と unit をプリミティブにもつ場合も同等の表現力がある。Applicative という名前はこちらから。

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]
}

product, map, unit を最小のプリミティブの組とすることも可能。

嬉しいこと

（Monad と異なり flatMap を前提とせず）sequence や traverse などのコンビネータを実装できる。
Monad のように前の結果を伝播して次の計算をすることができないが、前の結果を必要としない計算なら効率的に実装できる。
合成（compose）できる。Monad ではできない。

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

Applicative の項目ででてきた sequence や traverse は List という具体的な型コンストラクタを用いていたが、これを抽象化する。map は traverse から実装できるので Traversable Functor は Functor である。また foldMap, foldRight, foldLeft は traverse から実装できるので Traversable Functor は Foldable である。

sequence は F[G[A]] を G[F[A]] に変換する関数。

trait を使った表現

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

Cats の Traverse

嬉しいこと

State を用いて traverse することで、何らかの内部状態を管理する複雑な走査を実現できる。
構造を保ったまま走査できる。
- 例えば zip を実現できる。
一般的に Monad は合成できないが、合成する2つの Monad のうちひとつが Traversable な Monad であれば、合成できる。

まとめ

それぞれの構造の関係を整理した。

┌───────────────────────────────────┐
│               Functor             │
│  ┌─────────────┐                  │                 ┌──────────────┐
│  │ Applicative │  ┌───────────────┼───────────┐     │  Semigroup   │
│  │  ┌───────┐  │  │  ┌──────────┐ │ Foldable  │     │  ┌────────┐  │
│  │  │ Monad │  │  │  │ Traverse │ │           │     │  │ Monoid │  │
│  │  └───────┘  │  │  └──────────┘ │           │     │  └────────┘  │
│  └─────────────┘  └───────────────┼───────────┘     └──────────────┘
└───────────────────────────────────┘

参考
- https://typelevel.org/cats/typeclasses.html#type-classes-in-cats
- https://wiki.haskell.org/Typeclassopedia