package cn.edu.jxnu.scala.fb
/**
* @author 梦境迷离
* @version 1.0, 2019-05-18
*/
object laziness extends App {
lazy val stream = Stream.apply(1, 2, 3, 4, 5, 6, 7)
Console println "stream => " + stream
Console println "headOption => " + stream.headOption
Console println "toList => " + stream.toList
Console println "take => " + stream.take(1)
Console println "drop => " + stream.drop(1)
Console println "takeWhile => " + stream.takeWhile(_.equals(1))
Console println "exists => " + stream.exists(_.equals(2))
Console println "exists2 => " + stream.exists2(_ == 2)
Console println "forAll => " + stream.forAll(_ > 0)
Console println "takeWhile2 => " + stream.takeWhile2(_.equals(1))
Console println "map => " + stream.map(_ + 1) //对每个元素进行+1
Console println "filter => " + stream.filter(_ > 3) //取出大于3的
Console println "append => " + stream.append(Stream(6, 6, 6, 6, 6, 6)) //追加流
Console println "flatMap => " + stream.flatMap(i => Stream(i, i)) //对每个元素都进行 i=>(i,i)的转化
//只需处理当前元素所够用的内存，元素在被filter决定不再需时会被GC清理（大量的大元素处理时，这样会降低程序对内存的需求）
Console println "find => " + stream.find(_ > 6)
// Console println "ones => " + Stream.ones
Console println "mapWithUnfold => " + stream.mapWithUnfold(_.toString + " - ")
Console println "takeWithUnfold => " + stream.takeWithUnfold(2)
Console println "takeWhileWithUnfold => " + stream.takeWhileWithUnfold(_ > 0)
Console println "startsWith => " + stream.startsWith(Stream(1, 2))
//使用默认元素值填充
Console println "zipAll-1 => " + stream.zipAll(Stream(1, 2))
Console println "zipAll-2 => " + Stream(1, 2).zipAll(stream)
//只对对应位置进行处理，长度较长的被忽略
Console println "zipWith-1 => " + stream.zipWith(Stream(1, 2))(_ -> _)
Console println "zipWith-2 => " + Stream(1, 2).zipWith(stream)(_ -> _)
Console println "tails => " + stream.tails
//子序列是包含结尾的，不是从中间取
Console println "hashSubsequence => " + stream.hashSubsequence(Stream(6, 7))
Console println "scanRight => " + stream.scanRight(0)(_ + _)
import Stream._
//定义数据结构
//支持协变
trait Stream[+A] {
/**
* 只是为了方便测试，自己加的toString方法
*
* @return
*/
override def toString: String = {
toList.toString()
}
//书上原有方法
def headOption: Option[A] = this match {
case Empty => None
case Cons(h, t) => Some(h()) //显示调用thunk强制求值
}
/**
* 5.1：将流转化为List
*
* @return
*/
def toList: List[A] = {
//类似头插法构造list，()用于强制求值
@annotation.tailrec
def loop(s: Stream[A], acc: List[A]): List[A] = s match {
case Cons(h, t) => loop(t(), h() :: acc)
case _ => acc
}
loop(this, List()).reverse
}
/**
* 5.2-1：返回stream中前n个元素
*
* @param n
* @return
*/
def take(n: Int): Stream[A] = this match {
case Cons(h, t) if n > 1 => cons(h(), t().take(n - 1))
case Cons(h, _) if n == 1 => cons(h(), empty)
case _ => empty
}
/**
* 5.2-2：返回stream中第n个元素之后的所有元素
*
* @param n
* @return
*/
@annotation.tailrec
final def drop(n: Int): Stream[A] = this match {
case Cons(_, t) if n > 0 => t().drop(n - 1)
case _ => this
}
/**
* 5.3：返回stream中从起始元素连续满足给定断言的所有元素
*
* @param p
* @return
*/
def takeWhile(p: A => Boolean): Stream[A] = this match {
//匹配case，同时满足if
case Cons(h, t) if p(h()) => cons(h(), t().takeWhile(p))
case _ => empty
}
//书上原有方法
def exists(p: A => Boolean): Boolean = this match {
case Cons(h, t) => p(h()) || t().exists(p) // ||有短路功能，第一个参数为true，不会再执行第二个表达式（方法）
case _ => false
}
//书上原有方法，类似List的右折叠，=> B是传名参数
def foldRight[B](z: => B)(f: (A, => B) => B): B = {
this match {
case Cons(h, t) => f(h(), t().foldRight(z)(f)) //如果f不对第二个参数求值，递归就不会发生
case _ => z
}
}
//书上原有方法，使用foldRight实现的exists
def exists2(p: A => Boolean): Boolean = {
foldRight(false)((a, b) => p(a) || b)
}
/**
* 5.4：检查stream中所有元素是否与给定的断言匹配，遇到不匹配的值就终止遍历
*
* @param p
* @return
*/
def forAll(p: A => Boolean): Boolean = {
//这里默认是true。注意
foldRight(true)((h, t) => p(h) && t) //&& 可以短路，遇到不匹配就不执行递归了
}
/**
* 5.5：使用foldRight实现
*
* @param p
* @return
*/
def takeWhile2(p: A => Boolean): Stream[A] = {
//折叠初始值，折叠方式
foldRight(empty[A])((h, t) => if (p(h)) cons(h, t) else empty)
}
/**
* 5.6：使用foldRight实现
*
* @return
*/
def headOption2: Option[A] = {
//起始值是None，类型是Option
foldRight(None: Option[A])((h, _) => Some(h))
}
/**
* 5.7-1：使用foldRight实现
*
* @param f
* @tparam B
* @return
*/
def map[B](f: A => B): Stream[B] = {
foldRight(empty[B])((h, t) => cons(f(h), t))
}
/**
* 5.7-2：使用foldRight实现
*
* @param f
* @return
*/
def filter(f: A => Boolean): Stream[A] = {
foldRight(empty[A])((h, t) => if (f(h)) cons(h, t) else t)
}
/**
* 5.7-3：使用foldRight实现
*
* @param s
* @tparam B
* @return
*/
def append[B >: A](s: => Stream[B]): Stream[B] = {
foldRight(s)((h, t) => cons(h, t))
}
/**
* 5.7-4：使用foldRight实现
*
* @param f
* @tparam B
* @return
*/
def flatMap[B](f: A => Stream[B]): Stream[B] = {
foldRight(empty[B])((h, t) => f(h) append t)
}
//书上原有方法
def find(p: A => Boolean): Option[A] = {
filter(p).headOption
}
/**
* 5.13-1：使用unfold实现map
*
* @param f
* @tparam B
* @return
*/
def mapWithUnfold[B](f: A => B): Stream[B] =
unfold(this) {
//使用f函数将h进行类型转换生成值 f(h() ，继续对tail流操作
case Cons(h, t) => Some((f(h()), t()))
case _ => None
}
/**
* 5.13-2：使用unfold实现take
*
* @param n
* @return
*/
def takeWithUnfold(n: Int): Stream[A] = {
unfold((this, n)) {
case (Cons(h, t), 1) => Some((h(), (empty, 0)))
case (Cons(h, t), n) if n > 1 => Some((h(), (t(), n - 1)))
case _ => None
}
}
/**
* 5.13-3：使用unfold实现takeWhile
*
* @param f
* @return
*/
def takeWhileWithUnfold(f: A => Boolean): Stream[A] = {
unfold(this) {
case Cons(h, t) if f(h()) => Some((h(), t()))
case _ => None
}
}
/**
* 封装了zipWith
*
* @param s2
* @tparam B
* @return
*/
def zip[B](s2: Stream[B]): Stream[(A, B)] = {
zipWith(s2)((_, _))
}
/**
* 5.13-4：使用unfold实现zipWith
*
* 接收一个stream，对两个stream的对应元素使用f函数进行处理，构造出新的stream
* zip函数将传进来的两个参数中相应位置上的元素组成一个pair数组
* 如果其中一个参数元素比较长，那么多余的参数会被删掉。
*
* @param s2
* @param f
* @tparam B
* @tparam C
* @return
*/
def zipWith[B, C](s2: Stream[B])(f: (A, B) => C): Stream[C] = {
unfold((this, s2)) {
case (Cons(h1, t1), Cons(h2, t2)) => Some((f(h1(), h2()), (t1(), t2())))
case _ => None
}
}
/**
* 5.13-5：使用unfold实现zipAll
*
* zipAll应该继续遍历只要stream还有更多元素
* 和zip函数类似，区别：如果其中一个元素个数比较少，那么将用默认的元素填充(None)
*
* @param s2
* @tparam B
* @return
*/
def zipAll[B](s2: Stream[B]): Stream[(Option[A], Option[B])] = {
zipWithAll(s2)(_ -> _)
}
def zipWithAll[B, C](s2: Stream[B])(f: (Option[A], Option[B]) => C): Stream[C] = {
unfold((this, s2)) {
//二元组表达式除了标准的小括号表达方式：("a","b")，还可以有箭头表达式："a"->"b"
//1) ArrowAssoc是值类型，运行时虽有隐式转换，但避免了在堆上分配一个包装对象
//2) ->方法是声明为@inline的，也提升了性能
case (Empty, Empty) => None
case (Cons(h, t), Empty) => Some(f(Some(h()), Option.empty[B]) -> (t() -> empty[B]))
case (Empty, Cons(h, t)) => Some(f(Option.empty[A], Some(h())) -> (empty[A] -> t()))
case (Cons(h1, t1), Cons(h2, t2)) => Some(f(Some(h1()), Some(h2())) -> (t1() -> t2()))
}
}
/**
* 5.14：使用已经存在的函数实现。
*
* 检查一个stream是否是另一个stream的前缀
*
* Example：Stream(1,2,3).startsWith(Stream(1,2)) return true
*
* @param s
* @tparam A
* @return
*/
def startsWith[A](s: Stream[A]): Boolean = {
zipAll(s).takeWhile(_._2.isDefined) forAll {
case (h1, h2) => h1.get == h2.get
}
}
/**
* 5.15：使用unfold实现tails
*
* Example：Stream(1,2,3).tails return Stream(Stream(1,2,3),Stream(2,3),Stream(3),Stream())
*
* @return
*/
def tails: Stream[Stream[A]] = {
unfold(this) {
case Empty => None
//返回1,2,3调用drop，返回第一个元素之后的2,3
//返回2,3 调用drop，返回第一个元素之后的3
//返回3 调用 drop，返回第一个元素之后的()
case s => Some((s, s drop 1))
} append Stream(empty)
}
def hashSubsequence[A](s: Stream[A]): Boolean = {
//取出第一个元素后与传进来的流进行首匹配
tails exists (_ startsWith s)
}
/**
* 5.16：泛化tails函数，类似foldRight返回一个中间结果的stream
*
* Example：Stream(1,2,3).scanRight(0)(_ + _).toList return List(6,5,3,0)
*
* 难 看答案吧
*
* @param z
* @param f
* @tparam B
* @return
*/
def scanRight[B](z: B)(f: (A, => B) => B): Stream[B] = {
//初始值=(0,Stream()) ，操作 f= ( _ + _)
foldRight(z -> Stream(z))((a, p0) => {
//p0=p1=(27,List(27, 25, 22, 18, 13, 7, 0))
lazy val p1: (B, Stream[B]) = p0 // 对于p0又能继续使用函数(_ + _)处理
// 对p1._1与a 使用 _ + _ 进行处理
val b2 = f(a, p1._1) // 得到临时值
(b2, cons(b2, p1._2)) //继续与被调用与后续流相加
})._2
}
}
//空流
case object Empty extends Stream[Nothing]
//非空，由h+t组成，()不能省略
case class Cons[+A](h: () => A, t: () => Stream[A]) extends Stream[A]
//不需要使用this，不是对指定流进行处理的，用于构造流的方法写在object，作为“静态方法”
object Stream {
//流自带的智能构造方法（普通方法）
//构造非空流
def cons[A](hd: => A, tl: => Stream[A]): Stream[A] = {
lazy val head = hd
lazy val tail = tl
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: _*))
}
//别测试无限流。。out of memory
val ones: Stream[Int] = Stream.cons(1, ones)
/**
* 5.8：根据给定值返回无限流
*
* @param a
* @tparam A
* @return
*/
def constant[A](a: A): Stream[A] = {
//引用自身，是无限流，因为具有增量性质，上面写的函数对无限流也适用。但最后可能造成栈溢出
lazy val tail: Stream[A] = Cons(() => a, () => tail)
tail
}
/**
* 5.9：写一个函数生成一个整数无限流，从N开始，然后N+1,N+2,N+3... Scala的Int是有符号32位整型
* stream从某点开始从正数变为负数，并且40亿后会重复发生
*
* @param n
* @return
*/
def from(n: Int): Stream[Int] = {
//从N开始，每个tail构造使用N+1
cons(n, from(n + 1))
}
/**
* 5.10：写一个fibs函数生成斐波那契熟练的无限流：0,1,1,2,3,5,8，等
*/
def fibs = {
def go(f0: Int, f1: Int): Stream[Int] = {
//构造的时候使用f0+f1
cons(f0, go(f1, f0 + f1))
}
go(0, 1)
}
/**
* 5.11：写一个更加通用的构造流的函数，它接收一个起始状态，以及一个在生成的Stream中用于产生下一状态和下一个值的函数
* 注：fold 可以根据数据源和条件，由包含多个元素的序列产生一个结果；而 unfold 方向相反，它根据条件由源产生了更多的结果
*
* 它有两个优点：
* 1.消除了while循环语句
* 2.消除了不必要的变量声明
*
* 具体参考答案，这个地方不太好理解，而且不好测无限流
*
* @param z 初始化值
* @param f 传入S类型参数，产生下一值的函数
* @tparam A 产生值的类型
* @tparam S 初始值的类型
* @return
*/
def unfold[A, S](z: S)(f: S => Option[(A, S)]): Stream[A] = {
//共递归函数
//对z这个初始化先应用f函数
f(z) match {
//(h, s)是一个元组，使用f生成h（f在参与模式匹配时对第一个参数进行了处理），并继续对s执行同样操作
case Some((h, s)) => cons(h, unfold(s)(f))
case None => empty
}
}
/**
* 5.12-1：使用unfold实现fibs
*/
def fibsWithUnfold = {
//z:S=(f0, f1) => z:S=(f1,f0+f1)
unfold((0, 1)) { case (f0, f1) => Some((f0, (f1, f0 + f1))) }
}
/**
* 5.12-2：使用unfold实现from
*
* @param n
* @return
*/
def fromWithUnfold(n: Int) = {
unfold(n)(n => Some((n, n + 1)))
}
/**
* 5.12-3：使用unfold实现constant
*
* @param a
* @tparam A
* @return
*/
def constantWithUnfold[A](a: A) = {
unfold(a)(_ => Some((a, a)))
}
/**
* 5.12-4：使用unfold实现ones
*
* @return
*/
def onesWithUnfold = {
unfold(1)(_ => Some((1, 1)))
}
}
}
京公网安备 11010502036488号