2015-10-31 第７回 関数型プログラミング勉強会の簡単なまとめ Part.1

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

今回は前回の続きからでExericise 3.17から見ていくことに。

Exericise 3.17

ここら辺は今までの例題を参考にfoldRightを使って実装するパターン。 段階的に見ていくとこのような感じになる。

doubleToString(List(0.1, 0.2, 0.3)):List[String] =
foldRight(Cons(0.1, Cons(0.2, Cons(0.3, Nil)), Nil)((h,t) => Cons(h.toString, t))
Cons("0.1", foldRight(Cons(0.2, Cons(0.3, Nil)), Nil)((h,t) => Cons(h.toString, t)))
Cons("0.1", Cons("0.2", foldRight(Cons(0.3, Nil), Nil)((h,t) => Cons(h.toString, t))))
Cons("0.1", Cons("0.2", Cons("0.3", foldRight(Nil, Nil)((h,t) => Cons(h.toString, t)))))
Cons("0.1", Cons("0.2", Cons("0.3", Nil)))

Exercise 3.18

この例題も前の例題を踏まえていて、foldRightで行うのが一般的だけどスタックオーバーフローの問題がある。

なのでfoldRightViaFoldLeftを使ってスタックオーバーフローを避けることも可能だが、 実際のScalaのListの実装は関数内でミュータブルなローカル変数を使って処理することが多い。

ミュータブルでも関数内の閉じた世界だと問題ないという考えに基づいている。

下記はfoldRightの例。

map(List(1,2,3)(x => x+1)):List[String] =
foldRight(List(1,2,3), Nil)((h,t) => Cons(h.toString(),t))
foldRight(Cons(1, Cons(2, Cons(3, Nil))), Nil)((h,t) => Cons(h+1,t))
Cons(1+1, foldRight(Cons(2, Cons(3, Nil)), Nil)((h,t) => Cons(h+1,t)))
Cons(1+1, Cons(2+1, foldRight(Cons(3, Nil), Nil)((h,t) => Cons(h+1,t))))
Cons(1+1, Cons(2+1, Cons(3+1, foldRight(Nil, Nil)((h,t) => Cons(h+1,t)))))
Cons(1+1, Cons(2+1, Cons(3+1, Nil)))
Cons(2, Cons(3, Cons(4, Nil)))

下記はfoldRightViaFoldLeftの例。

map_1(List(1,2,3)(x => x+1)):List[String] =
foldRightViaFoldLeft(List(1,2,3), Nil)((h,t) => Cons(h+1,t))
foldRightViaFoldLeft(Cons(1, Cons(2, Cons(3, Nil))), Nil)((h,t) => Cons(h+1,t))
Cons(1+1, foldRightViaFoldLeft(Cons(2, Cons(3, Nil)), Nil)((h,t) => Cons(h+1,t)))
Cons(1+1, Cons(2+1, foldRightViaFoldLeft(Cons(3, Nil), Nil)((h,t) => Cons(h+1,t))))
Cons(1+1, Cons(2+1, Cons(3+1, foldRightViaFoldLeft(Nil, Nil)((h,t) => Cons(h+1,t))))
Cons(1+1, Cons(2+1, Cons(3+1, Nil)))
Cons(2, Cons(3, Cons(4, Nil)))

下記はミュータブルな変数bufを使った例。 まず、bufが空の状態で、List(1,2,3)がgo関数に渡され、最初の要素「1」が実行される。

map_2(List(1,2,3)(x => x+1)):List[String] =
  val buf = ListBuffer()
  def go(List(1, 2, 3)):Unit = {
    ListBuffer() += 1+1
    go(List(2,3)) 
  }

↓ 次にbufがListBuffer(2)の状態で、List(2,3)がgo関数に渡され、要素「2」が実行される。

  ListBuffer(2)
  def go(List(2, 3)):Unit = {
    ListBuffer(2) += 2+1
    go(List(3))
  }

↓ 次にbufがListBuffer(2,3)の状態で、List(3)がgo関数に渡され、要素「3」が実行される。

  ListBuffer(2, 3)
  def go(List(3)):Unit = {
    ListBuffer(2, 3) += 3+1
    go(Nil)
  }

↓ 次にbufがListBuffer(2,3,4)の状態で、Nilがgo関数に渡され、ループ処理は終了。

  ListBuffer(2, 3, 4)
  List(2, 3, 4)

ListBuffer(2,3,4)からをList(2,3,4)を形成する。

Exercise 3.19

これも3.18同様に3パターンで考えれる。 重要なポイントはほぼ同じなので、とりあえずfoldRightの例だけやってみる。

filter(List(1,2,3,4,5))( x => x%2==0 )
foldRight(List(1,2,3,4,5), Nil)( (h, t) => if (h => h%2==0)) Cons(h,t) else t)
foldRight(Cons(1, Cons(2, Cons(3, Cons(4, Cons(5, Nil))))), Nil )( (h, t) => if (h => h%2==0)) Cons(h,t) else t)
foldRight(Cons(2, Cons(3, Cons(4, Cons(5, Nil)))), Nil )( (h, t) => if (h => h%2==0)) Cons(h,t) else t)
Cons(2, foldRight( Cons(3, Cons(4, Cons(5, Nil))), Nil )( (h, t) => if (h => h%2==0)) Cons(h,t) else t))
Cons(2, foldRight( Cons(4, Cons(5, Nil)), Nil )( (h, t) => if (h => h%2==0)) Cons(h,t) else t))
Cons(2, Cons(4, foldRight( Cons(5, Nil)), Nil )( (h, t) => if (h => h%2==0)) Cons(h,t) else t)))
Cons(2, Cons(4, foldRight( Nil, Nil )( (h, t) => if (h => h%2==0)) Cons(h,t) else t)))
Cons(2, Cons(4, Nil))

