再びExercise 3.13

前回の記事の疑問点で返答をもらったので、参考にしながらExercise3.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)

いったん、foldLeftの最後の引数(z)を忘れてB=>Bを返す下記の関数で考える。

foldLeft(l, (b:B) => b)((g,a) => b => g(f(a,b))):B=>B

これでも長くて混乱するので下記に置き換える。

• id=(b=>b)に置き換え
• F=(g,a) => b => g(f(a,b)) に置き換え

foldLeft(l, (b:B)=>b)((g,a) => b => g(f(a,b))) 

↓

foldLeft(l, id)(F) // Fはidとリストの要素aを受け取るとb => g(f(a,b))になる

ちなみにg=idになる理由は

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(l, id)(F)の場合なら

foldLeft(l, id)(F): B=>B = l match {
    case Nil => id
    case Cons(x, xs) => foldLeft(xs, F(id, x))(F)
}

のようになるためかと思われる。

ここから、l = List(1,2,3)の場合を見ていくと

foldLeft(List(1,2,3), id)(F)  // Fは(アキュムレータ,a)をとる関数でaにはListのヘッダーが渡される
foldLeft(List(2,3), F(id, 1))(F)  // a=1、アキュムレータ=F(id, 1)
foldLeft(List(3), F(F(id, 1), 2))(F)  // a=2、アキュムレータ=F(F(id, 1),2)
foldLeft(List(), F(F(F(id, 1), 2),3))(F)  // a=3、アキュムレータ=F(F(F(id, 1),2),3)
F(F(F(id, 1), 2),3) // 空Listの場合

で、ここからFを展開する。
※ f(a,b) = a + b より　F(g,a) = b => g(a+b)

F(F(F(id, 1), 2),3)
F(F((b1 => id(1+b1)), 2),3) // Fに引数(id, 1)を渡すとb1 => id(1+b1)になる
// id2=(b1 => id(1+b1)) つまり id2(b1) = id(1+b1)
F(b2 => id2(2 + b2),3)
// id3=(id2(2 + b2)) つまり id3(b2) = id2(2+b2)
b3 => id3(3 + b3)

ここまでで foldLeft(l, (b:B)=>b)((g,a) => b => g(f(a,b))) の戻り値は b3 => id3(3 + b3) の関数になる。

もともとやりたかった下記をやるため

foldRightViaFoldLeft_1(List(1,2,3), 0)(\_+\_)

この関数の引数b3にもともとの引数z=0を渡すと

0 => id3(3 + 0)
id3(3)
id3(3) = 3 => id2(2+3)
id2(5)
id2(5) = 5 => id(1+5)
id(6)
6 // id = (b=>b) = (6=>6)

きちんとfoldRightと同じ動きになる。 これで納得です！