2015-10-03 第5回 関数型プログラミング勉強会の簡単なまとめ
Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド (impress top gear)
- 作者: Paul Chiusano,Rúnar Bjarnason,株式会社クイープ
- 出版社/メーカー: インプレス
- 発売日: 2015/03/20
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (6件) を見る
Exercise 3.10
- 末尾再帰なら@annotation.tailrecを付けるべき。それによりコンパイル時のチェックができ、実行時に初めて見つかることがなくなるため。
- 末尾再帰とは関数の最後の行で自分自身を呼び出すことではない。
Exercise 3.12
def reverse[A](l: List[A]): List[A] =
foldLeft(l, List[A]())((acc,h) => Cons(h,acc))
l = List(1, 2, 3) の場合の (acc, h) => Cons(h, acc)の処理の段階的なイメージ。
(Nil, 1) => Cons(1, Nil) (Cons(1, Nil), 2) => Cons(2, Cons(1, Nil)) (Cons(2, Cons(1, Nil)), 3) => Cons(3, Cons(2, Cons(1, Nil)))
Exercise 3.13
def foldRightViaFoldLeft_1[A,B](l: List[A], z: B)(f: (A,B) => B): B =
foldLeft(l, (b:B) => b)((g,a) => b => g(f(a,b)))(z)
foldRightViaFoldLeft_1(List(1, 2, 3), 0)( _+_ ) の場合の処理の段階的なイメージ。
↓
foldLeft(List(1, 2, 3), (b:B) => b)( (g, head) => (0 => g( f(head, b) ) ) )(0)
↓ b = 0、f = head + b
foldLeft(List(1, 2, 3), 0 => 0)( (g, head) => (0 => g( head + 0 ) ) )(0)
ここでは、本来は引数の式や関数はその場で展開されないが、わかりやすさのためその場で展開する。 評価順を変えても結果は同じという法則があるらしい。
まず、「(b:B) => b)」を一旦「id」と別名にし、Listのhead「1」を展開する。
foldLeft((2, 3), id)( (id,1) => (0 => g( head + b ) ) )(0) foldLeft((2, 3), id)( (id,1) => (0 => g( 1 + 0 ) ) )(0) foldLeft((2, 3), id)( (id,1) => (0 => id(1) ) )(0) // g = id foldLeft((2, 3), id)( (id,1) => (0 => 1) )(0) // 「(0 => 1)」は「0」を渡すと「1」を返す関数となる
次の、Listのhead「2」を展開する。
※ 今見ると「0 => g( head + b )」の0が固定なのが何故なのか気になる。
foldLeft((3), id)( (id, 2) => (0 => g( head + b ) ) )(0) foldLeft((3), id)( (id, 2) => (0 => g( 2 + 1 ) ) )(0) foldLeft((3), id)( (id, 2) => (0 => id(3) ) )(0) foldLeft((3), id)( (id, 2) => (0 => 3) )(0)
次の、Listのhead「3」を展開する。
foldLeft((), id)( (id,3) => (0 => g( head + 3 ) ) )(0) foldLeft((), id)( (id,3) => (0 => g( 3 + 3 ) ) )(0) foldLeft((), id)( (id,3) => (0 => id(6) ) )(0) foldLeft((), id)( (id,3) => (0 => 6) )(0)
最終的に「0」を渡すと「6」を返す関数となる。
(0 => 6)(0) = 6
なんとなく、このような感じで展開されているのかと思われる。
※ 勉強会のときは納得してたが、振り返ってみるとこれだと微妙な気がする。
13.answer.scalaの「foldLeftViaFoldRight_1」の解説は関数を変数に置き換えて説明していて、評価されるタイミングとかもきちんと表現している。