新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。もう新人じゃないかも…

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

第3章:関数型プログラミングのデータ構造(続き)

関数型データ構造でのデータ共有(続き)

高階関数型推論の改善

さきほど作成したdropWhile関数のような高階関数には、

  def dropWhile[A](l: List[A], f: A => Boolean): List[A] = l match {
    case Cons(h, t) if f(h) => dropWhile(t, f)
    case _ => l
  }

以下のように無名関数が渡されることがよくある。

scala> val x = List(1,2,3,4,5)
x: List[Int] = Cons(1,Cons(2,Cons(3,Cons(4,Cons(5,Nil)))))

scala> List.dropWhile(x, (a: Int) => a <= 3)
res38: List[Int] = Cons(4,Cons(5,Nil))

ここで、dropWhileの引数fには、無名関数(a: Int) => a <= 3が指定されている。
ここで、fの引数aは型をIntと示しているが、これは少し冗長である。
何故なら、dropWhileの第1引数lにはList[Int]型のxを渡しているので、第2引数fはIntを受け取るはずだからである。

dropWhileの引数リストを2つに分ける(カリー化する)ことで、このようなことをScalaが推測できるようになる。

  def dropWhile[A](as: List[A])(f: A => Boolean): List[A] = as match {
    case Cons(h, t) if f(h) => dropWhile(t)(f)
    case _ => l
  }

ここでdropWhileは、「引数asをとって「引数fをとってList[A]を返す関数」を返す」関数である。
関数定義に複数の引数グループが含まれている場合、型情報はこれらのグループを左から右に流れる。
最初の引数グループによってdropWhileの型パラメータAがIntに固定されているため、fの引数に型アノテーションは不要になる。

scala> val x = List(1,2,3,4,5)
x: List[Int] = Cons(1,Cons(2,Cons(3,Cons(4,Cons(5,Nil)))))

scala> List.dropWhile(x, a => a <= 3)
res39: List[Int] = Cons(4,Cons(5,Nil))

リストの再帰高階関数の一般化

Listのsumとproductの実装を見てみる。

  def sum(ints: List[Int]): Int = ints match {
    case Nil => 0
    case Cons(x, xs) => x + sum(xs)
  }

  def product(ds: List[Double]): Double = ds match {
    // 簡略化のため0.0をチェックする短絡ロジックを省略
    case Nil => 1.0
    case Cons(x, xs) => x * product(xs)
  }

この2つの定義がよく似ていることがわかる。
扱っている型の違いを除けば、リストが空である場合に返す値と、結果を結合するための演算が異なるだけである。
こうした重複に気づいた場合、部分式を関数の引数として抽出するとそれらを一般化できる。

次の関数は、リストが空である場合に返す値と、リストが空ではない場合に結果を結合するための関数を引数として受け取る。

  // リストasとNilの場合に返す値z、結合するための関数fを受け取る                    
  def foldRight[A,B](as: List[A], z: B)(f: (A, B) => B)	=
    as match {
      // リストがNil=空ならzを返す                                                    
      case Nil => z
      // 結合するにはf(x, xsの再帰)を呼ぶ                                           
      case Cons(x, xs) => f(x, foldRight(xs, z)(f))
    }

この一般化された関数により、sumとproductは以下のように書き直せる。

  def sum2(ns: List[Int]) =
    foldRight(ns, 0)((x,y) => x	+ y)

  // _ * _は(x,y) => x * yの簡易表記                                          
  def product2(ns: List[Double]) =
    foldRight(ns, 1.0)(_ * _)

foldRightは1つの型に限定されない。また一般化の際に、戻り値がリストの要素と異なる型でもよいことが判明する。
(リストの要素はA型だが、foldRightの戻り値はBになっている)
以下のように、リストのコンストラクタであるNilとConsをzとfで置き換えることで、動作を説明できる。

Cons(1, Cons(2, Nil))
f       (1, f        (2, z))
Exercise3.7
  • foldRightを使って実装されたproductは、0.0を検出した時点で直ちに再帰を中止して0.0を返せるか。

「この値が検出されたらこの値を返す」という引数とロジックをfoldRightに組み込んではどうか。

  def foldRight2[A,B](as: List[A], z: B, c: B, r: B)(f: (A, B) => B): B =
    as match {
      case Nil => z
      case Cons(x, xs) if (x == c) => r
      case Cons(x, xs) => f(x, foldRight2(xs, z, c, r)(f))
    }

  def product3(ns: List[Double]) =
    foldRight2(ns, 1.0, 0.0, 0.0)(_ * _)

どう見てもダメぽい・・・ということで解答を見ると「不可能」とのこと。
foldRightではリストを最後まで走査してから関数fによる畳み込みが発生するため。
早期終了をサポートするには、第5章で説明する非正格な評価が必要。

Exercise 3.8
  • foldRight(List(1,2,3), Nil:List[Int])(Cons(_,_))のように、NilまたはCons自体を渡した場合はどうなるか。

List(1,2,3)について走査していき、それぞれの要素をConsでまとめ、最後にはNil:List[Int]を返す。
つまり、元のList(1,2,3)を返す。

scala> List.foldRight(List(1,2,3), Nil:List[Int])(Cons(_,_))
res46: List[Int] = Cons(1,Cons(2,Cons(3,Nil)))
Exercise 3.9
  • foldRightを使ってリストの長さを計算せよ。

書いてみた。

  def length[A](l: List[A]): Int =
    foldRight(l, 0)((x,y) => 1 + y)

解答は以下。

  def length[A](l: List[A]): Int =
    foldRight(l, 0)((_,acc) => acc + 1)

やってることは一緒だけど、相変わらずワイルドカードの使いどころがよくわからない…

Exercise 3.10
  • foldRightの実装は末尾再帰でないので、末尾再帰にしたfoldLeftを記述せよ。

※末尾再帰でないということは、リストが大きいとStackOverflowErrorになってしまう。

最初は以下のようにfoldLeftを書いた。

  @annotation.tailrec
  def foldLeft[A,B](l: List[A], z: B)(f: (B, A) => B): B =
    l match {
      case Nil => z
      case Cons(x, xs) => f(foldLeft(xs, z)(f), x)
    }

が、当然ダメ。
末尾再帰とは、自身の再帰呼び出しがその計算における最後のステップになっていなければいけないので、
これだと最後の計算はfの計算になってしまう。

つまり、case Cons(x, xs)における戻り値の呼び出しをfoldLeftにする必要がある。
というわけで、以下が解答。

  @annotation.tailrec
  def foldLeft[A,B](l: List[A], z: B)(f: (B, A) => B): B =
    l match {
      case Nil => z
      case Cons(x, xs) => foldLeft(xs, f(z, x))(f)
    }

foldLeft(リストの残り, fで計算した現在の計算結果)(計算する関数f)を返すのがポイント。
リストの頭とこれまでの計算結果を使い、関数fによって計算を行う。
リストの残りと現在までの計算結果をfoldLeftに渡して再帰を行う。
foldRgihtと同様に、関数fが二箇所に登場するのに注意。

このfoldLeftを使ってもsum,product,lenghtを同様に実装できる。

  def sumLeft(ns: List[Int]) =
    foldLeft(ns, 0)(_ +	_)