2019-01-10 (Thu) · 1547 words

Scala

関数型プログラミングにおける副作用の除去は、結果型に副作用の元となるデータを返す入力Aに対する出力Bを返す関数 f: A => B は、内部・外部プロセスの変化に影響されない（＝副作用がない） buyCoffeの例では、請求処理という副作用を出力から排除すること

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

参照透過性

同じ条件を与えれば必ず同じ結果が得られる
他のいかなる機能の結果にも影響を与えない
関数の結果型に従い、実行する全てのことがその戻り値によって表されるという不変条件
プログラムによる等式推論(equational reasoning)が可能

def add1(x: Int, y: Int): Int = x + y

var x: Int = 1
def add2(y: Int): Int = x + y

参照透過性の確認フロー

例１

val x = "Hello World"
val r1 = x.reverse
// dlroW olleH
val r2 = x.reverse
// dlroW olleH

r1、r2は同じ
xをxが参照している式（その定義）と置き換える val r1 = "Hello World".reverse // dlroW olleH val r2 = "Hello World".reverse // dlroW olleH
r1、r2は同じ
置き換えても結果に影響を与えない

例２

val x = new StringBuilder("Hello")
val y = x.append(" World")
val r1 = y.toString
// Hello World
val r2 = y.toString
// Hello World

r1、r2は同じ
yをyが参照している式（その定義）と置き換える val x = new StringBuilder("Hello") val r1 = x.append(" World"").toString // Hello World val r2 = x.append(" World"").toString // Hello World World

unzip

reduce

List.fill

単相関数(monomorphic function)

１つの型のデータだけをを操作する関数

多相関数(polymorphic function)

総称関数(generic function)とも呼ばれる

関数リテラル

val f2 = (a: Int)

高階関数パラメータ名

引数に関数をとる関数
結果型を関数とする関数
f,g,hのような名称にするのが一般的

末尾再帰のオーバーライド

サブクラスで末尾再帰のメソッドをオーバーライドしようとするとコンパイルエラー
private final をつける http://www.ne.jp/asahi/hishidama/home/tech/scala/annotation/tailrec.html

関数型データ構造の定義

データコンストラクタ

反変（contravariant）

狭い型から、広い型へ変換

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

代数的データ型

algebraic data type
1つ以上のデータコンストラクタによって定義されるデータ型
コンストラクタは0個以上の引数を受け取る
データ型がそのデータコンストラクタの和である
各データコンストラクタがその引数の積である
分類として以下の3つがある
- 列挙型
- 直積型
- 直和型

列挙型

多言語のenumに該当
case objectとEnumerationの2種類がる
case objectを使う
- Enumerationは、パターンマッチの記述漏れチェックが自動で実行されないため -

直積型

直和型

3-3

def foldRight[A, B](as: List[A], z: B)(f: (A, B) => B): B = as match {
  case Nil => z
  case Cons(x, xs) => f(x, foldRight(xs, z)(f))
}
def sum2(ns: List[Int]): Int = foldRight(ns, 0)(_ + _)

// Program Trace
foldRight(List(1,2,3,4,5), 0)(_+_)
foldRight(Cons(1, Cons(2, Cons(3, Cons(4, Cons(5, 0))))))(_ + _)
f(1 + foldRight(Cons(2, Cons(3, Cons(4, Cons(5, 0))))))(_ + _)
f(1 + f(2 + foldRight(Cons(3, Cons(4, Cons(5, 0))))))(_ + _)
f(1 + f(2 + f(3 + foldRight(Cons(4, Cons(5, 0))))))(_ + _)
f(1 + f(2 + f(3 + f(4 + foldRight(Cons(5, 0))))))(_ + _)
f(1 + f(2 + f(3 + f(4 + f(5 + 0)))))(_ + _)
f(1 + f(2 + f(3 + f(4 + 5))))(_ + _)
f(1 + f(2 + f(3 + 9)))(_ + _)
f(1 + f(2 + 12))(_ + _)
f(1 + 14)(_ + _)
15

