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)))
