严格求值和惰性求值-Stream

再之前介绍函数式数据结构的章节中我们介绍了List这种数据结构，其中我们再List中实现了map，flatMap，filter等方法，他们会接受一个函数并返回一个新的List。利用这些方法我们来看一个例子：

List(1, 2, 3, 4).map(_ + 10).filter(_ % 2 == 0).map(_ * 3).take(1)

我们可以将上面的表达式展开：

    List(11, 12, 13, 14).filter(_ % 2 == 0).map(_ * 3).take(1)
    List(12, 14).map(_ * 3).take(1)
    List(36, 42).take(1)
    List(36)

从上面的表达式的展开中我们可以看到总共求值了4次，因为内存共享的原因，我们知道4次求值的过程不会多余的复制列表消耗过多的内存，但是多次遍历列表却会消耗多余的时间性能。假如我们手写循环完全可以一边处理完这些逻辑，来看下代码：

  def handleList(li: immutable.List[Int]): immutable.List[Int] = {
    val res = mutable.ListBuffer.empty[Int]
    var n = 0
    while (n < li.length) {
      val temp1 = li(n) + 10
      if (temp1 % 2 == 0) {
        res.addOne(temp1 * 3)
        return res.toList
      }
      n += 1
    }
    res.toList
  }

上面的代码我们回到传统的循环来处理逻辑，虽然他没有List上使用map和filter使用那么形象， 但是他至少可以将所以的处理逻辑封装到一个循环中，不需要重复的遍历。那么不禁会有疑问，使用map和filter这种HOF天生就存在缺陷，无法处理长度大的列表？带着这个问题我们先来看下严格求值和非严格求值。
什么是严格求值？什么是非严格求值？
严格求值和非严格求值或者说惰性求值都是针对函数的属性。非严格求值是指函数可以不对他一个或者多个参数求值；严格求值指的是函数总是先要对他的参数进行求值。严格求值是编程语言的常态，大部分编程语言也只支持严格求值，在Scala中默认函数的参数也是严格求值的，假如你需要标识函数的入参不是严格求值的需要给参数前面加上=>。我们来看一个例子：

  def if2[A](cond: Boolean, onTrue: => A , onFalse: => A): A =
    if (cond) onTrue else onFalse

   if2(cond = false, sys.error("fail"), 3)

if2(cond = false, sys.error("fail"), 3)表达式并不会抛出错误，因为onTrue是惰性求值的，只有cond为true的时候他才会真正求值， 这时候才会抛出错误。因为上面我传入的cond为flase，所以惰性求值参数并不会真正执行。其实在日常用到的逻辑并和与也是惰性求值的，exp1 && exp2 假如exp1为false，exp2就不会被计算求值；exp1 || exp2 假如exp1为true， exp2也不会被计算求值。除了在真正需要的时候才求值这一个特性，惰性求值还有一个特性就是他不会缓存求值结果， 每一次引用都会重新计算求值。来看一个例子：

def maybeTwice(cond: Boolean, a: => Int): Int =
  if (cond) a + a else 0

println(maybeTwice(true, {println("hello"); 1}))

scala>hello
scala>hello
scala>2

从上面代码可知惰性求值入参被计算了两次，有什么方法可以避免这种情况吗？这个时候我们就需要使用lazy关键字了，来看下下面的代码：

  def maybeTwice1(cond: Boolean, a: => Int): Int = {
    lazy val b = a
    if (cond) b + b else 0
  }

println(maybeTwice1(true, {println("hello"); 1}))

scala>hello
scala>2

如上使用了lazy关键字缓存惰性求值之后，表达式只会被计算一遍，同时惰性求值的特性还会保留，只有真正应用表达式的时候他才会被计算求值。
好了， 现在我们可以来看下惰性列表（Lazy List or Stream）了，看看惰性化在函数式编程中是如何提升效率和模块化的。先来看下Stream的定义：

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](head: => A, tail: => Stream[A]): Stream[A] = {
    lazy val h = head
    lazy val t = tail
    Cons(() => head, () => tail)
  }

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

}

