ｓｃａｌａ関数型デザイン＆プログラミング P51

Exercise3.11　foldLeftを使ってsum,product、リストの長さを計算する関数を記述せよ

def sum2(as:List[Int]):Int=
 foldLeft(as,0)(_+_)

def product2(as:List[Int]):Int=
 foldLeft(as,1)(_*_)

def length2[A](as:List[A]):Int=
 foldLeft(as,0)((b,_)=>b+1)

Exercise3.12　要素が逆に並んだリストを返す関数を記述せよ。
def rev[A](as:List[A]):List[A]=
 foldLeft(as,Nil:List[A])((b,a)=>Cons(a,b))

Exercise3.13　foldRigtからfoldLeftをつくる
def foldLeft2[A,B](as:List[A],z:B)(f:(B,A)=>B):B=
 {
 def g(a:A,b:B) :B =  f(b,a)
 foldRight(as,z)(g)
 }

foldLeftからfoldRightをつくる
def foldRight2[A,B](as:List[A],z:B)(f:(A,B)=>B):B=
 {
 def g(b:B,a:A) :B =  f(a,b)
 foldLeft(as,z)(g)
 }
としてみたが、そう簡単ではなかった。

3.13のfoldLeft2の正解は、
def foldLeftViaFoldRight[A,B](l: List[A], z: B)(f: (B,A) => B): B =
  foldRight(l, (b:B) => b)((a,g) => b => g(f(b,a)))(z)
なのだが、これを見ても、すぐには理解できない。
  foldRightの第一引数の型、List[A]でいいが、第二引数の型が、BのかわりにB=>B、つまり値ではなく、関数(b:B)=>bとするという考え方が、なかなか思いつかないところ。確かに、よく考えれば、型Bといえば、値であろうと関数であろうと論理的に問題はないことになる。
 したがって、次の引数である(A,B)=>BのBのところが、関数B=>Bに変わるので、(A,B=>B)=>（B=>B）となる。これは、(a,g) =>( b=>g(f(b,a))  )の部分で、gもB=>Bという型だし、b=>g(f(b,a))もB=>Bという型になっているから、これも問題ない。
　このB=>Bという関数が、foldRightで適用されたものは、foldRight(l, (b:B) => b)((a,g) => b => g(f(b,a)))であるが、これは、Bという型でなく、最終的にB=>Bの関数になるので、これだけでは、値が出てこない。そこで、この最終的にできた関数にzを引数としてやると
　foldRight(l, (b:B) => b)((a,g) => b => g(f(b,a)))(z)　となるようだ。

def foldRight(x:xs,z)(f)はf(x,foldRight(xｓ,z)(f)）となっているが、このzの部分がdelay関数と呼ばれている？もののようだ。再帰を繰り返すことで、delay関数にxが適用なっていき、蓄積していくイメージだろうか。これをもとにして、次のようになる。
foldRight(1:List(2,3),b=>b)(f)=f(1,foldRight(List(2,3),b=>b)(f))=f(1,f(2,foldRight(List(3),b=>b)(f)))
=f(1,f(2,f(3,b=>b)))
  ここで、fは(a,g)=>(b=>g(f(b,a))) より  f(3,b=>b)=(Ident(f(b,3))
 同様に fは(a,g)=>(b=>g(f(b,a))) より　 f(2,(f3,b=>b))=f(2,Ident(f(b,3)))=Ident(f(f(b,2),3))
 これを繰り返し f(1,(f(2,f(3,b=>b)))=Ident(f(f(f(b,1),2),3)))