hangscer

严格求值和惰性求值

2017/02/11

5 严格求值和惰性求值

请思考以下这段程序:
List(1,2,3,4).map(_+10).filter(_%2==0).map(3*_)
上面的表达式中map(_+10)会产生一个中间列表list1,然后再对中间列表进行filter(_%2==0)操作,这个filter也会产生另一个列表,等等。换句话说,每次转换都产生了临时列表为下次转换的输入,之后便被立即丢弃。

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

每次转换都会生成临时列表。
那么如果我们对一系列的转换融合成单个函数而避免产生临时数据结构岂不是更好吗?
我们可以通过使用非严格求值(non-strictness)来实现这种自动循环的融合物。非严格求值(惰性求值)是一项提升函数式编程效率和模块化的基础技术。

5.1 严格和非严格函数

非严格求值是函数的一种属性,这个函数可以选择不对它的一个或者多个参数求值。相反,一个严格求值的函数总是对它的参数求值。大部分编程语言也只支持严格求值。
def suquare(x:Double):Double=x*x
当调用square(41.0+1.0)时,square函数将接收到完成求值的42.0作为参数。因为它时严格求值的。
或者说,if-else语句,对条件参数是严格求值的,对于true或者false分支是非严格求值的。

1
2
3
4
def if2[A](cond:Boolean,onTrue:()=>A,onFalse:()=>A)={
if(cond) onTrue() else onFalse()
}
if2(true,()=>println("AA"),()=>println("BB"))

在每一个非严格求值参数的地方传入一个无參函数,然后在方法体里显式的调用它。Scala提供了更好的语法:

1
2
3
def if2[A](cond:Boolean,onTrue: =>A,onFlase: =>A):A=
if(cond) onTrue else onFalse
if2(true,{println("AA");"AA"},{println("BB");"BB"})

Scala不会去缓存一个参数的求值结果。用lazy,将导致Scala延迟对这个变量求值,它会缓存结果。
Scala中非严格求值的函数接收的参数是传名参数(by name)而非传值参数(by value)。

5.2 一个拓展例子:惰性列表

那么基于流(Stream)的转换是怎么通过使用惰性化融合成一次操作的?以下是Stream的简单定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
sealed trait Stream[+A]
case object Empty extends Stream[Nothing]
case class Cons[+A](h:()=>A,t:()=>Stream[A]) extends Stream[A]
// non-empty stream consist of non-empty head and non-empty tail,which is thunk,like call by name,but not this
object Stream{
def cons[A](hd: =>A,t1: =>Stream[A]):Stream[A]={
lazy val head=hd
lazy val tail=t1
Cons(()=>head,()=>tail)
}
def empty[A]:Stream[A]=Empty
def apply[A]:(as:A*):Stream[A]=
if(as.isEmpty) empty else cons(as.head,apply(as.tail: _*))
}

这个类型看上去和List差不多,除了Cons数据构造器接收显式的thunk(()=>A()=>Stream[A])。
下面是一个以可选的方式抽取Stream的head的函数:

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

注意,我们必须显式的调用h()来对h强制求值,不这样做的话!代码会像List一样。Stream直到这部分真正需要时,才求值(所以不会对Cons的tail求值)。

5.2.1 对Stream保持记忆,避免重复运算

我们希望能缓存Cons节点的值,一旦它们被强制求值。如果我们直接用Cons数据构造器,比如下面的代码,实际上运算了2次expensive(x):

1
2
3
val x=Cons(()=>expensive(x),t1)
val h1=x.headOption
val h2=x.headOption

通常定义更智能(smart)的构造器来避免这个问题,智能smart构造器的写法习惯上与普通的数据构造器相似,但受首字母小写(cons)。这里cons构造器负责将传名参数纪录到headtail,它确保thunk只运行一次。后续调用会返回已缓存的lazy val

1
2
3
4
5
def cons[A](hd: =>A,t1: =>Stream[A]):Stream[A]={
lazy val head=hd
lazy val tail=t1
Cons(()=>head,()=>tail)
}

注意

