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

Exercise　６．５　mapを使ってdoubleを実装し直せ

val rng = new scala.util.Random

trait RNG{
def nextInt:(Int,RNG)
}

case class SimpleRNG(seed: Long) extends RNG {
 def nextInt:(Int,RNG) = {
   val newSeed =(seed * 0x5DEECE66DL+0xBL) & 0xFFFFFFFFFFFFL
   val nextRNG= SimpleRNG(newSeed)
   val n = (newSeed >>>16).toInt
    (n,nextRNG)
 }
}

def nonNegativeInt(rng: RNG): (Int, RNG) = {
  val (i, r) = rng.nextInt
  (if (i < 0) -(i + 1) else i, r)
}

type Rand[+A]=RNG=>(A,RNG)

def map [A,B](s:Rand[A])(f:A=>B):Rand[B]=
 rng=>{
 val (a,rng2) = s(rng)
  (f(a),rng2)
}

def _double(rng:RNG):Rand[Double] =
 map (nonNegativeInt)(_/(Int.MaxValue.toDouble+1))

val (a,rng2) = _double(rng)(rng)で確認

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

Exercise 6.4 ランダムな整数のリストを生成する関数を記述せよ。
解答によれば
def ints(count: Int)(rng: RNG): (List[Int], RNG) =
  if (count <= 0)
    (List(), rng)
  else {
    val (x, r1)  = rng.nextInt
    val (xs, r2) = ints(count - 1)(r1)
    (x :: xs, r2)
  }
以下rngは略して、トレースしてみると
ints(0)()=(List(),rng)
ints(1)()=(x::List(), )
ints(2)()=(x::x::List(),)
と続くことになるようだ。

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