// Program Trace
foldRight(List(1,2,3,4,5), Nil: List[Int])(Cons(_,_))
foldRight(Cons(1, Cons(2, Cons(3, Cons(4, Cons(5, Nil: List[Int]))))))(Cons(_,_))
f(1, foldRight(Cons(2, Cons(3, Cons(4, Cons(5, Nil: List[Int]))))))(Cons(_,_))
f(1, f(2, foldRight(Cons(3, Cons(4, Cons(5, Nil: List[Int]))))))(Cons(_,_))
f(1, f(2, f(3, foldRight(Cons(4, Cons(5, Nil: List[Int]))))))(Cons(_,_))
f(1, f(2, f(3, f(4, foldRight(Cons(5, Nil: List[Int]))))))(Cons(_,_))
f(1, f(2, f(3, f(4, f(5, Nil: List[Int])))))(Cons(_,_))
f(1, f(2, f(3, f(4, Cons(5, Nil: List[Int])))))(Cons(_,_))
f(1, f(2, f(3, Cons(4, Cons(5, Nil: List[Int])))))(Cons(_,_))
f(1, f(2, Cons(3, Cons(4, Cons(5, Nil: List[Int])))))(Cons(_,_))
f(1, Cons(2, Cons(3, Cons(4, Cons(5, Nil: List[Int])))))(Cons(_,_))
Cons(1, Cons(2, Cons3, Cons(4, Cons(5, Nil: List[Int]))))

Exercise 10

def foldLeft[A, B](as: List[A], b: B)(f: (B, A) => B): B = as match {
  case Nil => b
  case Cons(a, xs) => foldLeft(xs, f(b, a))(f)
}

// Program Trace
foldLeft(List(1,2,3,4,5), 0)(_+_)
foldLeft(Cons(1, Cons(2, Cons(3, Cons(4, Cons(5, Nil))))), 0)(_+_)
foldLeft(Cons(2, Cons(3, Cons(4, Cons(5, Nil))))), 0+1)(_+_)
foldLeft(Cons(3, Cons(4, Cons(5, Nil))), 1+2)(_+_)
foldLeft(Cons(4, Cons(5, Nil)), 3+3)(_+_)
foldLeft(Cons(5, Nil), 6+4)(_+_)
10+5

Exercise 12

def reverse[A](l: List[A]): List[A] =
  foldLeft(l, List[A]())((b, a) => Cons(a, b))