看看上面Stream的定义，我们会发现Stream的定义几乎和List的一样，唯一的区别就是Cons中的head和tail都是惰性求值的。那我们来做一些练习，看一看那些在List中出现的方法在Stream中如何定义：

  //实现take方法， 返回Stream的前n个元素
  def take(n: Int): Stream[A] = {
    if (n <= 0) Empty
    else this match {
      case Empty => Empty
      case Cons(h, t) => cons(h(), t().take(n - 1))
    }
  }

  //实现drop方法，返回除去前n个元素之外的剩下的元素
  def drop(n: Int): Stream[A] = {
    if (n <= 0) this
    else this match {
      case Empty => Empty
      case Cons(h, t) => t().drop(n - 1)
    }
  }

  //实现takeWhile， 返回Stream从起始元素连续满足给定断言的所有元素
  def takeWhile(f: A => Boolean): Stream[A] = this match {
    case Cons(h, t) if f(h()) => cons(h(), t().takeWhile(f))
    case _ => Empty
  }

看完这些方法定义更可以看到Stream和List其实是一样的，只是List中的表达式是严格求值的，Stream中的表达式是惰性求值的，我们也可以称Stream为LazyList。那么利用了惰性求值特性Stream和List究竟有什么区别？其精华就在于利用惰性化可以实现描述和求值分离， 也就是说可以使用表达式描述函数的逻辑，单具体需要求值的时候才真正对他进行计算求值，这也其实是函数式编程的主题之一：关注分离。我们可以使用Stream来实现exists方法，exists需要达到的效果是遇到满足断言的元素就跳出递归，而不是一直递归下去。我们看下exists是如何实现的：

  //实现exist, 遇到满足断言的元素返回true
  def exists(f: A => Boolean): Boolean = this match {
    case Empty => false
    case Cons(h, t) => f(h()) || t().exists(f)
  }

我们知道Stream中的元素多是惰性的，并不会正在被求值，而且||方法也是惰性的，也就是说在f(h())求值为true的时候，后面的递归t().exists(f)根本就不会被计算求值。想想在前面处理List的时候我们得出的结论模式匹配+递归调用可以被折叠算法代替，那么在Stream中是不是也是一样的呢？先来看下在Stream中如何来实现折叠算法：

  //实现foldRight，对Stream进行折叠
  def foldRight[B](z: => B)(f: (A, => B) => B): B = this match {
    case Empty => z
    case Cons(h, t) => f(h(), t().foldRight(z)(f))  
  }

这里看到Stream和List对于foldRight的实现基本是一致的，唯一的区别还是惰性求值的区别。其中函数f中的第二个参数=> B是惰性求值的，也就是假如f选择不对第二个参数求值， 那么递归将会提前终止。我们来看下如何利用折叠算法foldRight来实现前面实现的方法：

  //实现toList方法，将Stream转换成List，其中Stream中的表达式会强制被求值
  def toList: List[A] = this match {
    case Empty => Nil
    case Cons(h, t) => LCons(h(), t().toList)
  }

  def toList1: List[A] =
    foldRight(Nil: List[A])(LCons(_, _))

  //实现take方法， 返回Stream的前n个元素
  def take(n: Int): Stream[A] = {
    if (n <= 0) Empty
    else this match {
      case Empty => Empty
      case Cons(h, t) => cons(h(), t().take(n - 1))
    }
  }

  def take1(n: Int): Stream[A] =
    foldRight((n, empty[A])) {
      case (_, (m, b)) if m <= 0 => (0, b)
      case (a, (m, b)) => (m - 1, cons(a, b))
    }._2

  //实现drop方法，返回除去前n个元素之外的剩下的元素
  def drop(n: Int): Stream[A] = {
    if (n <= 0) this
    else this match {
      case Empty => Empty
      case Cons(_, t) => t().drop(n - 1)
    }
  }

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

  //实现takeWhile， 返回Stream从起始元素连续满足给定断言的所有元素
  def takeWhile(f: A => Boolean): Stream[A] = this match {
    case Cons(h, t) if f(h()) => cons(h(), t().takeWhile(f))
    case _ => Empty
  }

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

  //实现exist, 遇到满足断言的元素返回true
  def exists(f: A => Boolean): Boolean = this match {
    case Empty => false
    case Cons(h, t) => f(h()) || t().exists(f)
  }

  def exists1(f: A => Boolean): Boolean =
    foldRight(false)((a, b) => f(a) || b)

