SE情報技術研究会’s blog

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

2015-10-03 第5回 関数型プログラミング勉強会の簡単なまとめ

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」の解説は関数を変数に置き換えて説明していて、評価されるタイミングとかもきちんと表現している。