読者です 読者をやめる 読者になる 読者になる

新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。気づけば社会人3年目に突入。

学習記録:Scala関数型デザイン 第5章

学習記録 関数型 プログラミング Scala

第5章:正格と遅延

無限ストリームと余再帰

ここまで記述してきた関数は漸進的なので,無限ストリームにも対応します。
例えば,1の無限ストリームは以下のようになる。

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

onesは無限だが,ここまで記述してきた関数は,ストリームの要素のうち要求された出力を生成するのに必要な部分だけを調べる。

scala> val ones: holder.Stream[Int] = holder.Stream.cons(1, ones)
ones: holder.Stream[Int] = Cons(<function0>,<function0>)

scala> ones.take(5).toList
res15: List[Int] = List(1, 1, 1, 1, 1)

scala> ones.exists(_ % 2 != 0)
res16: Boolean = true

scala> ones.map(_ + 1).exists(_ % 2 == 0)
res17: Boolean = true

scala> ones.takeWhile(_ == 1)
res18: holder.Stream[Int] = Cons(<function0>,<function0>)

scala> ones.forAll(_ != 1)
res19: Boolean = false

どのケースでもすぐに結果が返されるが,うっかりすると終了しない式やスタックセーフではない式を書いてしまいやすい。
例えば,ones.forAll(_ == 1)では終了するための要素が永遠に検出されないため,スタックオーバーフローになる。

scala> ones.exists(_ % 2 == 0)
java.lang.StackOverflowError
...

scala> ones.toList
java.lang.StackOverflowError
...
Exercise 5.8
  • onesを少し一般化し,指定された値の無限ストリームを返すconstant関数を記述せよ。

constant関数を再帰的に呼んでいけばOK。

  def constant[A](a: A): Stream[A] =
    cons(a, constant(a))

解答を見ると,lazy valを使うともっと効率の良い関数になるとのこと。

  def constant[A](a: A): Stream[A] = {
    lazy val tail: Stream[A] = Cons(() => a, () => tail)
    tail
  }

使うとこんな感じ。

scala> val twos = holder.Stream.constant(2)
twos: holder.Stream[Int] = Cons(<function0>,<function0>)

scala> twos.take(4).toList
res24: List[Int] = List(2, 2, 2, 2)
Exercise 5.9
  • nで始まってn+1, n+2と続く整数の無限ストリームを生成する関数を記述せよ。

これは簡単。

  def from(n: Int): Stream[Int] =
    cons(n, from(n+1))

実際に使ってみると以下のようになる。

scala> val numbers = holder.Stream.from(1)
numbers: holder.Stream[Int] = Cons(<function0>,<function0>)

scala> numbers.take(10).toList
res25: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

なお,ScalaでInt型は32ビットの符号付き整数なので,21億辺りを超えると負の数になり,更に進むと正の数になるのを繰り返す。

scala> val numbers = holder.Stream.from(2147483640)
numbers: holder.Stream[Int] = Cons(<function0>,<function0>)

scala> numbers.take(10).toList
res31: List[Int] = List(2147483640, 2147483641, 2147483642, 2147483643, 2147483644, 2147483645, 2147483646, 2147483647, -2147483648, -2147483647)
Exercise 5.10

go関数を作ってループさせる。今回はvalとして実装。

  val fibs = {
    def go(f0: Int, f1:	Int): Stream[Int] =
      cons(f0, go(f1, f0+f1))
    go(0, 1)
  }

使うと以下のようになる。一定以上進むとオーバーフローする。

scala> holder.Stream.fibs.take(10).toList
res34: List[Int] = List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)

scala> holder.Stream.fibs.take(100).toList
res35: List[Int] = List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, -1323752223, 512559680, -811192543, -298632863, -1109825406, -1408458269, 1776683621, 368225352, 2144908973, -1781832971, 363076002, -1418756969, -1055680967, 1820529360, 764848393, -1709589543, -944741150, 1640636603, 695895453, -1958435240, -1262539787, 1073992269, -188547518, 885444751, 696897233, 1582341984, -2015728079, -433386095, 1845853122, 1412467027, -1036647147, 375819880, -660827267, -285007387, -945834654, -1230842041, 21182906...
Exercise 5.11
  • より汎用的なストリーム生成関数unfoldを記述せよ。

この関数は,初期状態zに加えて,生成されるストリームの次の値を生成する関数fを受け取る。

f(z)でマッチングさせ,Some(head, tail部分のStream)にマッチすればconsに入れて再帰

  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
    } 

使うと以下のようになる。

# 途中でちょうど32bit = 0になってしまう
scala> holder.Stream.unfold(2)(x => Some(x, x*x)).take(10).toList
res44: List[Int] = List(2, 4, 16, 256, 65536, 0, 0, 0, 0, 0)

scala> holder.Stream.unfold(1.0)(x => Some(x, x/2)).take(10).toList
res50: List[Double] = List(1.0, 0.5, 0.25, 0.125, 0.0625, 0.03125, 0.015625, 0.0078125, 0.00390625, 0.001953125)

unfoldは,Streamを生成するための標準的な関数である。
Optionは,Streamを終了しなければならない場合に,そのタイミングを指定するために使われる。

unfold関数は,余再帰(corecursive)と呼ばれる関数の一例である。
再帰関数がデータを消費するのに対し,余再帰関数はデータを生成する。
また,再帰関数が再帰処理によって入力を小さくしていくことで終了するのに対し,
再帰関数は生産性が続く限り終了する必要がない。

Exercise 5.12
  • unfoldを使ってfibs, from, constant, onesを記述せよ。

まずはones。

  val onesViaUnfold =
    unfold(1)(_	=> Some(1,1))

fromとconstantも簡単。

  def fromViaUnfold(n: Int): Stream[Int] =
    unfold(n)(n => Some(n, n+1))

  def constantViaUnfold[A](a: A): Stream[A] =
    unfold(a)(a => Some(a, a))

fibは初期状態を(0,1)とするところと,パターンマッチングを使うのがわかりにくい。

  val fibsViaUnfold =
    unfold((0,1)){ case (f0,f1) => Some(f0, (f1, f0+f1)) }

2番目の括弧を( (f0,f1) => ... )と書きたくなるが,こうは書けない模様。
コンパイル時にパターンマッチングを使えと言われる。

<console>:198: error: missing parameter type
Note: The expected type requires a one-argument function accepting a 2-Tuple.
      Consider a pattern matching anonymous function, `{ case (f0, f1) =>  ... }`
           unfold((0,1))((f0,f1) => Some(f0, (f1, f0+f1)))

まとめ

本章では,モジュール性の高い効率的な関数型プログラムを実装するためのテクニックとして非正格性を取り上げた。
非正格性は,式の記述をその評価の方法やタイミングから切り離すことでモジュール性を向上させることを目的としている。
関心を切り離すことで同じ記述を複数のコンテキストで再利用でき,式の異なる部分を評価することで異なる結果が得られるようになる。

次章では,状態に関する純粋関数型のアプローチを取り上げる。