严格求值和惰性求值（1）

非严格求值是函数的一种属性，称一个函数是非严格求值的意思是这个函数可以选择不对它的一个或者多个参数求值；相反，严格求值的函数总是对它的参数求值。在Scala中除非明确声明，否则任何函数都是严格求值的。
惰性列表：

sealed trait Stream[+A]

case object Empty extends Stream[Nothing]

case class Cons[+A](head: () => A, tail: () => Stream[A]) extends Stream[A]

object Stream {
  
  def empty[A]: Stream[A] = Empty
  
  def cons[A](h: => A, t: => Stream[A]): Stream[A] = {
    lazy val head = h
    lazy val tail = t
    Cons(() => head, () => tail)
  }

  def apply[A](as: A*): Stream[A] =
    if (as.isEmpty) Empty
    else cons(as.head, apply(as.tail: _ *))
}

练习 5.1
写一个可将Stream转换成List的函数，它会被强制求值。

  def toList: List[A] = this match {
    case Empty => Nil
    case Cons(h, t) => h() :: t().toList  
  }

练习 5.2
写一个take(n)函数返回Stream中前n个元素；写一个函数drop(n)返回第n个元素之后的所有元素

   def take(n: Int): Stream[A] = n match {
    case m if m <= 0 => Empty
    case _ => this match {
      case Empty => Empty
      case Cons(h, t) => Cons(h, () => t().take(n - 1))
    }
  }

  def drop(n: Int): Stream[A] = n match {
    case m if m <= 0 => this
    case _ => this match {
      case Empty => Empty
      case Cons(h, t) => t().drop(n - 1)
    }
  }

练习 5.3
写一个函数takeWhile返回从起始元素连续满足给定断言的所有元素。

  def takeWhile(f: A => Boolean): Stream[A] = this match {
    case Empty => Empty
    case Cons(h, t) => if (f(h())) Cons(h, () => t().takeWhile(f)) else t().takeWhile(f)
  }

练习 5.4
实现一个forAll函数，检查Stream中所有元素是否与给定的断言匹配。遇到不匹配的值应该立即终止遍历。

  def foldRight[B](b: => B)(f: (A, => B) => B): B = this match {
    case Empty => b
    case Cons(h, t) => f(h(), t().foldRight(b)(f))  
  }
  
  def forAll(f: A => Boolean): Boolean = this match {
    case Cons(h, t) => f(h()) && t().forAll(f)
    case _ => true
  }
  
  def forAll1(f: A => Boolean): Boolean =
    foldRight(true)((a, b) => f(a) && b)

练习 5.5
使用foldRight实现takeWhile。

  import Stream._

  def takeWhile1(f: A => Boolean): Stream[A] =
    foldRight(empty[A]){(a, b) =>
      if (f(a)) cons(a, b)
      else b
    }

练习 5.6
使用foldRight实现headOption。

  def headOption: Option[A] = this match {
    case Empty => None
    case Cons(h, t) => Some(h())
  }

  def headOption1: Option[A] = {
    val init: Option[A] = None
    foldRight(init){(a, _) =>
      Some(a)
    }
  }

练习 5.7
用foldRight实现map、filter、append和flatMap，append方法参数应该是非严格求值的。

  def map[B](f: A => B): Stream[B] = this match {
    case Empty => Empty
    case Cons(h, t) => cons(f(h()), t().map(f))
  }
  
  def map1[B](f: A => B): Stream[B] =
    foldRight(empty[B])((a, b) => cons(f(a), b))

  def filter(f: A => Boolean): Stream[A] = this match {
    case Empty => Empty
    case Cons(h, t) =>
      if (f(h())) cons(h(), t().filter(f)) else t().filter(f)
  }
  
  def filter1(f: A => Boolean): Stream[A] =
    foldRight(empty[A])((a, b) => if (f(a)) cons(a, b) else b)

  def append[B >: A](s: => Stream[B]): Stream[B] = this match {
    case Empty => s
    case Cons(h, t) => cons(h(), t().append(s))
  }
  
  def append1[B >: A](s: => Stream[B]): Stream[B] =
    foldRight(s)((a, b) => cons(a, b))

  def flatMap[B >: A](f: A => Stream[B]): Stream[B] = this match {
    case Empty => Empty
    case Cons(h, t) => f(h()).append(t().flatMap(f))
  }

  def flatMap1[B >: A](f: A => Stream[B]): Stream[B] =
    foldRight(empty[B])((a, b) => f(a).append(b))