Scala 函数式编程 https://github.com/fpinscala/fpinscala](https://github.com/fpinscala/fpinscala)
非严格non-strict 求值
非严格求值 : 函数属性
非严格求值的函数是说 这个函数可以选择不对它的入参求值.
这种参数叫 by name 参数, (普通的叫 by value)
只有少数语言支持 非严格求值, Java中的stream 就是非严格求值 , 不会频繁产生用完就可以扔的中间值
例子:
/**
*
* @param cond 条件
* @param onTrue 一个无参的函数
* @param onFalse 一个无参的函数
* @tparam A
* @return
*/
def ifMy[A](cond:Boolean,onTrue:()=>A,onFalse:()=>A):A={
if (cond)
onTrue()// 这时才调用函数求值
else
onFalse()//这时才调用函数求值
}
使用
ifMy(
12<22,
()=>println("true"),
()=>println("false")
)
一个表达式 未求值的形式 称为 thunk
比如:
()=>println("true")就是thunk
scala对此提供了专门的语法
函数声明入参时: onTrue:()=>A 简写为 onTrue: =>A 把括号换成空格
调用时: ()=>println("true") 简写为 println("true"), 不再传无参函数 而是表达式, 会自动包装成thunk
上面的函数声明就可以变成
def ifMy2[A](cond:Boolean,onTrue: =>A,onFalse: =>A):A={
if (cond)
onTrue// 括号没了
else
onFalse//括号没了
}
调用变成
ifMy2(
12<22,// 表达式, 但是传入的时候不会计算, 真的用到时才会计算
println("true"),
println("false")
)
用lazy 改进 :缓存
参数求值的结果不会被缓存, 如
def pair(i: => Int): (Int, Int) = {
(i, i)
}
调用
pair {
println("hi");
1 + 41
}
这样hi会打印2次, 每次用i都会重新计算
如果不想每次都算一次, 得用lazy,
lazy 的值的意思是, 真的用到时计算它的赋值, 之后都不用计算了
原来函数改成
def pair2(i: => Int): (Int, Int) = {
lazy val j = i // 这样不会求值
(
j,// 第一次使用j时会求值
j // 已经计算过了,用缓存
)
}
惰性列表Stream
Stream简单定义
sealed trait Stream[+A]
case object Empty extends Stream[Nothing]
case class Cons[+A](h: () => A, t: () => Stream[A]) extends Stream[A]
对比List
sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[+A](head: A, tail: List[A]) extends List[A]
看起来几乎一样, 除了 构造器接受 显式thunk, 这样传head和tail的时候不会求值,用()触发, 比如head() 这样才会强制求值
但是和前文说的那样, 这样不能缓存值, 再次需要取head ,再调用head() 会再次计算
用lazy写一个可缓存的, 更加智能地 构造Cons的函数
//注意: 这个cons的入参可以直接写普通的表达式, 但是不会马上被求值
def cons[A](hd: => A, tl: => Stream[A]): Stream[A] = {
lazy val head = hd// lazy 转了一道
lazy val tail = tl
Cons(() => head, () => tail)// 缓存在head tail里面了
}
Stream(2,12,39) 这样来创建Stream时 调用的apply方法:
def apply[A](as: A*): Stream[A] =
if (as.isEmpty)
empty
else
cons(as.head, apply(as.tail: _*)) // 都不会强制求值, 直到第一次用到
为了尾递归, 常用reverse
def toList: List[A] = {
@annotation.tailrec
def go(s: Stream[A], acc: List[A]): List[A] = s match {
case Cons(h,t) => go(t(), h() :: acc)
case _ => acc
}
go(this, Nil).reverse
}
reverse的实现是如下, 只有n的时间复杂度
override def reverse: List[A] = {
var result: List[A] = Nil
var these = this
while (!these.isEmpty) {
result = these.head :: result
these = these.tail
}
result
}
分离: 表达式的描述 和 表达式的计算
惰性求值 让我可以分离 表达式的描述 和 它的计算
因此可以写一个更大的表达式, 但是只计算其中的一部分
比如
def foldRight[B](z: => B)(f: (A, => B) => B): B =
this match {
case Some((h, t)) => f(h, t.foldRight(z)(f))
case None => z
}
注意 f 这个函数的第二个入参类型是=> B是 non-strict, 就是传进去时不会被计算, 在f里面真的用到的了才会计算
第二个入参是 t.foldRight(z)(f) 如果根本用不到的话, foldRight 马上就结束了, 不会再调用foldRight 来递归
而且, 因为是by-name入参,不会去计算, 这里即便递归多少次也不会栈溢出
使用的例子
def exists(p: A => Boolean): Boolean = {
/**
*
* @param a Stream元素
* @param z 是惰性求值
* @return
*/
def f (a:A, z: =>Boolean) : Boolean={
p(a) || z// 或的第一个是真 后一个就不会计算
}
foldRight(false)(f)
}
map:
def map[B](g: A => B): Stream[B] ={
def f [B](a:A,z: => Stream[B]) : Stream[B]={
cons(g(a),z)
}
foldRight(empty[B])(f)
}
filter:
def filter(g: A => Boolean): Stream[A] ={
def f (a:A,z: => Stream[A]) : Stream[A]={
if (g(a)){
cons(a,z)
}else{
z
}
}
foldRight(empty[A])(f)
}
Stream(1,2,3,4).map(_ + 10).filter(_ % 2 == 0)计算过程:
cons(1+10, Stream(2,3,4).map(_ + 10)).filter(_ % 2 == 0)
Stream(2,3,4).map(_ + 10).filter(_ % 2 == 0)
cons(12, Stream(3,4).map(_ + 10).filter(_ % 2 == 0))
Notice we do not fully instantiate the intermediate stream
无限流
val ones: Stream[Int] = cons(1, ones)
scala> ones.take(5).toList
res0: List[Int] = List(1, 1, 1, 1, 1)
scala> ones.exists(_ % 2 != 0)
res1: Boolean = true
斐波那契数列 0 1 1 2 3 5 8
def fibs():Stream[Int]={
def help(a:Int,b:Int):Stream[Int]={
cons(a,cons(b,help(a,b)))
}
help(0,1)
}
通用的
/**
* 用初始值和生产函数 生产可能无限的Stream[A]
* @param z 初始值
* @param f 用初始值 产生下一个stream元素和下一个初始值
* @return
*/
def unfold[A, S](z: S)(f: S => Option[(A, S)]): Stream[A] =
f(z) match {
case Some((h,s)) => cons(h, unfold(s)(f))
case None => empty
}
