SE情報技術研究会’s blog

http://se-info-tech.connpass.com

2015-12-19 第１０回 関数型プログラミング勉強会（Scala）の振り返り

Scala Scala関数型デザイン＆プログラミング 振り返り 読書会 関数型プログラミング

Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド (impress top gear)

Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド (impress top gear)

第５章 正格と遅延

Listの処理などを正格で全て評価すると不要なデータまで処理することになり ムダが発生する。

正格関数と非正格関数

  • 正格関数＝引数が常に評価される関数
  • 非正格関数＝引数の１つ以上を評価しないことが可能な関数

非正格で馴染みのものは「&&」と「||」は非正格な演算である。

  • 「&&」の場合、 １つ目の結果が false の場合、２つ目の演算は行わないため非正格。
  • 「||」の場合、 １つ目の結果が true の場合、２つ目の演算は行わないため非正格。

「if」文も非正格な構文である。

  • 条件にあった場合しか処理を行わないため非正格。
  • ただし式の条件は全て評価されるので、そこについては正格。

サンク（thunk）＝必要になるまで評価されない形式の式

非正格な引数を指定する関数をつくる時に下記の書式で定義することが可能

def 関数名[A](arg: ()=>A)

ただし、これだと引数の関数に関数の引数（ここだと()）も定義しないといけないので、めんどい。 代わりに下記のように: =>Aと定義することも可能。

def 関数名[A](arg: =>A)

lazy

scalaの非正格な評価を行う引数は参照されるたびに式が評価される。 これだと効率がよくないので一度評価した値はキャッシュさせたほうがよい。 そのためlazyという評価した値を明示的にキャッシュさせるキーワードがある。

lazyキーワード ＝ val宣言にlazyキーワードを追加すると式の評価が最初に参照されるまで先送りされ、評価後は再度式が評価されないように結果がキャッシュされる。

引数の評価の種類

  • 値渡し＝関数の引数を関数が実行された時点に評価して渡すこと。
  • 名前渡し＝関数の引数を関数内で使われるタイミングで評価すること。

ボトム

  • 式が終了しない、もしくはエラーをスローする場合のことをボトムに評価されるという
  • 正格のf(x)でxがボトムに評価される場合、f(x)もボトムに評価されることになる
    → 例えばxを評価した際に無限ループが発生すれば、f(x)も処理が終了しない

遅延リストの例

Stream＝コンストラクタの引数が非正格の評価を行うリスト

遅延の問題点

p. 85

val x = Cons(() => expensive(x), t1)
val h1 = x.headOption
val h2 = x.headOption

これだとexpensive(x)が2度実行されてしまう

スマートコンストラクタ

p. 86

def cons[A](hd: => A, tl: => Stream[A]): Stream[A] = {
  lazy val head = hd
  lazy val tail = td
  Cons(() => head, () => tail)
}

Exercise 5.1

GitHubにあがってる解答によると一般的な解答は下記。

def toListRecursive: List[A] = this match {
  case Cons(h,t) => h() :: t().toListRecursive
  case _ => List()
}

上記の解答だと末尾再帰ではないのでスタックオーバーフローが発生する。 そのため末尾再帰で書き換える必要がある。

末尾再帰の手順は下記になる。

  • Streamの要素が逆になるListとなるアキュムレータを作成する
  • アキュムレータのヘッダーにStreamのヘッダーを追加する
  • 最後にListをreverseする

他にもreverseせずにListBufferを使う手段もある

Exercise 5.2

GitHubにあがってる解答には下記のように書いてある。

  • take関数はパターンマッチでn == 0かのチェックをおこなっているのでn == 0の場合、Streamの要素を全く見ないで済む
  • drop関数はtake関数と違い非正格ではない

Unlike take, drop is not incremental. That is, it doesn't generate the answer lazily. It must traverse the first n elements of the stream eagerly.

take関数と違いdrop関数は漸進的でない。 つまり非正格で結果を生成しない 先行評価でstreamの最初のn個の要素を見に行く。

@annotation.tailrec
final def drop(n: Int): Stream[A] = this match {
  case Cons(_, t) if n > 0 => t().drop(n - 1)
  case _ => this
}

毎回tを評価することにより非正格にはならない。

Exercise 5.3

GitHubにあがってる解答で問題なし。

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

  • 遅延によって式の記述と評価を切り離すことができる
    → 関数のモジュール性を向上することが可能

Exercise 5.4

GitHubにあがってる解答で問題なし。

解答に次のようなコメントがある。

Since && is non-strict in its second argument, this terminates the traversal as soon as a nonmatching element is found.

第２引数の&&は非正格であるため マッチしない要素が見つかると捜索を中断する

解答に値を入れて段階的に見ていく。 fに要素が奇数ならtrueにした場合

trueが返る場合：

