无限流与共递归
因为具有增量性质,我们所写的函数也适用于无限流,这里是一个由1组成的无限流的例子:
val ones: Stream[Int] = Stream.cons(1, ones)
尽管ones是无限的,我们目前为止写的函数只检测了Stream必要的部分,生产需要的输出。
练习 5.8
对ones稍微泛化一下,定义一个constant函数,根据给定值返回一个无限流。
def constant[A](a: A): Stream[A] = cons(a, constant(a))
练习 5.9
写一个函数生成一个整数的无限流,从n开始,然后n+1、n+2,等等。
def from(n: Int): Stream[Int] = cons(n, from(n + 1))
练习 5.10
写一个fibs斐波那契数列的无限流: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
写一个更加通用的构造流函数unfold。它接受一个初始状态,以及一个在生成的Stream中用于产生下一状态和下一个值的函数。
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
根据unfold函数来实现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实现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
}