了解 Stream scala 交错转换行为

Question

我正在阅读 Scala 中的函数式编程 一书中包含的示例和练习，并从中获得乐趣。我正在研究 严格和懒惰 章节，其中讨论了 Stream。

我无法理解以下代码摘录产生的输出：

sealed trait Stream[+A]{

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

  def map[B](f: A => B): Stream[B] = foldRight(Stream.empty[B])((h,t) => {println(s"map h:$h"); Stream.cons(f(h), t)})

  def filter(f:A=>Boolean):Stream[A] = foldRight(Stream.empty[A])((h,t) => {println(s"filter h:$h"); if(f(h)) Stream.cons(h,t) else t})
}

case object Empty extends Stream[Nothing]

case class Cons[+A](h: () => A, t: () => Stream[A]) extends Stream[A]   

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: _*))
}

Stream(1,2,3,4,5,6).map(_+10).filter(_%2==0)

当我执行这段代码时，我收到这样的输出：

map h:1
filter h:11
map h:2
filter h:12

我的问题是：

为什么映射和过滤器输出交错？
您能否解释一下涉及的所有步骤，从 Stream 创建到获得此行为的最后一步？
列表的其他元素在哪里也通过了过滤变换，所以4和6？

Answer 1

我认为理解此行为的关键在于 foldRight.

的签名

def foldRight[B](z: => B)(f: (A, => B) => B): B = ...

请注意，第二个参数 f 是一个带有两个参数的函数，一个 A 和一个别名（惰性）B。去掉惰性，f: (A, B) => B，你不仅得到了预期的方法分组（所有 map() 步骤在所有 filter() 步骤之前），它们也以相反的顺序出现 6 首先处理，1 最后处理，正如您对 foldRight.

的期望

一只小 => 是如何施展所有魔法的？它基本上说 f() 的第二个参数将被保留直到需要它。

所以，尝试回答您的问题。

Why map and filter output are interleaved?

因为每次调用 map() 和 filter() 都会延迟到请求值的时间点。

Could you explain all steps involved from the Stream creation until the last step for obtaining this behavior?

不是真的。这将花费比我愿意贡献更多的时间和 SO 回答 space，但让我们只需要几步进入泥潭。

我们从一个 Stream 开始，它看起来像一系列 Cons，每个都有一个 Int 和对下一个 Cons 的引用，但事实并非如此完全准确。每个 Cons 实际上包含两个函数，当调用第一个函数时产生一个 Int 而第二个函数产生下一个 Cons.

调用map()并将“+10”函数传递给它。 map() 创建一个新函数："Given h and t (both values), create a new Cons. The head function of the new Cons, when invoked, will be the "+10" 函数应用于当前的头部值。新的尾部函数将生成接收到的 t 值。"这个新函数被传递给 foldRight.

foldRight 接收新函数，但函数的第二个参数的计算将延迟到需要它时。 h() 被调用以获取当前的头部值，t() 将被调用 以获取当前的尾部值并且递归调用 foldRight 将是呼吁它。

调用filter()并将"isEven"函数传递给它。 filter() 创建一个新函数："Given h and t, create a new Cons if h passes the isEven test. If not then return t." 这才是真正的 t。不承诺稍后评估其价值。

Where are other elements of the list that pass also filter transformation, so 4 and 6?

他们还在那里等待评估。我们可以通过使用模式匹配逐一提取各种 Cons 来强制执行该评估。

val c0@Cons(_,_) = Stream(1,2,3,4,5,6).map(_+10).filter(_%2==0)
//  **STDOUT**
//map h:1
//filter h:11
//map h:2
//filter h:12

c0.h()  //res0: Int = 12

val c1@Cons(_,_) = c0.t()
//  **STDOUT**
//map h:3
//filter h:13
//map h:4
//filter h:14

c1.h()  //res1: Int = 14

val c2@Cons(_,_) = c1.t()
//  **STDOUT**
//map h:5
//filter h:15
//map h:6
//filter h:16

c2.h()  //res2: Int = 16
c2.t()  //res3: Stream[Int] = Empty

了解 Stream scala 交错转换行为

Understand Stream scala interleaved transformations behavior

functional-programming

scala

stream

lazy-evaluation

scala-collections