#book #wip  ## What is functional programming いわゆる関数型言語でよく挙げられる、「副作用のない」という特徴について簡単に触れられている。 副作用がないことのメリットとして再利用性やテストの容易性など基本的な関数型のメリットについて触れてる。 その中でReferential transparencyとSubstitution modelについて説明されている。 まずReferential Transparencyはなんとなく想像できると思うが、「同じ入力に対して同じ作用と同じ出力とを持つプログラムになる」ということで要するに任意に実行について同じ入力であれば同じ動作をすることを保証するというプログラムの性質のことである。例えば、簡単な例で `F(2) + G(5) == 7` だとした時には、 `F(2)が2` で `G(5)が5` に置き換えた時にも同じ動作をするというプログラムのことである。これは置き換えによって成立しててこういったモデルをおそらくsubstitute modelという。substitute modelがあるとプログラムはシンプルかる綺麗に保たれるのでこの概念を大事にすることが関数型の始まりのようである。 ### 補足 Referential transparencyとSubstitution modelのお互いの立ち位置がわかりづらかったのでそれについて[話してるスレッド](https://softwareengineering.stackexchange.com/a/223330)を参考に解釈した。 > So breaking RT disables you from using the substitution model. The big problem with not being able to use the substitution model is the power of using it to reason about a program? これによればReference Transparencyが失われるとSubstitute modelが使えなくなってしまい、プログラムを推論する(おそらく式や規則として表現するということ)ができなくなり関数型のパワーが発揮できなくなるということが言いたいのだと思う。 ## Getting started with functional programming in Scala - この章は、Scalaの文法の話がメインだった。 - 細かなScalaの文法の説明部分は省略して、なるほどとなって部分などについて触れていく。 ### 副作用のある関数 - 当然関数型にも副作用を生じないといけない場面がある、例えばmain関数などがそうである。 - そういった関数を関数型の文脈では、procedureやimpure functionsと呼ぶ。 ### 末尾再帰の最適化について - 普通にfor文などでループを実装してしまうと、イテレーションのための変数が各ループで副作用を生んでしまう。 - これを避けるために再帰関数を使ってループの実装を行うのが一般的である。 - Scalaで末尾再帰関数で実装される場合には、コンパイラがそれを見つけてwhileと同じようなバイトコードでコンパイルされるらしい。 - ちなみに末尾再帰とは、再帰の呼び出しの最後が自分自身であるコードのことを言う。 - 例えば以下のコードは末尾再帰である scala ``` def factorial(n: Int): Int = { def go(n: Int, acc: Int): Int = if(n <= 0) acc else go(n-1, n*acc) go(n, 1) } ``` - 例えば以下のようなものが含まれていると、末尾再帰とは呼べない scala ``` 1 + go(n-1, n*acc) ``` ### 高階関数について - 高階関数は、関数を引数にとる関数のことである。 - Scalaでは関数は第1級オブジェクトであり、型としては `Int => Int` のようになる。 - 本の中で出てきたコードは以下 scala ``` def formatResult(name: String, n: Int, f: Int => Int) = { val msg = "The %s of %d is %d." msg.format(name, n, f(n) } ``` ### polymorphic functions (ジェネリクス)について - このように高階関数などがあると(まあなくても)、違う型に対する同じような処理をまとめて書きたくなる。 - ここでジェネリクスが有効になる。 - 例えばArrayの操作で `findFirst` という `hogehogeを満たす最初の要素` などは型に関わらず同じような処理が可能である。 - それが以下のメソッドで、まとめとしてこの章で出てきた、 `高階関数` , `末尾再帰`, `ジェネリクス` を全て利用している。 scala ``` def findFirst[A](as: Array[A], p: A => Boolean): Int = { def loop(n: Int): Int = if(n >= as.length) -1 else if(p(as(n))) n else loop(n+1) loop(0) } ``` ## Functional data structures - Functional data structureとは、副作用のない純粋関数によって扱われるようなデータ構造のことである。 - この章では、Listを自前で実装することを通して説明している。 - 以下が説明に出てくるプログラム例である。 scala ``` sealed trait List[+A] case object Nil extends List[Nothing] case class Cons[+A](head: A, tail: List[A]) extends List[A] ``` - Consは関数型でよく出現する `car` , `cdr`, `cons` から来てると推測した。 ### traitについて - traitは他の言語で言うところのinterfaceやmixinを提供する機能。 - ↑の例ではListのデータ構造としては `Nil(空のリスト)` と `Cons[+A](非空のリスト)` の2種類の実装があることを表現しており、それぞれは型が `List[A]` の派生である。 - また `case class` 、 `case object` は [ケースクラス](https://dwango.github.io/scala_text/case-class-and-pattern-matching.html) というもので、ケースクラスとして定義するとパターンマッチングの型として使用できる。 - パターンマッチの話は後述する。 ### 参考 [https://dwango.github.io/scala_text/trait.html](https://dwango.github.io/scala_text/trait.html)([https://dwango.github.io/scala_text/trait.html)](https://dwango.github.io/scala_text/trait.html)) ### 共変性(covariant) と 反変性(contravariant)について - またジェネリクスの型の前についてる `+` は共変性を示してる。 - 共変性と反変性については詳細の説明は[記事](https://omuomugin.github.io/blog/2019/04/17/covariant-and-contravariant.html)で雑にイメージをまとめている。 ### pattern matching - Javaで言うところのSwitch相当である。 - ただし、型でマッチングができるためより高機能で柔軟である。 scala ``` def sum(ints: List[Int]): Int = ints match { case Nil => 0 case Cons(x, xs) => x + sum(xs) } ``` - また、以下のコードのようにネストして「構造」を比較して動作を変更することができる。 - `x` や `y` は、任意の値を指し、特に `_` はその後使うことのない任意の値を表現している。 scala ``` val x = List(1, 2, 3, 4, 5) match { case Cons(x, Cons(2, Cons(4, _))) => x case Nil => 42 case Cons(x, Cons(y, Cons(3, Cons(4, _)))) => x + y case Cons(h, t) => h + sum(t) case _ => 101 } ``` ### data sharing - Listなどのデータ構造をimmutableに扱うとすると、単純な解決方法は毎回ハードコピーをすることになる。 - しかし当然それではメモリの効率などが悪くなる。 - これを解決する方法の1つとして `data sharing` がある。 - ちなみに他に知ってるのは、Swiftなどで用いられる `copy on write` である。 - 変更が生じた際にデータをコピーして、参照してるだけの場合には同じデータを参照し続けるというものである。 - `data sharing` では、さらに書き込みの際にも同じデータを参照する仕組みを提供する。 - 例えば、 `x = {"b", "c", "d"}` というときに `y = "a" :: x` という `a` を先頭に追加したリストを新たに用意する場合は、xもyも同じオブジェクトを参照するようになる。 - またyの最後の要素を削除する際にも同様に実際には削除は行われずにyの最後のポインタが1つ前になるような挙動をする。 - しかし、間の要素などが変更された時や最後尾に要素を追加するときにどうなるか気になる。 ### curried (カリー化) - カリー化は複数の引数を持つような関数の引数を減らして、その代わり関数を返してチェーンして使うようにするテクニックである。 - [ここ](https://dwango.github.io/scala_text/function.html) にある例を引き合いに出すと、 scala ``` val add = (x: Int, y: Int) => x + y add(100, 200) val addCurried = (x: Int) => ((y: Int) => x + y) addCurried(100)(200) ``` - 本での説明としては、 > 型推論の効果を最大化するためにカリー化をよく行うことがある - としていて、具体的にはカリー化していない場合には scala ``` def dropWhile[A](l: List[A], f: A -> Boolean): List[A] // 本体は省略 val xs: List[Int] = List(1, 2, 3, 4, 5) val ex1 = dropWhile(xs, (x: Int) => x < 4) // カリー化していないと第２引数のxには型の明示が必要になる ``` - これをカリー化した場合には以下のように型の明示が必要じゃなくなり、より一般的な用途としてコンテキストを考慮せずに使うことができる。 scala ``` def dropWhile[A](as: List[A])(f: A => Boolean)] List[A] // 本体は省略 val xs: List[Int] = List(1, 2, 3, 4, 5) val ex1 = dropWhile(xs)(x => x < 4) // dropWhile(xs)が返す型が推論できるので、型の明示がなくなった ``` ## Handling errors without exceptions ### エラーハンドリングの導入 - この章では関数型で高階関数などとうまく活用できる形で例外やエラーを伝搬させる話が紹介されてる。 - このあと出てくるOptionやEitherなどを紹介するスタートとして以下のコードから始める scala ``` def failingFn(i: Int): Int = { val y: Int = throw new Exception("fail!") try { val x = 42 + 5 x + y } catch { case e: Exception => 43 } } ``` - ↑は1章で紹介したReference Transparencyが壊れていて関数型パラダイムの原理に沿っていない。 - Reference Transparencyであるならば変数の結果は全て置き換えが可能になるはずなので `y` を `throw new Exception("fail!")` で置き換えることが可能なはずである。 - しかし置き換えをした場合、この関数の結果は `47` ではなくcatch節の `43` になってしまう。 - したがって置き換えが成立していないのでReference Transparencyではなくこのエラーハンドリングのモデルは関数型では使えないことがわかる。 - このようにReference Transparencyは、置き換えだけではなく自分よりも外の状態やコンテキストに動作が依存しないこととも取れる。 - 上記の例のように `try-catch` に動作が依存してしまうので外に依存していると言える。 - また型安全に例外を扱えないという問題もこのモデルにはある。 - これを解決する方法として例外などを発火するのではなく、エラーケースを表現する値を返すことがスタートとなる。 - 値を返すというアプローチにもいくつか問題点がある - そもそもエラーを表現する値がない - 例えばIntでは0、-1はエラーを表現するのか、実際の値なのか判別がつかない。また型によってはこういったものがない場合さえある。 - 理想的には、型でエラーを判定したい - しかし、エラー用の値だと型では判別不可になる。 - そこでOptionとEitherが出てくる。本では、Option -> Eitherの順で紹介されてるので、ここでもその順で紹介する。 ### Option - Optionは型で値とそれ以外を表現する方法である。以下がそれを示す例のコード scala ``` sealed trait Option[+A] case class Some[+A](get: A) extends Option[A] case object None extends Option[Nothing] ``` - `Some` は値を `None` は値がないこと(つまりエラーなどが起こった)を表現する。 - 一見これによって全てが解決されるように見えるが、ここにも問題があり今までのメソッドをOption用に移行しなくてはいけないなどが考えられる。 - しかしこれは `lift` のような高階関数で解決することができる。 - Scalaで一般的かは知らないのだけれど、この本では `lifting` と呼んでいる。 scala ``` def lift[A, B](f: A => B): Option[A] => Option[B] = _ map f ``` - これを用いると、math.abs(絶対値を取る)ように `Double => Double` を `lift(math.abs)` で `Option[Double] => Option[Double]` に型を上げることができた(lifting)。 - 最初は戸惑うけど、Optionのジェネリクスの時に共変性を持つように指定されてるために可能になっている。 - 共変性については[こちら](https://omuomugin.github.io/blog/2019/04/17/covariant-and-contravariant.html) - とはいえ、このままでは `None` という名前通り何も値がないことしかわからない。 - 実用上ではエラー内容はスタックトレースなどを見たいという場面が多く発生するので次に紹介するEitherがある。 ### Either - Eitherは以下のようなコードで表現される scala ``` 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] ``` - EitherはOptionと同様で右と左で2つのケースを持ちつつ、どちらの場合も値を持つのが特徴。 - 一般的には、Leftが失敗ケースでRightが成功ケースである。(ここどうなの？とも思うのだけれど) - 例えば以下のような使い方が可能になる scala ``` def safeDiv(x: Int, y: Int): Either[Exception, Int] = try Right(x / y) catch { case e: Exception => Left(e) } ``` ## Strictness and laziness - この章では、`strictness` と `non-strictness` の定義と遅延処理について紹介されてる。 - 3章では多くのList系の演算(この本では`bulk operations`と呼ばれてる)について触れたが、この時点では全てのList系の演算時には新たなリストを毎回作成していて、無駄な走査を繰り返したり無駄なメモリを消費したりしている。 - これを改善する方法をベースにこの章では、遅延処理を紹介している。 ### strictnessとnon-strictnessについて - ある関数が `non-strictness` 任意の引数を評価しないとき、その関数は `non-strictness` と呼ぶ。 - 例えば、` && ` は第一引数がfalseだったら第二引数以降は評価しないので、 `non-strictness` である。 scala ``` false && { println("!!"); true } // does not print anything ``` - 他の例としては、 `if-else` も条件によってどちらかのみを評価するので `non-strictness` といえる。 - また一般的に引数に渡されている評価されない関数の形を `thunk` と呼ぶ。 ### lazy - 遅延評価のためのキーワードとしてScalaでは `lazy` を使う。 - lazyを使う場合は、実際の評価は参照が発生するまで遅延され、関数の結果もキャッシュされるようになる。 - キャッシュの例は以下 scala ``` def maybeTwice(b: Boolean, i: () => Int): Int = { lazy val j = i if(b) j()+j() else 0 } ``` - ちなみに以下のように関数を呼び出し方式で書かないようなシンタックスでも記述が可能。 scala ``` def maybeTwice(b: Boolean, i: => Int): Int = { lazy val j = i if(b) j+j else 0 } ``` ### ListにおけるLazyの活用 - Lazyを使うことで、冒頭であげたような無駄なリストの走査や生成をしなくなる。 - このような遅延処理をするListをStreamと呼ぶ。 - 本書では、Streamを自作することでより詳細を紹介してるが、Streamに対する演算のスタックトレースを見れば動作が明らかなのでそちらだけを紹介する。 - 本書のStreamはconsを利用して実装しており、headとtailを遅延評価している。 scala ``` Stream(1, 2, 3, 4).map(_ + 10).filter(_ % 2 == 0).toList # cons(11, Stream(2, 3, 4).map(_ + 10)).filter(_ % 2 == 0).toList // まずは先頭がmapされる # Stream(2, 3, 4).map(_ + 10).filter(_ % 2 == 0).toList // filterが適用される # cons(12, Stream(3, 4).map(_ + 10)).filter(_ % 2 == 0).toList // mapが適用される # cons(12, Stream(3, 4).map(_ + 10)).filter(_ % 2 == 0).toList // filterが適用される # 12 :: Stream(3, 4).map(_ + 10).filter(_ % 2 == 0).toList // toListが適用される # 12 :: cons(13, Stream(4).map(_ + 10)).filter(_ % 2 == 0).toList // mapが適用される # 12 :: Stream(4).map(_ + 10).filter(_ % 2 == 0).toList // filterが適用される # 12 :: cons(14, Stream().map(_ + 10)).filter(_ % 2 == 0).toList // mapが適用される # 12 :: cons(14, Stream().map(_ + 10)).filter(_ % 2 == 0).toList // filterが適用される # 12 :: 14 :: Stream().map(_ + 10).filter(_ % 2 == 0).toList // toListが適用される # 12 :: 14 :: List() ``` - また余談として、この遅延処理を用いることで無限リストを扱うことができる。 ## Purely functional state - 関数型言語でも当然stateを持つような対象を扱う必要がある。 - 例えば、`scala.util.Random` みたいな乱数がわかりやすい例である。 scala ``` val rng = new scala.util.Random rng.nextDouble # 0.9867076608154569 rng.nextDouble # 0.8455696498024141 ``` - 上記のように、明らかにrngはある種のstateを持って、呼び出しがあるたびにそのstateを更新している。 - これは、`referentially transparent` を侵害しているため関数型で扱うのは難しいので上手く工夫する必要がある。 - 例えば、入力と出力が一定ではないため、テストが困難になってしまうなどの問題がある。 - そこでアイディアとしてstateそのものを更新するのではなく、新しいstateを返すようにするものである。 - 以下のインターフェースを実装すればよい scala ``` trait RandomNumberGenerator { def nextInt: (Int, RandomNumberGenerator) } ``` - 前提として、RandomNumberGeneratorは必ずその時のstateでは必ず同じ数字を返すとする。 - そのような実装のとき新しいgeneratorに対して、nextIntを呼び出せば必ず同じ結果が返ってくるようになる。 - 実装の一例として本では紹介されてるが上記のような前提の実装の元では以下のような実行例になる。 scala ``` val rng1 = RandomNumberGenerator() val (n1, rng2) = rng1.nextInt() val (n2, rng3) = rng2.nextInt() val (n3, rng4) = rng3.nextInt() ``` - 上記の実行例でのポイントは、`rng1.nextInt()` は常に同じ結果を返すことにある。 - これによって既存のRandomNumberGeneratorのように自身のstateを更新することなく、stateの更新を扱うことができるようになった。 - このように、 `S => (A, S)` という形の関数を `state actions` や `state transitions` と呼ぶ。 - 他にもflatmapやtype aliasなどいくつかのScalaの機能の紹介があったが、この `state transisions` の方がメインだったのでその紹介に留める。 - この考え方はReduxやelmに近いものを感じた(reduxがelmから着想を得てるのでそれはそうだが)。