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

新人SEの学習記録

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

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

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

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

リストの再帰高階関数の一般化(続き)

Exercise 3.19
  • 与えられた述語条件が満たされるまでリストから要素を削除するfilter関数を記述せよ。

foldRightを使って…と思ったが、条件式をどう書けばよいかわからなかったのでmatchで。

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

しかし、どうも以下のようにして条件式をf内に埋め込めるらしい。

  def filter2[A](as: List[A])(f: A => Boolean): List[A] =
    foldRight(as, Nil:List[A])((h,t) => if(f(h)) Cons(h, t) else	t)
Exercise 3.20
  • mapと同じような働きをするflatMap関数を記述せよ。例えばflatMap(List(1,2,3))(i => List(i,i))はList(1,1,2,2,3,3)を返す。

うーん全然わからん…解答ではconcatとmapを使っていた。

  def append[A](a1: List[A], a2: List[A]): List[A] =
    a1 match {
      case Nil => a2
      case Cons(h,t) => Cons(h, append(t, a2))
    }

  def concat[A](l: List[List[A]]): List[A] =
    foldRight(l, Nil:List[A])(append)

  def flatMap[A,B](as: List[A])(f: A => List[B]): List[B] =
    concat(map(as)(f))
}

map(as)(f)では、List[A]の各要素Aに対し、A => List[B]の関数fを適用していくので、結果的にはList[List[B]]が返される。
List[List[B]]をフラットなList[B]にするためには、concatを使いListの各要素をConsに入れていく。

Exercise 3.21
  • flatMapを使ってfilterを実装せよ。

filterはList[A]と関数(引数AをとってBooleanを返す)をとってList[A]を返す。
flatMapはList[A]と関数(引数AをとってList[B]を返す)ととってList[B]を返す。
flatMapを使ってfilterを実現するには、flatMapの関数に(引数AとってList[A]を返す)関数を渡す必要がある。

  def filter3[A](as: List[A])(f: A => Boolean): List[A] =
    flatMap(as)((x) => if (f(x)) List(x) else Nil)
Exercise 3.22
  • 整数リストを2つ受け取り、対応する要素同士を足しあわせて新しいリストを作る関数を記述せよ。

この関数はList(1,2)とList(3,4)を引数にするとList(4,6)を返す。
まずmatch式を書いて…と思ったがmatchで2つのリストを扱う方法がわからず。
()で括ることで複数の対象をmatch式で扱える模様。

  def addPairwise(a: List[Int], b: List[Int]): List[Int] = (a,b) match {
    // どちらかのListがNilならNilを返す
    case (Nil, _) => Nil
    case (_, Nil) => Nil
    // 両方のListがCons(x,y)の形なら、足しあわせたものを返す
    case (Cons(h1,t1), Cons(h2,t2)) => Cons(h1+h2, addPairwise(t1,t2))
  }
Exercise 3.23
  • 3.22で作成した関数を、整数または加算に限定されないように一般化せよ。

3.22のものを少し変更し、以下のように書いた。

  def zipWith[A](a1: List[A], a2: List[A])(f: (A, A) => A): List[A] =
    (a1,a2) match {
      case (Nil, _) => Nil
      case (_, Nil) => Nil
      case (Cons(h1,t1),Cons(h2,t2)) =>	Cons(f(h1,h2), zipWith(t1,t2)(f))
    }

想定では引数としてとる二つのリストは同じ型で、返す型も同じ型だったが、
解答を見るとこれらは全て異なる型でも大丈夫のように作られていた。

  def zipWith[A,B,C](a1: List[A], a2: List[B])(f: (A, B) => C): List[C] =
    (a1,a2) match {
      case (Nil, _) => Nil
      case (_, Nil) => Nil
      case (Cons(h1,t1),Cons(h2,t2)) =>	Cons(f(h1,h2), zipWith(t1,t2)(f))
    }

確かに、これなら整数と浮動小数点数を足しあわせたり、
文字列に整数を末尾に加えたりできる。

この関数を実際に使用すると以下のようになる。

scala> List.zipWith(List(1,2,3),List(4,5,6))(_+_)
res87: List[Int] = Cons(5,Cons(7,Cons(9,Nil)))

scala> List.zipWith(List(1,2,3),List(4,5,6))(_-_)
res88: List[Int] = Cons(-3,Cons(-3,Cons(-3,Nil)))

scala> List.zipWith(List(1,2,3),List(4,5,6))(_*_)
res89: List[Int] = Cons(4,Cons(10,Cons(18,Nil)))

scala> List.zipWith(List("a","b","c"),List("d","e","f"))(_+_)
res90: List[String] = Cons(ad,Cons(be,Cons(cf,Nil)))