1
2
3
4
5
6
7
8
9
10
11
12
def recursive[A](list:List[A]):A=list match{
case h::Nil=>h
case h::t=>{
println(s"head:${h}")
recursive(t)
}
}
def cons[A](hd: =>A,t1: =>A)={
lazy val head=hd // <<function0>
lazy val tail=t1 // <<function0>
}
cons(1,recursive(List(1,2,3,4,5)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def recursive[A](list:List[A]):A=list match{
case h::Nil=>h
case h::t=>{
println(s"head:${h}")
recursive(t)
}
}
def cons[A](hd: =>A,t1: =>A)={
lazy val head=hd // <<function0>
lazy val tail=t1 // <<>function0>
head
}
cons(1,recursive(List(1,2,3,4,5)))
//output 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def recursive[A](list:List[A]):A=list match{
case h::Nil=>h
case h::t=>{
println(s"head:${h}")
recursive(t)
}
}
def cons[A](hd: =>A,t1: =>A)={
lazy val head=hd // <<function0>
lazy val tail=t1 // <<>function0>
tail
}
cons(1,recursive(List(1,2,3,4,5)))
//output
head:1
head:2
head:3
head:4

上式中cons(1,recursive(List(1,2,3,4,5)))传递给cons(hd: =>A,tl: =>A),相当于:def hd=1def tl=recursive(List(1,2,3,4,5))
上图中List(1,2,3,4,5)实例化发生在哪个时刻呢?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def recursive[A](list:List[A]):A=list match{
case h::Nil=>h
case h::t=>{
println(s"head:${h}")
recursive(t)
}
}
def cons[A](hd: =>A,t1: =>A)={
lazy val head=hd // <<function0>
lazy val tail=t1 // <<>function0>
println("aa")
// tail
}
cons(1,recursive(List(1,2,3,4,5)))
//output aa

1
2
3
4
5
6
7
8
def cons[A](hd: =>A,t1: =>A)={
lazy val head=hd // <<function0>
lazy val tail=t1 // <<>function0>
println("aa")
tail
}
cons(1,recursive(println("cc");List(1,2,3,4,5)))
//output aa cc ......

Scala负责包装thunk中传给cons的参数,所以as.headapply(as.tail:_*)表达式不会求值,直到在Stream中被强制求值(Scala函数式编程P59)

TIP:Scala用子类型来表示数据构造器,但需求几乎总是想要推断为Stream类型,而不是Cons或者Empty类型。让智能构造器返回基本类型在Scala中很常见。
练习

写出将Stream转化为List的函数toListRecursive。取Stream中前n个元素的take函数。取Stream中第n个元素之后的所有元素的函数drop。写出返回Stream中从起始元素连续满足给定断言的所有元素的函数takeWhile

5.3 把函数的描述与求值分离

函数式编程的主题之一是关注分离(separation of concerns)。希望将计算的描述与实际运行分离。比如一等函数,捕获函数体内的运算逻辑,只有在接收到参数时才去执行它。使用Option捕获的错误,而决定对它做什么是一个分离的关注点。对于Stream,可以构建一个产生一系列元素的计算逻辑直到实际需要这些元素时才去运行。
一般而言,惰性化对一个表达式分离了它的描述和求值。
例如,函数exists检查了Stream中是否存在元素满足某个条件:

1
2
3
4
5
6
7
8
sealed trait Stream[+A]{
import Stream._
def exists(p:A =>Boolean):Boolean=this match{
case Cons(h,t)=>p(h()) || t().exists(p)
case _=>false
}
//...other methods
}

注意||对它的第二个参数是非严格求值。如果p(h())返回true,则提前终止遍历。另外,Stream的tail也是lazy val,不仅仅提前终止,而且tail压根没有被求值。

exits用了显式的递归。还可以以更通用的foldRight方式来实现递归:

1
2
3
4
def foldRight[B](z: =>B)(f:(A, =>B)=>B):B=this match{
case Cons(h,t)=>f(h(),t().foldRight(z)(f))
case _=>z
}

与List的foldRight相似,组合函数f对它的第二个参数(=>B)是非严格求值(传名)。如果f选择不对第二个参数求值,则提前终止遍历。以下是用foldRight实现的exists函数:

1
2
def exists_(p:A=>Boolean):Boolean=
foldRight(false)((a,b)=>p(a)||b)

这里b是对Stream的tail进行fold的未求值的递归步骤,如果p(a)true,则b不会被计算,计算终止。

练习

实现forAll函数,检查Stream中所有元素是否与给定的断言相满足。遇到不匹配的值应该立即终止遍历并返回。
def forAll(p:A=>Boolean):Boolean

练习

实现map和filter函数。

跟踪Stream程序

Stream(1,2,3,4).map(_+10).filter(_%2==0).toList该程序的分步解读:

用于生成单个元素的map函数与用于测试元素是否被2整除的filter函数之间交替进行。并不会完全实例化map运算结果的中间Stream,Stream亦可描述为”一等循环“(first-class loops)。这是Stream转换的增量性质(incremental)。

5.4 无限流

正因为具有增量性质,Stream亦可生成无限流(infinite stream)。下面是由1组成的无限流的例子:

1
2
val ones:Sream[Int]=Stream.cons(1,ones)
println(ones.take(3).toListRecursive)

练习

ones泛化,定义格constant函数,根据给定值返回一个无限流

练习

写一个函数生成整数无限流,从n开始,然后n+1 n+2…:

练习

fibs是生成斐波那契数列的无限流:0 1 1 2 3 5 8...

练习

写一个更为通用的构造流的函数unfold。它接受一个初始状态以及一个在生成的Stream中用于产生下一个状态(值)的函数以及使用unfold实现from:
def unfold[A,S](z:S)(f:S=>Option[(A,S)]):Stream[A]