いまお世話になっている会社様の業務では、Scalaの様々な関数型ライブラリを使用する機会があるのですが、こちらの記事でもちょっと調べたFreeモナドとかをしっかり理解するためには、Scalaの関数型ライブラリがどういう考え方で作られているのか基礎から積み上げて勉強しないとちょっと厳しそうだなということで、Scala関数型デザイン&プログラミング―Scalazコントリビューターによる関数型徹底ガイドを1章〜13章までざーっと学習＆練習問題を7割ほど消化してみたので、その個人的な要約というか振り返りを備忘録代わりに書き留めておきたいと思います。

学習時間としては、1章と2章はそれぞれ数時間程度でしたが、3章以降は練習問題が多くなってくる(&それぞれの難易度が高い)ということもあり、私の場合は1章につきほぼ丸一日ほど必要になるという感じでした。

特にこの書籍では、前の章で作成したデータ型をそれ以降の章でも頻繁に使用するのですが、その度に前の章を復習する必要がある(大抵そのデータ型のことは忘れてしまっている)こと、および色々な型が組み合わさってくるとそれだけ理解も難しくなってくるため、後の章に行くほど前に進むのが大変になるという傾向があります。ここら辺ちょっと挫折しやすいポイントだと思うのでご注意ください。

(ちなみにこちらの書籍の練習問題の解答例等は、fpinscalaにアップされています)

また、13章までの振り返りを全部記述してからアップする予定だったのですが、思った以上に時間がかかってしまったため、一旦9章までの要約をアップして、10章〜13章は随時追加更新していく形にしたいと思います。

第1章関数型プログラミングとは

関数型プログラミングとは「純粋関数だけを使ってプログラミング(の主要な部分)を構築する」こと。
「純粋関数」とは「副作用のない関数」。関数が実行する全てのことが、その戻り値によって表される。
副作用とは下記のようなこと。

・変数を変更する(再代入/関数の引数の参照渡しとそれの変更)
・データ構造を直接変更する
・オブジェクトのフィールドを設定する
・例外をスローする、またはエラーで停止する(例外はOptionとかEitherとかで包むようにする)
・コンソールに出力する、またはユーザー入力を読み取る
・ファイルを読み取る
・画面上に描画する

副作用を発生させる層を本筋のロジックから切り離すことにより、テスタビリティを向上させられるという点が一つの大きなメリットである。
式が参照透過(参照先の式と置き換えることが可能)」であることにより、式の値がコンテキストに依存しないため、局所的なコードだけで式の値が推論可能であることによる可読性の向上も大きなメリットである。

第2章 Scala関数型プログラミングの準備

Scalaの基本的な文法の説明
高階関数の説明
- Scalaの高階関数のパラメータには、f、g、hのような名前を付けるのが慣例となっている。(高階関数が汎用的であるために、引数の実際の目的を説明しようがないため)
- 再帰関数内の関数(ヘルパー関数)には、goまたはloopという名称を用いるのが慣例となっている。
末尾再帰の説明
- 末尾再帰で記述すると、コンパイラがwhileループと同様なバイトコードに変換してくれる。(スタックオーバーフローを回避)
- @annotation.tailrecを付加することで、呼び出しが末尾再帰になっていない場合にコンパイラがエラーを出力してくれる。
- 「n番目のフィボナッチ数を取得する再帰関数を記述せよ」という練習問題がある。私の回答は下記のような感じ。
  - ちなみにこちらの書籍の練習問題をこなしていくと再帰関数を大量に記述することになるので、再帰関数の記述力と読解力はかなり向上すると思います。
```
def fib(n: Int): Int = {
  @annotation.tailrec
  def fib(cnt: Int, n1: Int, n2: Int): Int = {
    cnt match {
      case 0 => n1
      case _ => fib(cnt - 1, n2, n1 + n2)
    }
  }
  fib(n, 0, 1)
}
```
単相関数と多相関数の説明
- 単相関数一つの型のデータだけを操作する関数。例えばInt型やString型など固定の型だけを扱う関数
- 多相関数どのような型が渡されても動作する関数
  - 整合性がチェックされてコンパイルが通ったあとは型は消失しているので、実行時に型判定を行うような多相関数は警告が出る。この場合は[A: ClassTag]のようにしてimplicitのClassTag[A]型の変数が生成されるようにしておけば型判定が行える。(型は消去されてしまうが、変数は(implicitでも)消去されないのでこれが可能なのである)

第3章関数型プログラミングのデータ構造

Listデータ型

この章を読むと、ScalaのList型がおおよそどのような仕組みで実装されているかについて理解出来る。
下記のようなデータ構造が例示される。

sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[+A](head: A, tail: List[A]) extends List[A]

object List {
  def sum(ints: List[Int]): Int = // 型がIntに限定されているので実際にはこういう関数はない
    ints match {
      case Nil => 0
      case Cons(x, xs) => x + sum(xs)
    }

  def product(ds: List[Double]): Double = // 型がDoubleに限定されているので実際にはこういう関数はない
    ds match {
      case Nil => 1.0
      case Cons(0.0, _) => 0.0 
      case Cons(x, xs) => x * product(xs) 
    } 

  def apply[A](as: A*): List[A] =
    if (as.isEmpty) Nil 
    else Cons(as.head, apply(as.tail: _*)) 
}