Exersise　5.12　unfoldを使ってmap,take,takeWhile,zipWith,zipAllを実装せよ。zipAll関数ではどちらかのストリームに要素が残っている限り、評価を続ける必要がある。(ストリームが完全に評価されたかどうかを示すのにOptionを使用する）

 def map3[B](f:A=>B):Stream[B] =
unfold(this)( p=>p match {case Cons(a,as)=>Some(f(a()),as())
 case _ => None
   })
省略形にすると
 def map4[B](f:A=>B):Stream[B] =
   unfold(this) {case Cons(a,as)=>Some(f(a()),as())
                 case _ => None
}


def take2(n:Int):Stream[A]=
   unfold((this,n)) {
  case (Cons(a,as),n) if (n>0) => Some( (a(),(as(),n-1))   )
  case _ => None
}


def takeWhile4(p:A=>Boolean):Stream[A] =
  unfold(this) {
  case (Cons(a,as)) if (p(a())) => Some(a(),as())
  case _ => None
  }

def zipWith2[A](as:Stream[A],bs:Stream[A])(f:(A,A)=>A):Stream[A]=
  unfold(as,bs) {
  case (Cons(a,as),Cons(b,bs)) => Some(f(a(),b()),(as(),bs()))
  case (_,_)=>None
}


def zipAll[B](s2:Stream[B]):Stream[(Option[A],Option[B])] =
  unfold(this,s2) {
  case (Cons(a,as),Cons(b,bs)) => Some((Some(a()),Some(b())),(as(),bs()))
ここで、はたと止まってしまった。
　case(Empty,Cons(b,bs))=>Some、、、、のところがどうしてもうまくいかない。
解答のプログラムもコンパイルしてみたが、エラーが発生する。

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

Exercise 5.11 より汎用的なunfoldを記述せよ

解答をみるとf(z) matchとしている。柔軟な発想が必要なようだ。
def unfold[A, S](z: S)(f: S => Option[(A, S)]): Stream[A] =
  f(z) match {
    case Some((h,s)) => cons(h, unfold(s)(f))
    case None => empty
  }
これまで、でてきた生成関数に共通する部分をみると
　def 自分自身（引数１）＝cons(h,自分自身（引数２））
となっているので、引数１から引数２への変換のためにfという関数を用意し、同時にそのfの関数でhも求めるようにしている。

Exercise　5.12　fibs、from、constant,onesをunfoldを使って実装する。
   def fibs4(n1:Int,n2:Int)=
   unfold((n1,n2))( ((nn1,nn2)) => Some( (nn1,(nn2,nn1+nn2) ) )  )
としたが、なぜかエラー　１引数の関数にせよ。そのためにcaseパターンを使うということか？
解答のとおり
def fibs3(n1:Int,n2:Int)=
   unfold((n1,n2))( p=>p match  {case  (nn1,nn2) => Some( (nn1,(nn2,nn1+nn2) ) )  }  )
とするとうまくいく。　１引数としてpをとり、その戻り値がp match  {case  (nn1,nn2) => Some( (nn1,(nn2,nn1+nn2) ) )  } ということになるんだろうか。回りくどい感じがすると思うのは私だけだろうか。
省略形が
def fibs3(n1:Int,n2:Int)=
   unfold((n1,n2)) {case  (nn1,nn2) => Some( (nn1,(nn2,nn1+nn2) ) )  }
だとか。
　これ以降はmatchは使わなくてもよいようだ。
   def from2(n:Int):Stream[Int]=     unfold(n)( n=>Some((n,n+1)) )
def constant2[A](a:A):Stream[A]= unfold(a)(a=>Some(  (a , a )   ) )
def ones:Stream[Int]=unfold(1)(i=>Some((i,i)))

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

Exercise　5.8　指定された値の無限ストリームconstant関数を記述せよ
  def constant[A](a:A):Stream[A] =cons(a,constant(a))
解答は、次のようになっていた。これより効率のいい方法ということのようだ。
def constant[A](a: A): Stream[A] = {
  lazy val tail: Stream[A] = Cons(() => a, () => tail)
  tail
}

Exercise 5.9 nではじまり、n+1,n+2、、と続く無限ストリームを生成する関数を記述せよ
  def from(n:Int):Stream[Int] = cons(n,from(n+1))

Exercise 5.10 フィボナッチ数列の無限ストリームを生成するfibs関数を記述せよ
def fibs(n1:Int,n2:Int):Stream[Int]=cons(n1,cons(n2,fibs(n1+n2,n1+2*n2)))
解答は
val fibs = {
  def go(f0: Int, f1: Int): Stream[Int] =
    cons(f0, go(f1, f0+f1))
  go(0, 1)
}
これを見て
def fibs2(n1:Int,n2:Int):Stream[Int]=cons(n1,fibs2(n2,n1+n2))
でもいいのではないかと思ったが。。。

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

Exercise 5.4 Streamの要素のうち、指定された述語とマッチするものをすべてチェックするforAllを実装せよ。
def forAll(p:A=>Boolean):Boolean =
 foldRight(true)((a,b)=p(a)&&b)


Exercise 5.5 foldRightを使ってtakeWhileを実装せよ
 def takeWhile3(p:A=>Boolean):Stream[A] =
  foldRight(empty[A])((a,st)=>if p(a) cons(a,st) else st)
最後をstにしたが、解答はemptyだった。そうしないと、いったんfalseになっても、trueになると
前のStreamに追加されていく。（あとで出てくるfilterだとそれでいいが）

Exercise 5.6 foldRigthを使ってheadOptionを実装せよ
  def headOption:Option[A] =
 foldRight2(None:Option[A])( (a,_) =>if (a!=Nil) Some(a) else None )
最初foldRightの引数のNoneにOption[A]をつけなかったところ、エラーがでた。このへんの必要性について、いまいち理解できてない。
解答は
def headOption: Option[A] =
  foldRight(None: Option[A])((h,_) => Some(h))
となっていた。わざわざifはつける必要がないといことだ。hがNilでもNoneとなるようだ。

Exercise 5.7 foldRightを使って、map,filter,append.flatMapを実装せよ

def map[B](f:A=>B):Stream[B] =
 foldRight2(empty[B])( (a,st) => cons(f(a),st)  )

def filter(f: A => Boolean): Stream[A] =
 foldRight2(empty[B])( (a,st) => if (f(a)) cons(a,st) else st)

def append[A](as:Stream[A],bs:Stream[A]):Stream[A]=
 as.foldRight2(bs)((a,b)=>cons(a,b))

としたが、これでは引数を非正格にという条件にあわないので、間違い。

正しくは

 def append[B>:A] (bs: => Stream[B]):Stream[B]=

 foldRight2(bs)((a,b)=>cons(a,b))

ということだった。変位についても考慮して上位のBの型にしないとだめだそうだ。変位の指定ははまだ理解が難しい。

def flatMap[B](f:A=>Stream[B]):Stream[B] =
 foldRight(empty[B])( (a,st)=>cons(f(a).head,st)  ) 

ということは無理だったheadのような使いかたはできない

正解は  foldRight(empty[B])((a,st) => f(a).append(st))

appendを使うことは気づかなかった

scala関数型デザイン＆プログラミング P86~87

Exercise5.2　Streamの先頭からn個の要素を取り出す関数take(n)とｎ個の要素をスキップするdrop(n)関数を実装せよ

 def take(n:Int):Stream[A] = this match {
    case Cons(x,xs) if n>1 => cons(x(),xs().take(n-1))
    case Cons(x,_) if n==1 => cons(x(),empty)
    case Empty => Stream()
}
これをprintln(Stream(1,2,3,4).take(2).toList)で確認してみた

  def drop(n:Int):Stream[A]=this match {
  case Cons(x,xs) if n>0 => xs().drop(n-1)
  case Cons(x,xs) if n==0 => cons(x(),xs())
  case Empty => Stream()
  }
println(Stream(1,2,3,4).drop(3).toList)で確認したが、これだと、無駄があったようだ。
def drop2(n: Int): Stream[A] = this match {
  case Cons(_, t) if n > 0 => t().drop(n - 1)
  case _ => this
}
解答はこうなっていた。

Exercise5.3　Streamの先頭から指定された述語とマッチする要素をすべて取り出す　takeWhile関数を記述せよ
def takeWhile(f: A => Boolean): Stream[A] = this match {
  case Cons(h,t) if f(h()) => cons(h(), t() takeWhile f)
  case _ => empty
}
これは、なぜかprintln(Stream(1,2,3,4).takeWhile2(_>2).toList)とするとList()と表示される。
よく考えたら、先頭から～マッチしないとだめなわけだから、_>2でなく_<3などで試せばいいわけだ。