Exercise 3.20

本の内容的にはExercise 3.18とポイントは同じだが、勉強会ではそこから広げた会話になった。

flatMap関数はリストだとmapしたものをconcatしてまとめたような関数で、ScalaにはconcatMapという関数もあるらしい。

あと、他の言語ではflatMap関数はbind関数とも呼ばれている。

これはOptionとかにも同じメソッドがあって、関数型でよく使われるMonadという型で使われる関数だそう。

ざっくり説明してもらったとこではリストもOptionも箱みたいなもので、FunctorとかApricativeFunctorとかMonadという型があり、 それぞれ下記の特徴的な関数を持っている。

• Functorは要素を処理するA => Bのmap関数を持つ
• ApricativeFunctorは要素からA => Bの関数を持つApricativeFunctorを生成するHaskellだと<*>という関数を持つ
• Monadは要素から処理した結果をMonadにもたすA => Monad[B]のflatMap/bind関数を持つ

Exercise 3.21

基本的には今までの例題をみていたらポイント的なことは同じ。 段階的に見ていくとこのような感じになる。

filterViaFlatMap(List(1, 2, 3))(x => x%2 != 0)
flatMap(List(1, 2, 3))(a => if (a%2 != 0) List(a) else Nil)
concat(map(Cons(1, Cons(2, Cons(3, Nil))))(a => if (a%2 != 0) List(a) else Nil))
concat(foldRight(Cons(1, Cons(2, Cons(3, Nil))), Nil)((h,t) => if (f(h)) Cons(h,t) else t))
concat(Cons(List(1), foldRight(Cons(2, Cons(3, Nil))), Nil)((h,t) => if (f(h)) Cons(h,t) else t)))
concat(Cons(List(1), foldRight(Cons(3, Nil), Nil)((h,t) => if (f(h)) Cons(h,t) else t)))
concat(Cons(List(1), Cons(List(3), Nil)))
foldRight(Cons(List(1), Cons(List(3), Nil)),Nil)(append)
append(List(1), foldRight(Cons(List(3), Nil),Nil)(append))
append(List(1), append(List(3), foldRight(Nil,Nil)(append)))
append(List(1), append(List(3), Nil))
append(List(1), List(3))
List(1,3)

Exercise 3.22

この例題はペアなど複数の値を持つタプルのマッチ機能についての話。GitHubの解答に下記のマッチを示している。

(a,b) match {
  case (Nil, _) => Nil
  case (_, Nil) => Nil
  case (Cons(h1,t1), Cons(h2,t2)) => Cons(h1+h2, addPairwise(t1,t2))
}

ただ、コメントのほうで使い勝手は悪いが少しだけ効率的なパターンマッチをネストすることも可能だとあるが、その例がなくて残念という話になった。

Exercise 3.23

この例題はExercise 3.22を汎用的にリファクタしたってことで、特に問題なくそのまま流していった。

Exercise 3.24

GitHubの解答はリスト限定の処理で本来は関数を組み合わせたほうが良いらしいが、それは第５章で解説しているとある。

また、解答の解説にループを抜けるためのロジックが必要と書いてあるが、解答だとNilの場合の処理もあるので、それ以外に何かあるのかが不明。

とりあえず、下記のリストがある場合で試してみた

• xs = [1,2,3]
• ys = [4,5,6]
• zs = [7,8,9]

例題の解答のコメントにある各処理を段階的に見ていく。

// (xs append ys) startsWith xs
List(1,2,3,4,5,6) startWith List(1,2,3)
1 == 1 => List(2,3,4,5,6) startWith List(2,3)
2 == 2 => List(3,4,5,6) startWith List(3)
3 == 3 => List(4,5,6) startWith Nil
true

// xs startsWith Nil
List(1,2,3) startWith Nil
false

// (xs append ys append zs) hasSubsequence ys
List(1,2,3,4,5,6,7,8,9) hasSubsequence List(4,5,6)
List(2,3,4,5,6,7,8,9) hasSubsequence List(4,5,6)
List(3,4,5,6,7,8,9) hasSubsequence List(4,5,6)
List(4,5,6,7,8,9) startWith List(4,5,6)
=> true

// xs hasSubsequence Nil
List(1,2,3) hasSubsequence Nil
List(2,3) hasSubsequence Nil
List(3) hasSubsequence Nil
Nil == Nil
true

ここまでで、リストについての内容が終わり、次からツリーの話に。 かなり長くなってきたのでいったん区切ります。