Stream(1*1, 3*1, 5*1).forAll(x => x%2==1)
↓ f = x => x%2==1
Stream(1*1, 3*1, 5*1).foldRight(true)((a,b) => f(a) && b)
↓ 
(1*1, Stream(3*1, 5*5)) => f(1*1) && Stream(3*1, 5*1).foldRight(true)((a,b) => f(a) && b))
↓
true && f(3*1) && Stream(5*1).foldRight(true)((a,b) => f(a) && b)
↓
true && true && f(5*1)
↓
true && true && true
↓
true

falseが返る場合：

Stream(1, 4, 6).forAll(x => x%2==1)
↓ f = x => x%2==1
Stream(1, 4, 6).foldRight(true)((a,b) => f(a) && b)
↓ 
(1, Stream(4, 6)) => f(2) && Stream(4, 6).foldRight(true)((a,b) => f(a) && b))
↓
f(1) && Stream(4, 6).foldRight(true)((a,b) => f(a) && b))
↓
true && Stream(4, 6).foldRight(true)((a,b) => f(a) && b))
↓
true && f(4) && Stream(6).foldRight(true)((a,b) => f(a) && b))
↓
true && false && Stream(6).foldRight(true)((a,b) => f(a) && b))
↓
false

Exercise 5.5

GitHubにあがってる解答で問題なし。

解答に値を入れて段階的に見ていく。 fに要素が奇数ならtrueにした場合

Stream(1*1,2*1,3*1).takeWhile_1(x => x%2==1)
↓
Stream(1*1,2*1,3*1).foldRight(empty[A])((h,t) => ...)
↓
if( (1*1)%2 == 1) cons(1, Stream(2*1,3*1))
↓
if( (2*1)%2 == 1) ...
else cons(1, empty)
↓
Stream(1)

Exercise 5.6

GitHubにあがってる解答で問題なし。

解答に値を入れて段階的に見ていく。

値がある場合

 Stream(1*2, 2*2, 3*2).headOption
 ↓
 Stream(1*2, 2*2, 3*2).foldRight(None: Option[A])((h,_) => Some(h))
 ↓
Cons(1*2, Stream(2*2, 3*2)) => ((h,_) => Some(h))
 ↓
(1*2,_) => Some(2)
 ↓
Some(2)

値がない場合

Empty.headOption
 ↓
Empty.foldRight(None: Option[A])((h,_) => Some(h))
 ↓
Empty => None
 ↓
None

Exercise 5.7

GitHubにあがってる解答で問題なし。

斬新的（ぜんしんてき）＝順を追って徐々に目的を実現しようとするさま。

  • 中間結果を完全にインスタンス化することなく、これらの関数を次々に呼び出すことができる
  • リスト5-5の例は全要素がmapされた中間結果のListを作ってからfilterに行っているのではなく、要素ごとに処理が実行されている例を示している
  • 中間Streamが生成されないため、現在使われている要素を扱うのに必要なメモリで十分になる

無限ストリームと余再帰

Exercise 5.8

GitHubの解答は下記

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

解説には

This is more efficient than cons(a, constant(a)) since it's just one object referencing itself.

これは自身の参照をしているのは1オブジェクトなので cons(a, constant(a)) より効率的である

とある。

例えば要素「1」を持つ無限Streamをつくる場合

constant(1)
↓
tail = Cons(()=>1, ()=>tail)
↓ イメージ的には下記だが新しいConsを作っているわけではない
tail = Cons(()=>1, Cons(()=>1, Cons(()=>1, …))

Exercise 5.9、5.10

GitHubにあがってる解答で問題なし。

ただし5.10のフィボナッチでzipやiterateを使っての実装をしている参加者もいた

zip関数を使った場合

  def fib1: Stream[Int] =
    Stream(0, 1).append(zip(fib1, fib1.tail).map({ tuple => tuple._1 + tuple._2 }))
  def zip[A, B](s1: Stream[A], s2: Stream[B]): Stream[(A, B)] = zipWith(s1, s2)((_, _))
  def zipWith[A, B, C](s1: Stream[A], s2: Stream[B])(f: (A, B) => C): Stream[C] =
    (s1, s2) match {
      case (Empty, _) => Empty
      case (_, Empty) => Empty
      case (Cons(h1, t1), Cons(h2, t2)) => cons(f(h1(), h2()), zipWith(t1(), t2())(f))
    }

iterate関数を使った場合

  def fib2: Stream[Int] = iterate((0, 1))({
    case (a: Int, b: Int) => (b, a + b)
  }).map(_._1)
  def iterate[A](start: A)(f: A => A): Stream[A] = cons(start, iterate(f(start))(f))

Exercise 5.11

5.11のunfoldだけだとわかりづらいので、例として5.12のfromViaUnfold関数を見てみる

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

これに10を渡した場合を段階的に見ていく

fromViaUnfold(10)
↓
unfold(10)(10 => Some((10,10+1)))
↓
cons(10,unfold(11)(11 => Some((11,11+1))))
↓
Stream(10, 11, …)
  • OptionはStreamを終了しなければならない場合に、そのタイミングを指定するのに使える
  • 再帰関数はデータを消費する関数で余再帰関数はデータを生成する関数