scala関数デザイン＆プログラミング P５２

Exercise 3.16 各要素に１ずつたして整数のリストを返す関数を記述せよ

def add1(as:List[Int]):List[Int]=
 as match {
  case Nil => Nil
  case Cons(x,xs)=> Cons(x+1,add1(xs))
}

def add1f(as:List[Int]):List[Int]=
  foldRight(as:List[Int],Nil:List[Int])((a:Int,b:List[Int])=>Cons(a+1,b))


Exercise 3.17 List[Double]の各値をStringに変換する関数を記述せよ

def toStringD(as:List[Double]):List[String]=
 foldRight(as:List[Double],Nil:List[String])((a:Double,b:List[String])=>Cons(a.toString,b))

Exercise 3.18 リストの各要素を変更し、かつリストの構造をそのまま保つ総称関数mapを記述せよ。
def map[A,B}(as:List[A])(f:A=>B):List[B]=
 foldRight(as:List[A],Nil:List[B])((a:A,b:List[B])=>Cons(f(a),b))

Exercise 3.19 与えられた述語条件が満たされるまでリストから要素を削除するfilter関数を記述せよ。

def filter[A](as:List[A])(f:A=>Boolean):List[A]=
 foldRight(as:List[A],Nil:List[A])((a:A,b:List[A])=>(if (f(a)) Cons(a,b) else b ))

scala関数型デザイン＆プログラミング P51-2

Exercise 3.14 foledLeftまたはfoldRightをベースとしてappendを実装せよ。
def append[A](as:List[A],bs:List[A]):List[A]=
 foldLeft(reverse(as):List[A],bs:List[A])((b:List[A],a:A)=>Cons(a,b))

def append2[A](as:List[A],bs:List[A]):List[A]=
 foldRight(as:List[A],bs:List[A])((a:A,b:List[A])=>Cons(a,b))

foldRightのほうは、reverseが不要なのでシンプル

Exercise 3.15 複数のリストからなるリストを一つのリストとして連結する関数を記述せよ。
実行時間についてはよくわからないが、これでどうか？
def renketu[A](as:List[List[A]]):List[A]=
 foldRight(as:List[List[A]],Nil:List[A])((a:List[A],b:List[A])=>append(a,b))

ｓｃａｌａ関数型デザイン＆プログラミング 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)))

scala関数型デザイン＆プログラミング P５０

Exercise3.9　foldRightを使ってリストの長さを計算せよ
def length[A](as:List[A]):Int=
 foldRight(as,0)((a,b)=>b+1)

Exercise3.10 リスト再帰の総称関数foldLeftを記述せよ。
def foldLeft[A,B](as:List[A],z:B)(f:(B,A)=>B):B =
 as match {
      case Nil => z
      case Cons(x, xs) =>      f(foldLeft(xs, z)(f),x)
    }
これで、求められるけれど、末尾再帰でないので、だめなようだ。
あくまで、最後はfoldLeftの形でないとだめなので、正しい答は
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)
}

scala関数型デザイン＆プログラミング P45

Exercise 3.4  tailを一般化して、リストの先頭からｎ個の要素を削除するdropという関数に書き換えよ。
  def drop[A](l:List[A],n:Int):List[A] =
   l match {
   case Nil=>Nil
   case Cons(x,xs)=>if (n>1) drop(xs,n-1)
                    else xs
   }


Exercise 3.5 述語とマッチする場合に限り、Listからその要素までの要素を削除するdropWhileを実装せよ。
   def dropWhile[A](l:List[A],f:A=>Boolean):List[A] =
    l match {
     case Nil=>Nil
     case Cons(x,xs)=>if (f(x)) dropWhile(xs,f)
                      else l
    }

としてみたが、どうだろうか。

scala関数型デザイン＆プログラミング P44

Exercise3.2
　Listの最初の要素を削除する関数tailを実装せよ。

 def tail[A](as:List[A]):List[A]=
   as match {
     case Nil => Nil
     case Cons(x,xs)=>xs
}

Exercise3.3
 最初の要素を別の値と置き換えるsetHead関数を実装せよ。

def setHead[A] (as:List[A] , y:A ) : List[A] =
 as match {
   case Nil =>Nil
  case Cons(x,xs)=>Cons(y,xs)
}

Scala関数型デザイン＆プログラミング P34

Exercise2.3
カリー化では、引数２つの関数ｆが、fを部分的に適用する引数１つの関数に変換される。この場合も、コンパイルできる実装は１つだけである。この実装を記述せよ。
 def curry[A,B,C](f:(A,B)=>C):A=>(B=>C) =
   a=>(b=>f(a,b)) 　これは　a=>b=>f(a,b)という書き方でいいのだろうか。

　　curryの返り値としては、aを決めれば b=>cつまりb=>f(a,b)となる関数ができる　と理解していいのだろうか。
　
Exercise2.4
Curryによる変換を逆向きに行うuncurryを実装せよ。＝＞は右結合であるため、A=>(B=>C)はA=>B=>Cと記述できる。
　def uncurry{A,B,C](f:A=>B=>C):(A,B)=>C =
    (a,b)=>f(a)(b)
ｆは、aを引数として、b=>cとなる関数を返す関数
b=>cという関数がf(a)　つまり　　bを引数としてf(a)という関数がf(a)(b)を返すという意味で
とらえるということと理解したが、これでいいのだろうか。