上記のデータ構造に関する説明
- NilはobjectでConsはclassだが、どちらもScala内では「オブジェクト」で、さらに継承元がどちらもList[+A]であり、共変が指定されているので、List[Int]型の変数にはCons[Int]( = List[Int])だけでなく、Nil( = List[Nothing]も入れることが可能。
- List[+A]でなぜ共変が指定されているか、Nothingの用途は何かという点に関しては下記の記事の説明が非常に分かりやすい。
  - scala.Nothingは何のためにあるのか - kmizuの日記
- ConsはConstructの略らしい。
- sealed traitのように「sealed」を付けると、このtraitの実装が全てこのファイルで宣言されなければならないことを意味する。
  - 正確には、sealedが指定されたtrait(やclass)は、同一ファイル内のクラスからは継承出来るが、別ファイル内で定義されたクラスでは継承出来ない。(ただしsealedを継承したクラスは別ファイルのクラスからも継承可能)
- コレクション型のデータ型では、コンパニオンオブジェクトに引数が可変長のapplyメソッドを定義し、そのデータ型のインスタンスを生成するという方式が慣例らしい。
ちなみにScalaの実際のListは下記のように定義されている。(Consではなく::クラスが定義されている。また上記の例ではメソッドはコンパニオンオブジェクトに定義されているが、これはList[+A]とNilとConsの関係を分かりやすくするためにこのように定義しているものと思われる。ScalaのListでは各メソッドはList[+A]トレイトに定義されている)

sealed abstract class List[+A] extends AbstractSeq[A] ...
case object Nil extends List[Nothing] {...}
final case class ::[B](override val head: B, private[scala] var tl: List[B]) extends List[B] {...}

immutableであるメリット

上記のList型の変数に要素を追加したい場合は、下記のように新しいConsを返せばよい。

val xs = List(2, 3)
Cons(1, xs)

上記において、xsのcopyは行わないでよい。なぜなら上記で定義したListデータ型は、内部の変数(headとtail)を変更するメソッドを提供していないのでimmutableだからである。
- immutableにしておくメリットはここにもある。Consが、例えば「update」みたいな関数を提供して、head変数やtail変数を変更出来てしまうようにするとimmutableではなくなり、要素を追加する関数はcopyを行ったりしなければならなくなる。

高階関数の型推論の改善

def dropWhile[A](l: List[A], f: A => Boolean): List[A] = {
  ...
}

上記のシグネチャだと、使用する際にval ex1 = List.dropWhile(List(1, 2, 3, 4, 5), (x: Int) => x < 4)のように、無名関数にx: Intという型アノテーションを付加する必要がある。(付加しないとerror: missing parameter typeというエラーになる

def dropWhile[A](l: List[A])(f: A => Boolean): List[A] = {
  ...
}

上記のシグネチャだとScalaが型を推測可能になり、val ex1 = List.dropWhile(List(1, 2, 3, 4, 5))(_ < 4)のように型アノテーションが不要になる。

foldLeft/foldRight

この書籍の中ではfoldLeft関数またはfoldRight関数が様々な箇所で登場する。(後の章で登場するsequenceやtraverse等様々な関数がfoldLeftやfoldRightを使用して実装されている)
- 大量に登場するということは要するにそれだけ重要な関数＆これに類似する再帰の構造もよく出てくるので、この関数の引数と戻り値の構造や再帰の方法については暗記しておいた方がこの書籍のこれ以降のコードの理解が早くなると思われる。
- 関数のシグネチャ的に、foldRightの方が直観的で理解しやすい(無名関数の引数として渡されるタプルのうち、第一引数がリストの要素で、第二引数がアキュムレーターになる)ためか、こちらの書籍ではfoldLeftよりもfoldRightが頻繁に登場する。

@annotation.tailrec
def foldLeft[A,B](l: List[A], z: B)(f: (B,A) => B): B = l match { 
  case Nil => z
  case Cons(h,t) => foldLeft(t, f(z,h))(f)
}

def foldRight[A,B](l: List[A], z: B)(f: (A,B) => B): B = 
  foldLeft(reverse(l), z)((b,a) => f(a,b))

def reverse[A](l: List[A]): List[A] = 
  foldLeft(l, List[A]())((acc,h) => Cons(h,acc))

ちなみにScalaのListのfoldLeftは、末尾再帰ではなく下記のようにwhileループで作成されている。

def foldLeft[B](z: B)(@deprecatedName('f) op: (B, A) => B): B = {
  var acc = z
  var these = this
  while (!these.isEmpty) {
    acc = op(acc, these.head)
    these = these.tail
  }
  acc
}

override def foldRight[B](z: B)(op: (A, B) => B): B =
  reverse.foldLeft(z)((right, left) => op(left, right))

Listの末尾への要素追加が遅い理由

下記のように、末尾まで再帰する必要があるため。

def append[A](a1: List[A], a2: List[A]): List[A] =
  a1 match {
    case Nil => a2
    case Cons(h,t) => Cons(h, append(t, a2))
  }

代数的データ型

Listは、代数的データ型(ADT)(algebraic data typeと呼ばれるものの1つ。
代数的データ型とは、「一つ以上のデータコンストラクタによって形成されるデータ型」と「それらを操作する関数の集まり」と「関数の間の関係を指定する一連の法則」のこと。
- データ型がデータコンストラクタの「直和(非交和)」で構成され、各データコンストラクタがその引数の「直積」で構成されることから「代数的データ型」と言われる、という記述もされているが、あまり深く考えすぎずに「大体こんな感じのもの」という程度の理解で良いと思われる。
- Scalaの場合、sealed traitまたはabstractなクラスと、それをextendsしている1つ以上のデータコンストラクタ(大抵はcase classまたはcase object)と、それらに定義されている関数と法則が「代数的データ型」という理解で良いと思われる。
下記の記事等が参考になる。
下記のTreeというデータ構造も、典型的な「代数的データ型」の1つ。

sealed trait Tree[+A]
case class Leaf[A](value: A) extends Tree[A] 
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

第4章例外を使わないエラー処理

参照透過性について

下記の場合、java.lang.Exception: fail!が発生する。

def failingFn(i: Int): Int = {
  val y: Int = throw new Exception("fail!")
  try {
    val x = 42 + 5
    x + y
  }
  catch { case e: Exception => 43 } 
}

下記はres1: Int = 43となる。つまり例外がキャッチされる。

def failingFn2(i: Int): Int = {
  try {
    val x = 42 + 5
    x + ((throw new Exception("fail!")): Int)
  }
  catch { case e: Exception => 43 }
}

上記は「yが参照透過でない」ことを意味している。参照透過な式は参照先の式と置き換えても意味が変わらないが、上記では異なる結果となってしまっている。つまりyはコンテキスト(この場合はtry)に依存している。

例外に代わる手法

例外を発生させるコードの例

def mean(xs: Seq[Double]): Option[Double] =
  if (xs.isEmpty)
    throw new ArithmeticException("mean of empty list!")
  else Some(xs.sum / xs.length)

Optionデータ型を導入して、上記を書き換える

sealed trait Option[+A]
case class Some[+A](get: A) extends Option[A]
case object None extends Option[Nothing]

def mean(xs: Seq[Double]): Option[Double] =
  if (xs.isEmpty) None
  else Some(xs.sum / xs.length)

なぜOption型が優れているのかの理由が、「部分関数の例」や「空の値の場合のデフォルト値を呼び出し側に渡させる例」を示して色々記述されているが、割愛。

Optionデータ型の主要な関数のシグネチャ

sealed trait Option[+A] {
  def map[B](f: A => B): Option[B] = this match {
    case None => None
    case Some(a) => Some(f(a))
  }
  def flatMap[B](f: A => Option[B]): Option[B] =
    map(f) getOrElse None
  def getOrElse[B>:A](default: => B): B = this match {
    case None => default
    case Some(a) => a
  }
  def orElse[B>:A](ob: => Option[B]): Option[B] =
    this map (Some(_)) getOrElse ob
}

getOrElseとorElseが型パラメータBを使っているのは、「共変が指定された型パラメータ(この場合はA)は関数の引数として使用出来ない」という制約に対処するため。この制約に関しては下記の記事が参考になる。
- 共変・反変・上限境界・下限境界の関係性まとめ - Qiita

Option型を使うシナリオ

case class Employee(name: String, department: String) {
  def manager: Option[Employee] = ...
}
def lookupByName(name: String): Optione[Employee] = ...
def joeDepartment: Option[String] = lookupByName("joe").map(_.department).getOrElse("Default Dept")
def joeManager: Option[Employee] = lookupByName("joe").flatMap(_.manager)

Noneが返されればずっとNoneのままメソッドチェインが実行されていく。

Option型を使う場合の一般的なパターン

map/flatMap/filter等の呼び出しを通じてOptionを変換し、エラー処理(orElseやgetOrElse等)を最後に実行するのが一般的なパターン。

val dept: String =
  lookupByName("Joe").
  map(_.dept)
  filter(_ != "Accounting")
  getOrElse("Default Dept")

List[Option[A]]をOption[List[A]]に変換する(sequence関数)

def map2[A,B,C](a: Option[A], b: Option[B])(f: (A, B) => C): Option[C] =
  a flatMap (aa => b map (bb => f(aa, bb)))

def sequence[A](la: List[Option[A]]): Option[List[A]] =
  la.foldRight[Option[List[A]]](Some(Nil))((a,z) => map2(a,z)(_ :: _))

G[F[A]] -> F[G[A]] という変換(sequence関数)を、foldRightとmap2を使って実装する手法は、この書籍の練習問題で頻出する。イディオムとして覚えてしまって良さそう。

List[A] に A => Option[B] な無名関数fを再帰的に適用して Option[List[B]] を返す関数(traverse関数)

def traverse[A, B](a: List[A])(f: A => Option[B]): Option[List[B]] = a match {
  case Nil => Some(Nil)
  case h :: t => f(h) flatMap (hh => traverse(t)(f) map (hh :: _))
}

この場合、fがどこかでNoneを返すと、traverse関数の戻り値もNoneとなる。
sequenceとtraverseは、第12章の「トラバーサブルファンクタ」の節でも登場する。

for内包表記

map2関数の元のバージョン

def map2[A, B, C](a: Option[A], b: Option[B])(f: (A,B) => C): Option[C] =
  a flatMap (aa =>
    b map (bb => 
      f(aa, bb)
    )
  )

for内包表記で書き直す

def map2[A, B, C](a: Option[A], b: Option[B])(f: (A,B) => C): Option[C] =
  for {
    aa <- a
    bb <- b
  } yield f(aa, bb)

途中の呼び出しは全部flatMapに変換される。最後の呼び出しだけがmapに変換される。
for内包表記では、一番上の<-の右辺の型(この場合はOption)が、yieldで返された型(この場合はC)をくるむ型(Option)となるので、結果の型はOption[C]となる。
また、flatMapは引数の型を規定するので、Option[A]型の変数のflatMapに渡せるのは、A => Option[B]型の無名関数だけである。

for内包表記(もしくはflatMapやmap)の即時評価と遅延評価

List型やOption型のfor内包表記は「即時評価」だが、この後で登場するState型やFreeモナド等のfor内包表記は遅延評価である。(この言い方が正しいかどうかは微妙だが)

Eitherデータ型

Optionは、例外的な状況で何がうまくいかなかったのかを何も教えてくれない。エラーに関する情報が必要な場合はEitherデータ型を使用する。

sealed trait Either[+E, +A]
case class Left[+E](value: E) extends Either[E, Nothing]
case class Right[+A](value: A) extends Either[Nothing, A]

Option型の例で出てきたmean関数をEitherを使って書き直す

def mean(xs: IndexedSeq[Double]): Either[String, Double] =
  if (xs.isEmpty)
    Left("mean of empty list!")
  else
    Right(xs.sum / xs.length)

例外のスタックトレースが欲しい場合は下記のようにする。

def safeDiv(x: Int, y: Int): Either[Exception, Int] = 
  try Right(x / y)
  catch { case e: Exception => Left(e) }

第5章正格と遅延

正格：関数の引数が常に評価される
非正格：関数の引数の一つ以上を評価しないという選択が可能

例

def square(x: Double): Double = x * x

square関数は正格なので、square(41.0 + 1.0)と呼び出すと、計算済みの42.0という値が渡される
square(sys.error("failure"))のように呼び出すと、squareの本体に入る前にsys.errorが実行されるため、squareが何かをする間もなく例外が発生する。

false && { println("!!"); true }

この場合、標準出力には何も出力されない(printlnが実行されない)
&&を、引数を2つ取る関数(この場合は中置記法が使われているになっている)と考えてみる。
2つ目の引数を評価するのは1つ目の引数がtrueの場合のみなので、&&や||は非正格関数である。

val result = if (input.isEmpty) sys.error("empty input") else input

ifは、条件パラメータについては正格。trueとfalseの分岐に関しては非正格。

サンク

def if2[A](cond: Boolean, onTrue: () => A, onFalse: () => A): A =
  if (cond) onTrue() else onFalse()

val a = 1
if2(a < 22, () => println("a"), () => println("b"))

上記のように、評価されない形式の式を一般にサンク(thunk)という。
上記(引数を取らない関数を引数にとる)は非常によくあるケースなので、下記のように便利なシンタックスシュガー(糖衣構文)が用意されている

def if2[A](cond: Boolean, onTrue: => A, onFalse: => A): A =
  if (cond) onTrue else onFalse // ()が不要

if2(false, sys.error("fail"), 3)

これがいわゆるScalaの「名前渡し」構文である。() => Aの()の部分を省略したもの。
ちなみに、()を省略した「名前渡し」構文は、クラスのコンストラクタに対しては使用出来ない。この後出てくるStreamデータ型のConsデータコンストラクタで名前渡し構文が使用されていないのはそれが理由。

case class Cons[+A](h: () => A, t: () => Stream[A]) extends Stream[A]

lazyを使用して複数回の評価を回避する手法

def maybeTwice(b: Boolean, i: => Int) = if (b) i+i else 0
val x = maybeTwice(true, { println("hi"); 1+41 })
// hi
// hi
// x: Int = 84

iが2回呼び出されているので上記のように"hi"が2回出力されてしまっている。(printlnが2回実行されている)

def maybeTwice2(b: Boolean, i: => Int) = {
  lazy val j = i
  if (b) j+j else 0
}
val x = maybeTwice2(true, { println("hi"); 1+41 })
// hi
// x: Int = 84

"hi"が1回だけ出力されるようになる。
このように、lazyを使うことで、評価を遅延(最初に参照されるまで評価されない)させるという基本動作を変えない上で、評価された場合の結果をキャッシュしておくことが可能。

遅延リスト(Stream)とスマートコンストラクタ

trait Stream[+A] {
  def headOption: Option[A] = this match {
    case Empty => None
    case Cons(h, t) => Some(h())
  }
}
case object Empty extends Stream[Nothing]
case class Cons[+A](h: () => A, t: () => Stream[A]) extends Stream[A]
object Stream {
  def cons[A](hd: => A, tl: => Stream[A]): Stream[A] = {
    lazy val head = hd
    lazy val tail = tl
    Cons(() => head, () => tail) // この時点ではheadとtailはまだ評価されないので、hdとtlも評価されない。
  }
}

val s = Stream.cons({println("hi!"); 1}, Empty)
s.headOption
// hi!
// res1: Option[Int] = Some(1)
s.headOption
// res2: Option[Int] = Some(1)

"hi!"が一回だけしか出力されていない。(評価結果がキャッシュされている)
データコンストラクタに渡す引数をlazyを経由させることで評価結果をキャッシュさせる。上記のconsのような関数を「スマートコンストラクタ」と呼ぶ。
対応するデータコンストラクタの1文字目を小文字にしたものをスマートコンストラクタとして定義することが慣例らしい。

プログラムの記述と評価の切り分け

def foldRight[B](z: => B)(f: (A, => B) => B): B =
  this match {
    case Cons(h, t) => f(h(), t().foldRight(z)(f))
    case _ => z
  }

上記のfoldRight関数の無名関数fの第二引数は非正格なので、fが第二引数を評価しない限り、t().foldRight(z)(f)の部分は評価されないことに注意。
それを前提に、exists関数を実装してみる。

def exists(p: A => Boolean): Boolean = {
  this.foldRight(false)((a, b) => p(a) || b)

p(a)がfalseを返し続けている間は、bが評価されるのでfoldRightが再帰的に実行される。
p(a)がtrueを返すと、bが評価されないため、foldRightの再帰がそこで終了する。

中間ストリームをインスタンス化しない

trait Stream[+A] {
  def foldRight[B](z: => B)(f: (A, => B) => B): B =
    this match {
      case Cons(h,t) => f(h(), t().foldRight(z)(f))
      case _ => z
    }

  def map[B](f: A => B): Stream[B] =
    foldRight(empty[B])((h,t) => cons(f(h), t))

  def filter(f: A => Boolean): Stream[A] =
    foldRight(empty[A])((h,t) =>
      if (f(h)) cons(h, t)
      else t)
}
object Stream {
  def apply[A](as: A*): Stream[A] =
    if (as.isEmpty) empty
    else cons(as.head, apply(as.tail: _*))
}

Stream(1, 2, 3, 4).map(_ + 10).filter (_ % 2 == 0).toList
// 12と14が抽出される

上記の処理は「漸進的」に実行される。つまり、Stream(11, 12, 13, 14)のような中間ストリームが生成されない。
中間ストリームが生成されない理由は、Consの引数のhとtがサンクであることによるもの。(スマートコンストラクタが使われているかどうかはこの場合関係がない)
- Stream(1, 2, 3, 4)もStream(1, 2, 3, 4).map(_ + 10)もStream(1, 2, 3, 4).map(_ + 10).filter (_ % 2 == 0)も全てCons(<function0>,<function0>)を返す
- Stream(1, 2, 3, 4)が返すConsは当然apply関数が生成したもので、Stream(1, 2, 3, 4).map(_ + 10)が返すのはmap関数が生成したCons。当然のことながらどちらもhとtに渡された式の評価は実行されていない。
- toListやheadOptionが実行されると、末端のConsのhとtの評価が行われる。その評価が上に向かって遡っていくイメージと考えれば良いと思われる。
書籍の当該ページにはプログラムトレースが掲載されている。

無限ストリーム

val ones: Stream[Int] = Stream.cons(1, ones)

Cons(1, 自分自身) という構造なので、headとtailのうちtailを辿っていくとまた自分に戻るという無限リスト。

ones.take(5).toList
// List[Int] = List(1, 1, 1, 1, 1)
ones.forAll(_ != 1)
// これはスタックオーバーフローになる

第6章純粋関数型の状態

乱数を生成するデータ型

trait RNG {
  def nextInt: (Int, RNG)
}
case class SimpleRNG(seed: Long) extends RNG {
  def nextInt: (Int, RNG) = {
    val newSeed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL // &はビット論理積
    val nextRNG = SimpleRNG(newSeed)
    val n = (newSeed >>> 16).toInt // >>>は0埋め右バイナリシフト。nが新しい乱数
    (n, nextRNG)
  }
}

def nonNegativeInt(rng: RNG): (Int, RNG) = {
  val (i, r) = rng.nextInt
  (if (i < 0) -(i + 1) else i, r)

def double(rng: RNG): (Double, RNG) = {
  val (i, r) = nonNegativeInt(rng)
  (i / (Int.MaxValue.toDouble + 1), r)
}

def intDouble(rng: RNG): ((Int, Double), RNG) = {
  val (i, r1) = nonNegativeInt(rng)
  val (d, r2) = double(r1)
  ((i, d), r2)
}

nextIntは純粋関数である。(引数が同じなら結果も常に同じ)

状態の処理に適したAPI

上記のnextInt関数やdouble関数は、いずれもRNG => (A, RNG)というシグネチャである。
この種の関数は、RNGの状態を遷移させることから「状態アクション」または「状態遷移」と呼ばれる。
これらの状態アクションは「コンビネータ」と呼ばれる高階関数(この後で定義していく)を使って組み合わせることが出来る。
- これ以降、「コンビネータ」という用語が頻出するが、要するに「代数的データ型に対して定義された一連の高階関数のこと」である。

状態アクションデータ型の定義

type Rand[+A] = RNG => (A, RNG)

nextInt関数等をこの新しい型で保持することが可能になる
- 下記はval int: Rand[Int] = rng => rng.nextIntの短縮形である。

val int: Rand[Int] = _.nextInt

コンビネータの定義
- 関数型ライブラリで「unit」という用語が出てきたら、「1つの値をラッピングする」と考えてよいらしい。(「lift」とかも同様な意味と思われる)

def unit[A](a: A): Rand[A] =
  rng => (a, rng)

def map[A, B](r: Rand[A])(f: A => B): Rand[B] =
  rng => {
    val (a, r2) = r(rng)
    (f(a), r2)
  }

def map2[A, B, C](ra: Rand[A], rb: Rand[B])(f: (A, B) => C): Rand[C] = {
  rng => {
    val (a, r1) = ra(rng)
    val (b, r2) = rb(r1)
    (f(a, b), r2)
  }
}

def flatMap[A, B](f: Rand[A])(g: A => Rand[B]): Rand[B] = {
  rng => {
    val (a, r2) = f(rng)
    g(a)(r2)
  }
}

使用例

val u = unit(1)  // Rand[Int]型を生成して返す
val (i, r) = u(SimpleRNG(42)) // (1, rng)が返される。

def nonNegativeEven: Rand[Int] =
  map(nonNegativeInt)(i => i - i % 2)

def both[A, B](ra: Rand[A], rb: Rand[B]): Rand[(A, B)] = {
  map2(ra, rb)((_, _))
}

def intDouble: Rand[(Int, Double)] = 
  both(nonNegativeInt, double)

状態アクションデータ型の一般化

RNG => (A, RNG)をS => (A, S)として一般化する

// typeとして定義する場合
type State[S, +A] = S => (A, S)

// case classとして定義する場合
case class State[S, +A](run: S => (A, S))

case class版の主要な関数の実装は下記のようになる

case class State[S, +A](run: S => (A, S)) {
  def map[B](f: A => B): State[S, B] =
    flatMap(a => unit(f(a)))
  def map2[B,C](sb: State[S, B])(f: (A, B) => C): State[S, C] =
    flatMap(a => sb.map(b => f(a, b)))
  def flatMap[B](f: A => State[S, B]): State[S, B] = State(s => {
    val (a, s1) = run(s)
    f(a).run(s1)
  })
}

object State {
  def unit[S, A](a: A): State[S, A] =
    State(s => (a, s))
}

case class版はCatsのKleisliとよく似ているが、Kleisliはもう一つ型パラメータが多く、final case class Kleisli[M[_], A, B](run: A => M[B])のように定義されている。

第7章純粋関数型の並列処理

色々記述されているが、とりあえず下記のようなデータ型と関数の組み合わせが一旦提示される。
- こちらはスレッドプールのサイズが1の場合にデッドロックが発生する。章の後半で改善版が提示される。

import java.util.concurrent._

object Par {
  type Par[A] = ExecutorService => Future[A]

  def run[A](s: ExecutorService)(a: Par[A]): Future[A] = a(s)

  def unit[A](a: A): Par[A] = (es: ExecutorService) => UnitFuture(a)

  private case class UnitFuture[A](get: A) extends Future[A] {
    def isDone = true
    def get(timeout: Long, units: TimeUnit) = get
    def isCancelled = false
    def cancel(evenIfRunning: Boolean): Boolean = false
  }

  def map2[A,B,C](a: Par[A], b: Par[B])(f: (A,B) => C): Par[C] =
    (es: ExecutorService) => {
      val af = a(es)
      val bf = b(es)
      UnitFuture(f(af.get, bf.get))
    }

  def fork[A](a: => Par[A]): Par[A] = 
    es => es.submit(new Callable[A] {
      def call = a(es).get
    })

  def lazyUnit[A](a: => A): Par[A] = fork(unit(a))

  def asyncF[A,B](f: A => B): A => Par[B] =
    a => lazyUnit(f(a))

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

  def equal[A](e: ExecutorService)(p: Par[A], p2: Par[A]): Boolean =
    p(e).get == p2(e).get
}

このParというデータ型は、Parという名称ではあるものの、並行処理を行うかどうか(つまりメインスレッドから別の論理スレッドをフォークするかどうか)はプログラマ側に委ねられている。
- forkメソッドを経由しない場合、論理スレッドはフォークされない。例えばunitメソッドは正格なので引数が即時評価される。lazyUnitメソッドは引数が非正格かつforkメソッドを経由するので遅延評価かつ論理スレッドがフォークされる。
- 本文内で「並列化のグローバルポリシー」という言葉が使用されているが、要するに「論理スレッドをフォークするかどうかの方針を全関数を通じて統一してしまうとライブラリとして使いづらくなる」のでプログラマ側に委ねるという意味と思われる。
また、説明の便宜上のためと思われるが、scala.concurrent.Futureではなくjava.util.concurrent.Futureを使用している。
- scala.concurrent.Futureだと、既にノンブロッキング処理とかが実装されているためここで説明したい内容に適さないからだと思われる。
UnitFutureクラスが必要なのは、java.util.concurrent.Futureが単なるインターフェイスなので実装が必要なため。(5つの関数に実装を提供する必要がある)
- 微妙にややこしいが、ExecutorService.submitで返されるFutureのgetメソッドと、UnitFutureのgetは別物である。
  - Futureのgetメソッドは、論理スレッドの結果が返されるまでメインスレッドの処理をブロック。UnitFutureのgetは評価済みの値を返すだけ。
- 同じインターフェイスなので、論理スレッドをフォークしているかどうかに関わらず、どちらもgetで値を取得出来るということになる。
java.util.concurrent.Futureのインターフェイスは純粋関数型ではない(InterruptedException等の例外をスローする可能性があるため)が、上記のAPIは純粋関数型である。これを「作用であって副作用でない」というらしい。
- 副作用を発生させるjava.util.concurrent.Futureインターフェイスを扱ってはいるが、UnitFutureは例外を発生させない(trueやfalse等の定数値を返しているだけ)。
- ただし、forkで返されたFutureのgetメソッドは、定義通り例外をスローする可能性があるので、その処理が上記APIに含まれていれば上記APIは純粋関数型ではない。
  - その部分は分離されていて、Par.run(es)(p).getのように別の層で呼び出すことになるので、このAPI自体は純粋関数型であるということになるようである。

使用例

分割統治アルゴリズムでInt型のシーケンスの合計値を算出するアルゴリズム

def sum(ints: IndexedSeq[Int]): Int =
  if (ints.size <= 1)
    ints.headOption getOrElse 0
  else {
    val (l, r) = ints.splitAt(ints.length/2)
    sum(l) + sum(r)
  }

上記をParを使って書き換える

def sum(ints: IndexedSeq[Int]): Par[Int] =
  if (ints.size <= 1)
    Par.unit(ints.headOption getOrElse 0)
  else {
    val (l, r) = ints.splitAt(ints.length/2)
    Par.map2(Par.fork(sum(l)), Par.fork(rum(r)))(_ + _)
  }

// 下記のように使う
val p = sum(IndexedSeq(1,2,3))
val result: Int = Par.run(es)(p).get // ここは例外(つまり副作用)が発生する可能性がある

中置構文

Par[A]はデータ型ではなく型エイリアスにすぎないため、通常はp.map(f)のような中置構文は使えない。(Par.map(p)(f)のように書く必要がある)
上記を、暗黙変換を使って型に中置構文を追加するという方法がある。

import language.implicitConversions

implicit def toParOps[A](p: Par[A]): ParOps[A] = new ParOps(p)

class ParOps[A](p: Par[A]) {
  def map[B](f: A => B): Par[B] = Par.map(p)(f)
  ...
}

これを使うと、ParOps <=> Parの相互変換をサポートしてくれる。(p.map(f)のような中置構文が使えるようになる)
- が、中置構文をサポートしたい関数を全てParOpsに記載する必要があるということになるので、自分でライブラリを作るならParのような型はtraitとかで定義しておいた方が良さそうな印象。

デッドロック

スレッドプールのサイズが1の場合、下記のコードではデッドロックが発生する。

val a = lazyUnit(42 + 1)
val S = Executors.newFixedThreadPool(1)
println(Par.equal(S)(a, fork(a)))

aはlazyUnitで生成されているので内部でforkが呼び出されている。
- さらに、equalに対して2つ目の引数がforkで囲まれた状態で渡されている。
  - ネストされたforkでは、内部でCallableが2回生成されるが、スレッドプールのサイズが上記では1なので、
    - 親が一つスレッドを取得した状態で子のスレッドを実行する。
    - 親がスレッドを解放するのは、子がgetの戻り値を返した場合であるが、java.util.concurrent.Futureのgetは呼び出し側のスレッドをブロックする。
      - この実装においては、forkが返すFutureはUnitFutureではなくjava.util.concurrent.Futureであることに注意。(ここはちょっとややこしい)
    - 子はスレッドを獲得しようとするが、親が獲得済みなので獲得出来ない。
- これによりデッドロックが発生する。
固定サイズ(例えば1)のスレッドプールでもデッドロックが発生しないようにParの実装を変更する必要がある。それが次の節。

アクターを使ったノンブロッキング実装

考え方はシンプル。ParをFutureに変換してそこからjava.util.concurrent.Future.getを使って値を取得するのではなく(それだと親子関係のスレッドが生成された際に、呼び出し側スレッドがブロックされることによりデッドロックが発生してしまう)、結果が準備出来たときに呼び出されるコールバックを登録すればよい。
- scala.concurrent.Futureには既にこの機能が実装されているが、下記ではそれを使わず、専用のFutureトレイトを新たに作成する。
下記で登場する「カウントダウンラッチ」に関してはこちらを参照。
ちなみに下記の、この書籍で独自に実装されているActorは、scalazのActorをより簡易にしたものとのこと。(AkkaのActorと同様なものと考えてよいと思われる)
- 論理スレッドの生成にはExecutorServiceが使用されている
ブロッキングバージョンから大きく変更になったのは下記。
- p(es).getで値を取得するのではなく、p(es) { a => ... }のようにコールバックを登録する方式になった。
  - 下記のp(es)(cb)とかp(es) {...}とかのコードはFuture.apply(cb)に展開して考えると読みやすい。
- forkメソッド(もしくはevalメソッド)で論理スレッドがフォークされるが、java.util.concurrent.Future.getメソッドが使用されなくなったので、呼び出し側スレッドがブロックされなくなった。
  - つまり、fork関数がネストしていても、外側のスレッドは内側のスレッドの完了を待たずに終了するようになったので、デッドロックが発生しなくなった。
    - scalaの通常のFutureを使用する場合に、論理スレッドをフォークしても、Await.Resultとかのブロッキングの発生するメソッドを使用しなければ、論理スレッドの終了を待たずに呼び出し側のスレッドが終了するのと同じことである。
    - 旧バージョンの場合、メインスレッドからフォークされた一つ目の論理スレッドのCallable内のjava.util.concurrent.Future.getが、結果を待つブロッキング関数だったことが問題だったわけである。

import java.util.concurrent.{Callable, CountDownLatch, ExecutorService}
import java.util.concurrent.atomic.AtomicReference

final class Actor[A](strategy: Strategy)(handler: A => Unit, onError: Throwable => Unit = throw(_)) {
  self =>
  ...
}

object Nonblocking {

  trait Future[+A] {
    def apply(k: A => Unit): Unit
  }

  type Par[+A] = ExecutorService => Future[A]

  object Par {

    def run[A](es: ExecutorService)(p: Par[A]): A = {
      val ref = new java.util.concurrent.atomic.AtomicReference[A] // mutableでスレッドセーフなreference。結果をストアするために使用される。
      val latch = new CountDownLatch(1) // カウントダウンラッチ。デクリメントされた際に、ref変数に値が設定されたことを示す。
      p(es) { a => ref.set(a); latch.countDown } // 非同期でref変数に値を設定して、カウントダウンラッチをデクリメントする。
      latch.await // ラッチのcountDownメソッドが呼び出されるまでメインスレッドをブロックする。
      ref.get // コードがここに達したらref変数に値が設定されているのでgetで値を取得出来る。
    }

    def unit[A](a: A): Par[A] =
      es => new Future[A] {
        def apply(cb: A => Unit): Unit =
          cb(a)
      }

    def fork[A](a: => Par[A]): Par[A] =
      es => new Future[A] {
        def apply(cb: A => Unit): Unit =
          eval(es)(a(es)(cb))
      }

    def eval(es: ExecutorService)(r: => Unit): Unit =
      es.submit(new Callable[Unit] { def call = r })

    def map2[A,B,C](p: Par[A], p2: Par[B])(f: (A,B) => C): Par[C] =
      es => new Future[C] {
        def apply(cb: C => Unit): Unit = {
          var ar: Option[A] = None
          var br: Option[B] = None
          // this implementation is a little too liberal in forking of threads -
          // it forks a new logical thread for the actor and for stack-safety,
          // forks evaluation of the callback `cb`
          val combiner = Actor[Either[A,B]](es) {
            case Left(a) =>
              if (br.isDefined) eval(es)(cb(f(a,br.get)))
              else ar = Some(a)
            case Right(b) =>
              if (ar.isDefined) eval(es)(cb(f(ar.get,b)))
              else br = Some(b)
          }
          p(es)(a => combiner ! Left(a))
          p2(es)(b => combiner ! Right(b))
        }
      }

    // specialized version of `map`
    def map[A,B](p: Par[A])(f: A => B): Par[B] =
      es => new Future[B] {
        def apply(cb: B => Unit): Unit =
          p(es)(a => eval(es) { cb(f(a)) })
      }
  }
}

第8章プロパティベースのテスト

ScalaCheckのような、プロパティベースのテストライブラリの作成方法が解説される。
「プロパティベースのテスト」とは、「入力と出力の関係性や法則(性質)を示すステートメント」に対し、「大量の入力を自動的に生成」して、そのステートメント(性質)の「総当りテスト」を行うようなテストのこと、と考えてよいらしい。
- 関数型ライブラリでは、代数的データ型に対して定義された各コンビネータ(高階関数)の法則性を自動的にチェック出来る仕組みが必要なため、これに関する解説の章が設けられているようである。
- 下記の記事が参考になる。
  - ScalaCheck をつかって Java の性質テスト (Property-based Testing) をしてみる | Futurismo
  - Abstractivate: Property-based testing: what is it?
ScalaCheckの具体的なコードは下記。

val intList = Gen.listOf(Gen.choose(0, 100))
val prop = 
  forAll(intList)(ns => ns.reverse.reverse == ns) &&
  forAll(intList)(ns => ns.headOption == ns.reverse.lastOption)
val failingProp = forAll(intList)(ns => ns.reverse == ns)

prop.check
// + OK, passed 100 tests.

failingProp.check
// ! Falsified after 2 passed tests.
// > ARG_0: List("0", "1")
// > ARG_0_ORIGINAL: List("71", "86")

上記のpropの例であれば、forAll(intList)(ns => ns.reverse.reverse == ns)の部分が丸ごと「ステートメント(性質)」ということになると思われる。
- この場合は「1から100までのランダムな整数のリストに対して、そのリストを2回リバースしたリストが元のリストと等しい」という性質を示している。
テストを実際に実行するPropと、テストデータを生成するGenの、2つのでデータ型が必要となる。

Genの定義

case class Gen[+A](sample: State[RNG,A]) {
  def map[B](f: A => B): Gen[B] =
    Gen(sample.map(f))

  def map2[B,C](g: Gen[B])(f: (A,B) => C): Gen[C] =
    Gen(sample.map2(g.sample)(f))

  def flatMap[B](f: A => Gen[B]): Gen[B] =
    Gen(sample.flatMap(a => f(a).sample))

  def listOfN(size: Int): Gen[List[A]] =
    Gen.listOfN(size, this)

  /* A version of `listOfN` that generates the size to use dynamically. */
  def listOfN(size: Gen[Int]): Gen[List[A]] =
    size flatMap (n => this.listOfN(n))

  def listOf: SGen[List[A]] = Gen.listOf(this)
  def listOf1: SGen[List[A]] = Gen.listOf1(this)

  ...
}

object Gen {
  def unit[A](a: => A): Gen[A] =
    Gen(State.unit(a))

  val boolean: Gen[Boolean] =
    Gen(State(RNG.boolean))

  def choose(start: Int, stopExclusive: Int): Gen[Int] =
    Gen(State(RNG.nonNegativeInt).map(n => start + n % (stopExclusive-start)))

  def listOfN[A](n: Int, g: Gen[A]): Gen[List[A]] =
    Gen(State.sequence(List.fill(n)(g.sample)))

  def listOf[A](g: Gen[A]): SGen[List[A]] =
    SGen(n => g.listOfN(n))

  ...
}

case class SGen[+A](g: Int => Gen[A]) {
  def apply(n: Int): Gen[A] = g(n)
  ...
}

Genは、第6章で作成したState型とRNG型を使った「ランダムに値を生成する状態アクションデータ型」のラッパーと考えればよい。(Genケースクラスははsample: State[RNG,A]を引数にとる)
- Genには、State[RNG,A]を使用して、整数や実数や文字列や真偽値をランダムに返すための関数、整数や実数のランダムなリスト、それらを結合するための関数等が定義されている。
- Genを、Propを使わずに単体で実行するならば下記のようになる。

val gen = Gen.choose(3, 21)
val (i1, rng1) = gen.sample.run(SimpleRNG(1000)) // SimpleRNGも第6章に登場。
val (i2, rng2) = gen.sample.run(rng1)
// 3から21までのランダムな整数が返される。

val genList = gen.listOfN(10)
val (l1, rng3) = genList.sample.run(rng2)
// 3から21までのランダムな整数の、要素数10のリストが返される。

SGenは、例えば「ランダムな整数のリスト」の要素数を、この後登場するProp型のforAll関数内で任意に決定したい場合(つまり要素数の決定を後回しにしたい場合)の、Genのラッパーである。
- この章の「テストケースの最小化」の節で、テストケースを最小化するための「縮小」と「サイズに基づく生成」の2種類が紹介されているが、Prop型はforAll関数内で「サイズに基づく生成」により、最小のテストケースの特定を行っている。
  - 要するに、「要素数10のリスト」と「要素数の100のリスト」ならば、「要素数10のリスト」でエラーが発見された方が、「どういう条件だとエラーが発生するのか」という情報を、テストライブラリ使用者側が発見しやすくなるので、それをサポートする機能を提供しているということである。
  - Prop型のforAll関数にはいくつかのバージョンがあるが、Stream.from(0).take((n min max) + 1).map(i => forAll(g(i))(f))という箇所が、SGenを使って「サイズに基づく生成」を行っている箇所である。n+1からmax+1までのサイズのテストケースが生成される。(返される型はリストとは限らないがコレクション型と考えて良い)
    - Genを使うと、forAll呼び出し前にリスト等のサイズを決定しておく必要があるが、SGenを使うと、forAll内でリスト等のサイズを決定出来る。(「サイズに基づく生成」が行える)

Propの定義

case class Prop(run: (MaxSize,TestCases,RNG) => Result) {
  def &&(p: Prop) = Prop {
    (max,n,rng) => run(max,n,rng) match {
      case Passed | Proved => p.run(max, n, rng)
      case x => x
    }
  }
  ...
}

object Prop {
  type SuccessCount = Int
  type TestCases = Int
  type MaxSize = Int
  type FailedCase = String

  sealed trait Result {
    def isFalsified: Boolean
  }
  case object Passed extends Result {
    def isFalsified = false
  }
  case class Falsified(failure: FailedCase,
                       successes: SuccessCount) extends Result {
    def isFalsified = true
  }
  case object Proved extends Result {
    def isFalsified = false
  }

  def apply(f: (TestCases,RNG) => Result): Prop =
    Prop { (_,n,rng) => f(n,rng) }

  def randomStream[A](g: Gen[A])(rng: RNG): Stream[A] =
    Stream.unfold(rng)(rng => Some(g.sample.run(rng)))

  def forAll[A](as: Gen[A])(f: A => Boolean): Prop = Prop {
    (n,rng) => randomStream(as)(rng).zip(Stream.from(0)).take(n).map {
      case (a, i) => try {
        if (f(a)) Passed else Falsified(a.toString, i)
      } catch { case e: Exception => Falsified(buildMsg(a, e), i) }
    }.find(_.isFalsified).getOrElse(Passed)
  }

  def forAll[A](g: SGen[A])(f: A => Boolean): Prop =
    forAll(g(_))(f)

  def forAll[A](g: Int => Gen[A])(f: A => Boolean): Prop = Prop {
    (max,n,rng) =>
      val casesPerSize = (n - 1) / max + 1
      val props: Stream[Prop] =
        Stream.from(0).take((n min max) + 1).map(i => forAll(g(i))(f))
      val prop: Prop =
        props.map(p => Prop { (max, n, rng) =>
          p.run(max, casesPerSize, rng)
        }).toList.reduce(_ && _)
      prop.run(max,n,rng)
  }

  def run(p: Prop,
          maxSize: Int = 100,
          testCases: Int = 100,
          rng: RNG = RNG.Simple(System.currentTimeMillis)): Unit =
    p.run(maxSize, testCases, rng) match {
      case Falsified(msg, n) =>
        println(s"! Falsified after $n passed tests:\n $msg")
      case Passed =>
        println(s"+ OK, passed $testCases tests.")
      case Proved =>
        println(s"+ OK, proved property.")
    }

  val ES: ExecutorService = Executors.newCachedThreadPool

  def check(p: => Boolean): Prop = Prop { (_, _, _) =>
    if (p) Passed else Falsified("()", 0)
  }

  ...
}

先に例として出されたprop.checkではなくProp.run(prop)のようにしてテストを実行する方式に変更されている。
- runの引数であるrngのデフォルト値がRNG.Simple(System.currentTimeMillis)のように指定されているため、明示的に指定しない限り、rngを使用した乱数の生成は、毎回異なるシード値で行われる。
type SuccessCount = Int等の定義は単なる「可読性向上」のためのtypeエイリアス指定なので気にしないで良い。
一つ目のforAll関数から呼び出されているrandomStream関数のg.sample.run(rng))で、GenでラップされたState[RNG,A]のrunが実行され、ランダム値が返される。
- randomStream関数内で使用されているStream.unfoldは下記のようなシグネチャ。「逆畳み込み」関数である。
- (A, S)という形式のタプルを使用しているため、State[RNG,A]のような状態アクションデータ型に都合が良いというか、むしろそのために作られている関数と考えて良さそう。

def unfold[A, S](z: S)(f: S => Option[(A, S)]): Stream[A] =
  f(z) match {
    case Some((h,s)) => cons(h, unfold(s)(f))
    case None => empty
  }

// 典型的な使い方としては下記のような感じ(Noneが終了条件。Noneを返さない場合は無限ストリームとなる)
Stream.unfold(10)(s => if (s == 0) None else Some(s, s - 1)).take(5).toList
// List[Int] = List(10, 9, 8, 7, 6)

randomStream関数は、引数で受け取ったrngを使って状態アクションデータ型を再帰的に呼び出して乱数を生成するStreamを返す。(Streamなので当然遅延評価である)
runを、第1引数のみで実行すると、maxSizeとtestCasesはどちらも100である。この状態で、3番目の方のforAllが実行されると、
- Stream.from(0).take((n min max) + 1).map(i => forAll(g(i))(f))の箇所では、mapに渡されるiは0から101の値となるので、この値を使って1番目のforAllが呼び出されると、要素数0から101までのランダム値リストを生成するStreamを使ったテストケースが生成される。
  - なぜStream.from(1)ではなくStream.from(0)なのかはよく分からないが、要素数0のStreamもテストする必要があるからということだと思われる。
- casesPerSize変数はこの場合1になるため、p.run(max, casesPerSize, rng)で1番目のforAll関数で返されたPropが実行される際に渡されるnの値は1となる。この値が各テストの実行回数となるので、この場合は「要素数0から101までのランダム値リストを生成するStreamを使ったテスト」はそれぞれ1回ずつ実行されるということになる。
  - 各テストの実行回数を2回にしたければ、Prop.runを実行する際のtestCases変数の値を101等にする必要がある。10回実行したいなら901等の値を設定する。(この方式が良いのかどうかはいまいち良く分からない)
- ちなみに3番目のforAll関数内のp.run(max, casesPerSize, rng)で実行される1番目のforAll関数は、第1引数で渡されているmax変数を無視するので注意。(ここはかなり分かりにくい。Propオブジェクトのapply関数を参照)

第9章パーサーコンビネータ

この章は理解が非常に難しい。
- JSONをパースするためのアルゴリズムがそもそも難しい。
- 途中まで実装がない状態なので「これ具体的にどう動作するんだろう？」というのがイメージ出来ない。(slice関数等の存在理由も謎)
- 「代数的設計」という方法を説明するために、抽象度の高い手法(下記の場合ParserとParseErrorはtrait等ではなく単なる型パラメータ)で設計と実装が行われていくのだが、「具体性が高い状態 -> 抽象化」という手順であれば理解し易いものの、最初から抽象度が高いままなので、「なぜそうする必要があるのか」がピンとこない。
自分でパーサーを作るつもりでなければ、「時間がたっぷりある時に復習」ということで良いかなと思うので後回し。実行する際は下記のようになる。

val c = 'X'
run(char(c))(c.toString)
// Right(c)

val s = 'abc'
run(string(s))(s)
// Right(s)

trait Parsers[Parser[+_]] { self => // so inner classes may call methods of trait
  def run[A](p: Parser[A])(input: String): Either[ParseError,A]

  implicit def string(s: String): Parser[String]
  implicit def operators[A](p: Parser[A]) = ParserOps[A](p)
  implicit def asStringParser[A](a: A)(implicit f: A => Parser[String]): ParserOps[String] = ParserOps(f(a))
  implicit def regex(r: Regex): Parser[String]

  def char(c: Char): Parser[Char] =
    string(c.toString) map (_.charAt(0))

  def slice[A](p: Parser[A]): Parser[String]

  def attempt[A](p: Parser[A]): Parser[A]

  def token[A](p: Parser[A]): Parser[A] =
    attempt(p) <* whitespace

  def map2[A,B,C](p: Parser[A], p2: => Parser[B])(f: (A,B) => C): Parser[C] =
    for { a <- p; b <- p2 } yield f(a,b)

  def skipL[B](p: Parser[Any], p2: => Parser[B]): Parser[B] =
    map2(slice(p), p2)((_,b) => b)

  def skipR[A](p: Parser[A], p2: => Parser[Any]): Parser[A] =
    map2(p, slice(p2))((a,b) => a)

  def root[A](p: Parser[A]): Parser[A] =
    p <* eof

  def surround[A](start: Parser[Any], stop: Parser[Any])(p: => Parser[A]) =
    start *> p <* stop

  def whitespace: Parser[String] = "\\s*".r

  case class ParserOps[A](p: Parser[A]) {
    def |[B>:A](p2: => Parser[B]): Parser[B] = self.or(p,p2) // use `self` to explicitly disambiguate reference to the `or` method on the `trait`
    def or[B>:A](p2: => Parser[B]): Parser[B] = self.or(p,p2)

    def *>[B](p2: => Parser[B]) = self.skipL(p, p2)
    def <*(p2: => Parser[Any]) = self.skipR(p, p2)
    def token = self.token(p)
    ...
  }
}

case class Location(input: String, offset: Int = 0) {

  lazy val line = input.slice(0,offset+1).count(_ == '\n') + 1
  lazy val col = input.slice(0,offset+1).lastIndexOf('\n') match {
    case -1 => offset + 1
    case lineStart => offset - lineStart
  }
  ...
}

case class ParseError(stack: List[(Location,String)] = List()) {
  ...
}

trait JSON

object JSON {
  case object JNull extends JSON
  case class JNumber(get: Double) extends JSON
  case class JString(get: String) extends JSON
  case class JBool(get: Boolean) extends JSON
  case class JArray(get: IndexedSeq[JSON]) extends JSON
  case class JObject(get: Map[String, JSON]) extends JSON

  def jsonParser[Parser[+_]](P: Parsers[Parser]): Parser[JSON] = {
    // we'll hide the string implicit conversion and promote strings to tokens instead
    // this is a bit nicer than having to write token everywhere
    import P.{string => _, _}
    implicit def tok(s: String) = token(P.string(s))

    def array = surround("[","]")(
      value sep "," map (vs => JArray(vs.toIndexedSeq))) scope "array"
    def obj = surround("{","}")(
      keyval sep "," map (kvs => JObject(kvs.toMap))) scope "object"
    def keyval = escapedQuoted ** (":" *> value)
    def lit = scope("literal") {
      "null".as(JNull) |
      double.map(JNumber(_)) |
      escapedQuoted.map(JString(_)) |
      "true".as(JBool(true)) |
      "false".as(JBool(false))
    }
    def value: Parser[JSON] = lit | obj | array
    root(whitespace *> (obj | array))
  }
}

object ReferenceTypes {
  type Parser[+A] = ParseState => Result[A]
}

object Reference extends Parsers[Parser] {
  def run[A](p: Parser[A])(s: String): Either[ParseError,A] = {
    val s0 = ParseState(Location(s))
    p(s0).extract
  }
  ...
}

型クラスのインスタンスに対する命名の慣例

jsonParser関数の引数の引数Pは小文字ではなく大文字になっている。この方式はScalaのStyle Guideには明記されていないが、ScalazやCatsにおいて「型クラスのインスタンス」に対して用いられる慣例のようである。
- Type class instance naming conventions · Issue #293 · typelevel/cats
  - 上記の議論を見る限り、この慣例が完全に受け入れられているというわけでもないようである。
- 「型クラス」に関しては下記で説明されている。
  - Cats
    - 上記でもimplicit A: Monoid[A]のように、大文字1文字の慣例が使用されている。
    - implicit eva: A <:< Monoid[A]の場合は、型クラスではなく「Aに対する型制約」なので大文字始まりではない。

「Scala関数型デザイン&プログラミング」を13章まで学習して練習問題を7割ほど消化したので要約＆振り返ってみました。

第1章 関数型プログラミングとは