エンジニアリンググループの松原です。 社内で4月から続いているScala関数型デザイン&プログラミング輪読会で、14章を担当したので復習も兼ねてその練習問題について解説記事としてまとめます。 ちなみにこの輪読会ですが、14章に到達した現在も誰一人として脱落することなく続いております(2人が USA 出張、1人が育休なのですが、これは仕方がないので脱落と呼ばないことにします)。 私を含めちらほら心を折られている人がいるような気配もありますが、Scala に強い人が参加していることもあって何とか続けられています。
なお、この記事は エムスリーアドベントカレンダー 9 日目の記事です。
14章の練習問題について
できればお手元に本書があるとよいのですが、お持ちでない方のために少しだけ14章についての補足を書きます。
この本では1章からずっと副作用のない関数のことを純粋関数として話を進めてきたのですが、
14章ではミュータブルな処理(副作用)があったとしても、使う側から触れられなければ、純粋関数であるということを学びます。
そこで最初に出てくる例が 14.1 節のミュータブル版 quicksort になります。
上記のリンクからコードを読んでいただくと分かるように、ミュータブルな配列 arr を直接並び替える操作が行われ副作用が発生していますが、
quicksort を使う側からすると全ての副作用は quicksort 内部のローカルスコープで行われているため触れられず純粋な関数となっています。
続く 14.2 節ではこのミュータブル版の quicksort のようにローカルスコープを用いて作用の範囲を決める方法もあるが、
Scala の型システムを使って作用のスコープを適用することもできると話が進みます。
この作用のスコープを適用するために定義されるものが、局所作用モナド ST、ミュータブルな参照の代数 STRef、ミュータブルなアクションの実行のための RunnableST、ミュータブルな配列 STArray の4つです。
それぞれにリンクを貼っているので、詳細のコードはそちらをご覧ください。
これらがあることを前提に14章の練習問題は作られています。
それでは以下14章にある3問の練習問題をそれぞれ解説していきます。また私の解答は fpinscala *1リポジトリの answers ディレクトリも参考にして書いております。
練習問題1(書籍中では EXERCISE 14.1)
まずは 14.2.4 項にある EXERCISE 14.1 からです。
14.2.4 項で作ったミュータブルな配列を扱う STArray 型に、Map のデータを配列に書き込むコンビネータ def fill(xs: Map[Int,A]): ST[S,Unit] を追加する問題です。
私の解答は以下の通りです。
sealed abstract class STArray[S,A](implicit manifest: Manifest[A]) { // ...省略... def fill(xs: Map[Int,A]): ST[S,Unit] = { xs.foldRight(ST[S,Unit](())) { case ((k, v), st) => st flatMap (_ => write(k, v)) } } // ...省略... }
引数 xs に渡ってきたマップの全キーバリューペアを配列に設定するため foldRight で畳み込みます。
アキュムレーターとして ST[S,UNIT](()) を渡すことで、STArray の write へキーとバリューを渡すことで返される ST を結合した結果を返すことができています。
練習問題2(EXERCISE 14.2)
次は 14.2.5 項にある EXERCISE 14.2 ですが、今度はミュータブル版ではなくイミュータブルな quicksort を ST などを使い構築します。
書籍中では予め STArray 用の swap と、イミュータブル版の quicksort 関数の中身は定義された状態で、quicksort 関数から呼ばれる partition と qs の純粋関数型バージョンを追加する問題です。
解答は以下になります。
object Immutable { def noop[S] = ST[S,Unit](()) def partition[S](a: STArray[S,Int], l: Int, r: Int, pivot: Int): ST[S,Int] = for { pivotVal <- a.read(pivot) _ <- a.swap(pivot, r) j <- STRef(l) _ <- (l until r).foldLeft(noop[S])((s, i) => for { _ <- s curVal <- a.read(i) _ <- if (curVal < pivotVal) (for { jVal <- j.read _ <- a.swap(i, jVal) _ <- j.write(jVal + 1) } yield ()) else noop[S] } yield ()) resultPos <- j.read _ <- a.swap(resultPos, r) } yield resultPos def qs[S](a: STArray[S,Int], l: Int, r: Int): ST[S, Unit] = if (l < r) for { pi <- partition(a, l, r, l + (r - l) / 2) _ <- qs(a, l, pi - 1) _ <- qs(a, pi + 1, r) } yield () else noop[S] def quicksort(xs: List[Int]): List[Int] = if (xs.isEmpty) xs else ST.runST(new RunnableST[List[Int]] { def apply[S] = for { arr <- STArray.fromList(xs) size <- arr.size _ <- qs(arr, 0, size - 1) sorted <- arr.freeze } yield sorted }) }
基本的には14.1節に出てくるミュータブル版の quicksort 実装にある partition および qs を、
STArray および STRef を用いて書き直していく作業となるので、コードを比較して見ていくとわかりやすいです。
解答を見て私が気になったことは以下の3点です。
qs,partitionの第1引数にSTArrayが追加されている- ローカルスコープを使うわけではないので、このように
STArrayを引き回しています
- ローカルスコープを使うわけではないので、このように
- 元のコードで
ifに対するelse節がない箇所でも、elseが必要になっている- これは
STを結合していく必要があるため、何もしない処理であるnoop[S]即ちST[S,Unit](())を返す必要があります
- これは
- 元のコードにある
partitionのforによる繰り返し処理がfoldLeftになり、表記も煩雑化- 元のコードにある
forで繰り返されている処理を、STとして結合するためにfoldLeftに変更する必要があります - 値の読み込みなども
STRefのreadを経由してSTにする必要があり結果煩雑になっています
- 元のコードにある
14.2節の注釈にもありますが、効率も表記の簡便性もともに大きく落ちていますね。 Scala の型システムを使うことでこういった手段も取れるという事例なので、これが有効なパターンがあるときに使うのが望ましそうです。
練習問題3(EXERCISE 14.3)
3問目は scala.collection.mutable.HashMap について、STRef や STArray と同じように STMap を実装しましょうという問題です。
ハッシュマップを作成して操作するための最小限のプリミティブコンビネータを考える問題なのですが、
私の時間がなかったこともあり輪読会では必要なインターフェースについてはリポジトリの解答を見てから実装の中身だけを考えました。
解答によると最小限というのは、STMap に size, apply, get, +=, -=, empty, fromMap を実装したものということで、
HashMap の生成ができ、取得や追加、削除など一通りの操作ができるものを指すようです。
これらインターフェースの型をもとに実装したものが以下となります。
import scala.collection.mutable.HashMap sealed trait STMap[S,K,V] { protected def map: HashMap[K,V] def size: ST[S,Int] = ST(map.size) // Get the value under a key def apply(k: K): ST[S,V] = ST(map(k)) // Get the value under a key, or None if the key does not exist def get(k: K): ST[S,Option[V]] = ST(map.get(k)) // Add a value under a key def +=(kv: (K, V)): ST[S,Unit] = { ST(map += kv) } // Remove a key def -=(k: K): ST[S,Unit] = { ST(map -= k) } } object STMap { def empty[S,K,V]: ST[S, STMap[S,K,V]] = ST(new STMap[S,K,V] { lazy val map = HashMap.empty[K,V] }) def fromMap[S,K,V](m: Map[K,V]): ST[S, STMap[S,K,V]] = ST(new STMap[S,K,V] { lazy val map = HashMap.empty[K,V] ++ m }) }
こちらの実装は STArray を参考に対応すれば良いので、そこまで難しくないと思います。
求められている STMap 型のインターフェースに合うように、HashMap のインターフェースを繋げるようなイメージで作ることができます。
console で試しに使ってみると以下のようになります*2。
scala> val p = new RunnableST[(Option[String], String, String)] {
| def apply[S] = for {
| map <- STMap.fromMap(Map(1 -> "x", 2 -> "y"))
| _ <- map += (3 -> "z")
| _ <- map -= (1)
| val1 <- map.get(1)
| val2 <- map(2)
| val3 <- map(3)
| } yield (val1, val2, val3)
| }
p: fpinscala.localeffects.RunnableST[(Option[String], String, String)] = $anon$1@361e138
scala> val v = ST.runST(p)
v: (Option[String], String, String) = (None,y,z)
まとめ
ということで14章についてはこの3問が練習問題でした。本書後半の方にしては比較的分量も少なめの章なので、何とか担当しきることができたと思います。
4月に始まったこの輪読会も残すところ15章のみとなりました。 自分の担当があることで担当分をやらざるを得ませんし、なんとか続けることができたかなと思います。 完走に向けて後もう少し頑張ります。
参考リンク
- fpinscala/fpinscala: Code, exercises, answers, and hints to go along with the book "Functional Programming in Scala" https://github.com/fpinscala/fpinscala
- Scala関数型デザイン&プログラミングの練習問題、解答、ヒントが掲載されています。これがあることで全く解答が分からない場合でも、解答のコードをもとに理解を進めることができたりするので助かりました。
- 書籍: FP in Scala を100倍楽しむ方法 ｜ DevelopersIO https://dev.classmethod.jp/server-side/scala/how_to_read_the_fp_in_scala/
- 輪読会をするにあたって実行環境を作成するために参考にしました。学んで、手を動かして、結果を見てというプロセスを回せて理解がかなり深まりました。
- なぜfoldRightが美しいのか - エムスリーテックブログ https://www.m3tech.blog/entry/2018/07/25/162459
- この輪読会を主催する冨岡の記事です。こちらの記事でも輪読会の雰囲気が書かれています。よろしければご覧になってください。
We're Hiring
エムスリーでは、共に医療の課題を解決していく仲間を募集中です。 社内勉強会や輪読会に参加したい方も、自分が開催したいという方も、ぜひエムスリーも検討していただけたらと思います。 カジュアル面談や Tech Talk への参加も歓迎しておりますので、以下フォームよりご応募お待ちしております。
