無限流與共遞歸
因為具有增量性質是己,我們所寫的函數(shù)也適用于無限流白筹,這里是一個由1組成的無限流的例子:
val ones: Stream[Int] = Stream.cons(1, ones)
盡管ones是無限的,我們目前為止寫的函數(shù)只檢測了Stream必要的部分兑牡,生產需要的輸出央碟。
練習 5.8
對ones稍微泛化一下,定義一個constant函數(shù)均函,根據(jù)給定值返回一個無限流亿虽。
def constant[A](a: A): Stream[A] = cons(a, constant(a))
練習 5.9
寫一個函數(shù)生成一個整數(shù)的無限流,從n開始苞也,然后n+1洛勉、n+2,等等如迟。
def from(n: Int): Stream[Int] = cons(n, from(n + 1))
練習 5.10
寫一個fibs斐波那契數(shù)列的無限流:0收毫,1,1殷勘,2此再,3,5玲销,8输拇,等等。
def fibs: Stream[Int] = {
def loop(prev: => Int, curr: => Int): Stream[Int] =
cons(prev, loop(curr, prev + curr))
loop(0, 1)
}
練習 5.11
寫一個更加通用的構造流函數(shù)unfold贤斜。它接受一個初始狀態(tài)策吠,以及一個在生成的Stream中用于產生下一狀態(tài)和下一個值的函數(shù)。
def unfold[A, S](z: S)(f: S => Option[(A, S)]): Stream[A] = f(z) match {
case None => Empty
case Some((a, s)) => cons(a, unfold(s)(f))
}
練習 5.12
根據(jù)unfold函數(shù)來實現(xiàn)fibs瘩绒、from猴抹、constant和ones。
val ones1: Stream[Int] = unfold(1)(Some(1, _))
def constant1[A](a: A): Stream[A] = unfold(a)(Some(a, _))
def from1(n: Int): Stream[Int] =
unfold(n)(s => Some(s, s + 1))
def fibs1: Stream[Int] =
unfold((0, 1)){
case (prev, curr) => Some((prev, (curr, prev + curr)))
}
練習 5.13
使用unfold實現(xiàn)map锁荔、take蟀给、takeWhile、zipWith以及zipAll
def map1[B](f: A => B): Stream[B] =
unfold(this){
case Empty => None
case Cons(h, t) => Some(f(h()), t())
}
def take1(n: Int): Stream[A] =
unfold((n, this)){
case (m, _) if m <= 0 => None
case (_, Empty) => None
case (a, Cons(h, t)) => Some(h(), (a - 1, t()))
}
def unCons[B >: A](s: Stream[B]): Option[(B, Stream[B])] = s match {
case Empty => None
case Cons(h, t) => Some(h(), t())
}
def takeWhile2(f: A => Boolean): Stream[A] =
unfold(unCons(this)){
case Some((h, t)) if f(h) => Some(h, unCons(t))
case _ => None
}