我们可以对上面的方法进行验证， 查看foldRight是如何提前终止递归的。为了强化对foldRight的认识我们再来做一下练习：

  //实现forAll，检查Stream中所有的元素是否满足断言，假如遇到不满足断言的元素立即终止遍历
  def forAll(f: A => Boolean): Boolean = this match {
    case Empty => true
    case Cons(h, t) => f(h()) && t().forAll(f)
  }
  
  def forAll1(f: A => Boolean): Boolean =
    foldRight(true)((a, b) => f(a) && b)

  //实现headOption，返回Stream中的第一个元素
  def headOption: Option[A] = this match {
    case Empty => None
    case Cons(h, t) => Some(h())
  }

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

  //实现map
  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))

  //实现filter
  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)

  //实现append
  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)(cons(_, _))

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

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

上面方法除去headOption之外，其他的方法的返回值都是Stream，也就是到最后只是对算法逻辑的描述，并没有真正的出发求值。我们重回文章开头的例子并使用Stream来操作，来看下Stream是如何避免多余的遍历的：

    Stream(1, 2, 3, 4).map(_ + 10).filter(_ % 2 == 0).map(_ * 3).take(1).toList
    cons(11, Stream(2, 3, 4).map(_ + 10)).filter(_ % 2 == 0).map(_ * 3).take(1).toList
    Stream(2, 3, 4).map(_ + 10).filter(_ % 2 == 0).map(_ * 3).take(1).toList
    cons(12, Stream(3, 4).map(_ + 10)).filter(_ % 2 == 0).map(_ * 3).take(1).toList
    cons(12, Stream(3, 4).map(_ + 10).filter(_ % 2 == 0)).take(1).toList
    cons(12, Stream(3, 4).map(_ + 10).filter(_ % 2 == 0).take(0)).toList
    cons(12, empty).toList
    List(12)

仔细观察上面的过程， 需要检查整个过程到底遍历了几遍，整个过程中产生了几次中间变量Stream。正式因为Stream的这种增量特性，Stream又被称为第一循环，他可以按需求值， 他既不会多余循环也不会产生多余的中间变量，所以利用Stream可以将一个复制的逻辑拆散成多个函数子的组合，而不必去担心重复循环和多余的中间变量。让我们再来看一个练习：

  //实现find，遇到第一个匹配的元素之后返回并退出递归
  def find(f: A => Boolean): Option[A] = this match {
    case Empty => None
    case Cons(h, t) => if (f(h())) Some(h()) else t().find(f)  
  }

  def find1(f: A => Boolean): Option[A] =
    foldRight(None: Option[A])((a, b) => if (f(a)) Some(a) else b)

  def find2(f: A => Boolean): Option[A] =
    filter(f).headOption

从上面的练习中可以find既可以使用传统的方式实现，也可以使用filter和headOption来实现，虽然原定义中filter会遍历所有的元素，但是因为Stream惰性求值的特性所以这样组合实现的效果是一样的。

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 202,802评论 5赞 476
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,109评论 2赞 379
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 149,683评论 0赞 335
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,458评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,452评论 5赞 364
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,505评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,901评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,550评论 0赞 256
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,763评论 1赞 296
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,556评论 2赞 319
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,629评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,330评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,898评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,897评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,140评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,807评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,339评论 2赞 342