// Program Trace
reverse(List(1,2,3,4,5))
foldLeft(List(1,2,3,4,5), List())((b, a) => Cons(a, b))
foldLeft(Cons(1, Cons(2, Cons(3, Cons(4, Cons(5, Nil)))), List())((b, a) => Cons(a, b))
foldLeft(Cons(2, Cons(3, Cons(4, Cons(5, Nil)))), Cons(1, Nil))((b, a) => Cons(a, b))
foldLeft(Cons(3, Cons(4, Cons(5, Nil))), Cons(2, Cons(1, Nil)))((b, a) => Cons(a, b))
foldLeft(Cons(4, Cons(5, Nil)), Cons(3, Cons(2, Cons(1, Nil))))((b, a) => Cons(a, b))
foldLeft(Cons(5, Nil), Cons(4, Cons(3, Cons(2, Cons(1, Nil)))))((b, a) => Cons(a, b))
Cons(5, Cons(4, Cons(3, Cons(2, Cons(1, Nil)))))

Exercise 13

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

// Program Trace
- id: (b: B) => b

foldRightViaFoldLeft2(List(1,2,3,4,5), 0)(_+_)
foldLeft(Cons(2, Cons(3, Cons(4, Cons(5, Nil)))), id)((g, a) => b => g(f(a, b)))(z)
foldLeft(Cons(2, Cons(3, Cons(4, Cons(5, Nil)))), id)((id, 1) => b => id(1 + b))(z) // g=id, a=1, res b => b + 1
foldLeft(Cons(3, Cons(4, Cons(5, Nil))), id)((id, 1) => b => id(f(b + 1)))(0)

Exercise 14

def append2[A](al: List[A], bl: List[A]): List[A] =
  foldRight(al, bl)(Cons(_,_))

// Program Trace
append2(List(1,2,3,4,5), List(6,7,8,9,10))
foldRight(Cons(1, Cons(2, Cons(3, Cons(4, Cons(5, Nil))))), Cons(6, Cons(7, Cons(8, Cons(9, Cons(10, Nil))))))(Cons(_,_))
f(1, foldRight(Cons(2, Cons(3, Cons(4, Cons(5, Nil))))), Cons(6, Cons(7, Cons(8, Cons(9, Cons(10, Nil))))))(Cons(_,_))
f(1, f(2, foldRight(Cons(3, Cons(4, Cons(5, Nil))))), Cons(6, Cons(7, Cons(8, Cons(9, Cons(10, Nil))))))(Cons(_,_))
f(1, f(2, f(3, foldRight(Cons(4, Cons(5, Nil))))), Cons(6, Cons(7, Cons(8, Cons(9, Cons(10, Nil))))))(Cons(_,_))
f(1, f(2, f(3, f(4, foldRight(Cons(5, Nil))))), Cons(6, Cons(7, Cons(8, Cons(9, Cons(10, Nil))))))(Cons(_,_))
f(1, f(2, f(3, f(4, f(5, Nil))))),Cons(6, Cons(7, Cons(8, Cons(9, Cons(10, Nil))))))(Cons(_,_))
f(1, f(2, f(3, f(4, f(5, Cons(6, Cons(7, Cons(8, Cons(9, Cons(10, Nil)))))))))(Cons(_,_))
f(1, f(2, f(3, f(4, Cons(5, Cons(6, Cons(7, Cons(8, Cons(9, Cons(10, Nil)))))))))(Cons(_,_))
f(1, f(2, f(3, Cons(4, Cons(5, Cons(6, Cons(7, Cons(8, Cons(9, Cons(10, Nil)))))))))(Cons(_,_))
f(1, f(2, Cons(3, Cons(4, Cons(5, Cons(6, Cons(7, Cons(8, Cons(9, Cons(10, Nil)))))))))(Cons(_,_))
f(1, Cons(2, Cons(3, Cons(4, Cons(5, Cons(6, Cons(7, Cons(8, Cons(9, Cons(10, Nil)))))))))(Cons(_,_))
Cons(1, Cons(2, Cons(3, Cons(4, Cons(5, Cons(6, Cons(7, Cons(8, Cons(9, Cons(10, Nil)))))))))(Cons(_,_))

Exercise 15

def concat[A](l: List[List[A]]): List[A] =
  foldRight(l, List[A]())(append)

// Program Trace
concat(List(List(1,2,3), List(4,5,6), List(7,8,9,10)))
foldRight(List(List(1,2,3), List(4,5,6), List(7,8,9,10)), List[A]())(append)
f(Cons(1, Cons(2, Cons(3, Nil))), foldRight(List(List(4,5,6), List(7,8,9,10)), List[A]())(append)
f(Cons(1, Cons(2, Cons(3, Nil))), f(Cons(4, Cons(5, Cons(6, Nil)))), foldRight(List(List(7,8,9,10))),List[A]())(append)
f(Cons(1, Cons(2, Cons(3, Nil))), f(Cons(4, Cons(5, Cons(6, Nil)))), f(Cons(7, Cons(8, Cons(9, Cons(10, Nil))))), List[A]())(append)
f(Cons(1, Cons(2, Cons(3, Nil))), f(Cons(4, Cons(5, Cons(6, Nil)))), append(Cons(7, Cons(8, Cons(9, Cons(10, Nil))))))(append)
f(Cons(1, Cons(2, Cons(3, Nil))), append(Cons(4, Cons(5, Cons(6, (Cons(7, Cons(8, Cons(9, Cons(10, Nil)))))))))(append)
append(Cons(1, Cons(2, Cons(3, (Cons(4, Cons(5, Cons(6, (Cons(7, Cons(8, Cons(9, Cons(10, Nil)))))))))))))(append)
Cons(1, Cons(2, Cons(3, (Cons(4, Cons(5, Cons(6, (Cons(7, Cons(8, Cons(9, Cons(10, Nil))))))))))))

Exercise 19

def filter[A](as: List[A])(f: A => Boolean): List[A] =
  foldRight(as, Nil: List[A])((a, b) => if(f(a)) Cons(a, b) else b)

// Program Trace
filter(List(1,2,3,4,5,6,7,8,9,10))((x: Int) => x % 2 != 0)
foldRight(as, Nil: List[A])((a, b) => if(f(a)) Cons(a, b) else b)
f(1, f(2, f(3, f(4, f(5, f(6, f(7, f(8, f(9, f(10, Nil: List[A]))))))))))((a, b) => if(f(a)) Cons(a, b) else b)
f(1, f(2, f(3, f(4, f(5, f(6, f(7, f(8, f(9, Nil: List[A])))))))))((a, b) => if(f(a)) Cons(a, b) else b)
f(1, f(2, f(3, f(4, f(5, f(6, f(7, f(8, Cons(9, Nil: List[A])))))))))((a, b) => if(f(a)) Cons(a, b) else b)
f(1, f(2, f(3, f(4, f(5, f(6, f(7, Cons(9, Nil: List[A]))))))))((a, b) => if(f(a)) Cons(a, b) else b)
f(1, f(2, f(3, f(4, f(5, f(6, Cons(7, Cons(9, Nil: List[A]))))))))((a, b) => if(f(a)) Cons(a, b) else b)
f(1, f(2, f(3, f(4, f(5, Cons(7, Cons(9, Nil: List[A])))))))((a, b) => if(f(a)) Cons(a, b) else b)
f(1, f(2, f(3, f(4, Cons(5, Cons(7, Cons(9, Nil: List[A])))))))((a, b) => if(f(a)) Cons(a, b) else b)
f(1, f(2, f(3, Cons(5, Cons(7, Cons(9, Nil: List[A]))))))((a, b) => if(f(a)) Cons(a, b) else b)
f(1, f(2, Cons(3, Cons(5, Cons(7, Cons(9, Nil: List[A]))))))((a, b) => if(f(a)) Cons(a, b) else b)
f(1, Cons(3, Cons(5, Cons(7, Cons(9, Nil: List[A])))))((a, b) => if(f(a)) Cons(a, b) else b)
Cons(1, Cons(3, Cons(5, Cons(7, Cons(9, Nil: List[A])))))((a, b) => if(f(a)) Cons(a, b) else b)

flatMap

ネストしたListの各要素に、mapを適用して、flattenしている

GenTraversableOnce

TODO

Exercise 20

def flatMap[A,B](as: List[A])(f: A => List[B]): List[B] =
  concat(map(as)(f))

// Program Trace
flatMap(List(1,2,3,4,5))((i => List(i, i))
  concat(map(List(1,2,3,4,5))(i => List(i, i)))
    map(List(1,2,3,4,5))(i => List(i, i))
      foldRight(as, Nil: List[B])((a, b) => Cons(f(a), b))
      f(1, foldRight(Cons(2, Cons(3, Cons(4, Cons(5, Nil))))))((a, b) => Cons(f(a), b))
      f(1, f(2, foldRight(Cons(3, Cons(4, Cons(5, Nil))))))((a, b) => Cons(f(a), b))
      f(1, f(2, f(3, foldRight(Cons(4, Cons(5, Nil))))))((a, b) => Cons(f(a), b))
      f(1, f(2, f(3, f(4, foldRight(Cons(5, Nil))))))(((a, b) => Cons(f(a), b))
      f(1, f(2, f(3, f(4, f(5, Nil)))))((a, b) => Cons(f(a), b))
      // f = (i => List(i, i))
      f(1, f(2, f(3, f(4, Cons(Cons(5, Cons(5, Nil)), Nil)))))((a, b) => Cons(f(a), b))
      f(1, f(2, f(3, Cons(Cons(4, Cons(4, Nil)), Cons(Cons(5, Cons(5, Nil)), Nil)))))((a, b) => Cons(f(a), b))
      f(1, f(2, Cons(Cons(3, Cons(3, Nil)),Cons(Cons(4, Cons(4, Nil)), Cons(Cons(5, Cons(5, Nil)), Nil)))))((a, b) => Cons(f(a), b))
      f(1, Cons(Cons(2, Cons(2, Nil)), Cons(Cons(3, Cons(3, Nil)),Cons(Cons(4, Cons(4, Nil)), Cons(Cons(5, Cons(5, Nil)), Nil)))))((a, b) => Cons(f(a), b))
      Cons(Cons(1, Cons(1, Nil)), Cons(Cons(2, Cons(2, Nil)), Cons(Cons(3, Cons(3, Nil)),Cons(Cons(4, Cons(4, Nil)), Cons(Cons(5, Cons(5, Nil)), Nil)))))((a, b) => Cons(f(a), b))
  foldRight(Cons(Cons(1, Cons(1, Nil)), Cons(Cons(2, Cons(2, Nil)), Cons(Cons(3, Cons(3, Nil)),Cons(Cons(4, Cons(4, Nil)), Cons(Cons(5, Cons(5, Nil)), Nil))))))(append)
f(Cons(Cons(1, Cons(1, Nil))), f(Cons(Cons(2, Cons(2, Nil)))), f(Cons(Cons(3, Cons(3, Nil)))), f(Cons(Cons(4, Cons(4, Nil)))), f(Cons(Cons(5, Cons(5, Nil))), Nil))
f(Cons(Cons(1, Cons(1, Nil))), f(Cons(Cons(2, Cons(2, Nil)))), f(Cons(Cons(3, Cons(3, Nil)))), f(Cons(Cons(4, Cons(4, Nil)))), Cons(5, Cons(5, Nil)))
f(Cons(Cons(1, Cons(1, Nil))), f(Cons(Cons(2, Cons(2, Nil)))), f(Cons(Cons(3, Cons(3, Nil)))), Cons(4, Cons(4, Cons(5, Cons(5, Nil)))))
f(Cons(Cons(1, Cons(1, Nil))), f(Cons(Cons(2, Cons(2, Nil)))), Cons(3, Cons(3, Cons(4, Cons(4, Cons(5, Cons(5, Nil)))))))
f(Cons(Cons(1, Cons(1, Nil))), Cons(2, Cons(2, Cons(3, Cons(3, Cons(4, Cons(4, Cons(5, Cons(5, Nil)))))))))
Cons(1, Cons(1, Cons(2, Cons(2, Cons(3, Cons(3, Cons(4, Cons(4, Cons(5, Cons(5, Nil))))))))))

Exercise 21

def filterViaFlatMap[A](l: List[A])(f: A => Boolean): List[A] =
  flatMap(l)(a => if (f(a)) List(a) else Nil)

// Program Trace
List.filterViaFlatMap(List(1,2,3,4,5))((x: Int) => x % 2 != 0)
  flatMap(List(1,2,3,4,5))(a => if (f(a)) List(a) else Nil)
    concat(map(List(1,2,3,4,5))(a => if (f(a)) List(a) else Nil))
      map(List(1,2,3,4,5))(a => if (f(a)) List(a) else Nil)
        foldRight(as, Nil: List[B])((a, b) => Cons(f(a), b))

Exercise 24

hasSubsequence
- リストlの先頭が、リストprefixの先頭と一致するまで再帰処理
startsWith
- リストlの要素が、リストprefixの要素と一致しているか、リストprefixの要素数全てを再帰処理で確認する

  @annotation.tailrec
  def startsWith[A](l: List[A], prefix: List[A]): Boolean = (l,prefix) match {
    case (_,Nil) => true
    case (Cons(h,t),Cons(h2,t2)) if h == h2 => startsWith(t, t2)
    case _ => false
  }
  @annotation.tailrec
  def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean = sup match {
    case Nil => sub == Nil
    case _ if startsWith(sup, sub) => true
    case Cons(_,t) => hasSubsequence(t, sub)
  }

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

失敗や例外を通常の値で表し、エラー処理とリカバリに共通するパターンを高階関数として抽出する
例外は参照透過生を失わせ、コンテキストへの依存をもたらす
例外は型安全ではない
例外のスローに変わる手法として、例外的な状況が発生していることを示す値を返す
Optionデータ型

第6章純粋関数型の状態

6.2 純粋関数型の乱数生成

副作用から参照透過性を取り戻すためには、状態の更新を明示的なものにする
状態を副作用として更新するのではなく、生成された値と共に新しい状態を返すようにする
つまり、乱数と新しい状態の両方を返す

trait RNG {
  def nextInt: (Int, RNG)
}

case class SimpleRNG(seed: Long) extends RNG {
  override def nextInt: (Int, RNG) = {
    val newSeed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL
    val nextRNG = SimpleRNG(newSeed)
    val n = (newSeed >>> 16).toInt
    (n, nextRNG)
  }
}

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

参照透過性

参照透過性の確認フロー

例１

例２

unzip

reduce

List.fill

単相関数(monomorphic function)

多相関数(polymorphic function)

関数リテラル

高階関数パラメータ名

末尾再帰のオーバーライド

関数型データ構造の定義

反変（contravariant）

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

代数的データ型

列挙型

直積型

直和型

3-3

Exercise 10

Exercise 12

Exercise 13

Exercise 14

Exercise 15

Exercise 19

flatMap

GenTraversableOnce

Exercise 20

Exercise 21

Exercise 24

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

第6章 純粋関数型の状態

6.2 純粋関数型の乱数生成

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

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

第6章純粋関数型の状態