Scala中递归定义的惰性瓦尔(类型为Stream[T])如何求值

egmofgnx 于 12个月前发布在 Scala

关注(0)|答案(2)|浏览(125)

我对Scala中如何计算lazy瓦尔感到困惑。

private def incrementStream: Stream[Int] = {
    def increment1(x: Int): Int = {
        println("increment: " + x + ", " + (x + 1))
        x + 1
    }

    lazy val n: Stream[Int] = 1 #:: (n map increment1)
    n
}

上面的代码递归地定义了n。
当计算n的前三个元素时，我认为计算轨迹如下所示。
n0 = 1
n1 = 1 #：：（n0 map increment1）= 1 #：：2
n2 = 1 #：：（n1 map increment1）= 1 #：：（（1 #：：2）map increment1）= 1 #：：2 #：：3
ni（n 0，n1，...）表示递归计算i步之后的结果。
在上面的跟踪中，将1递增到2发生了两次。一次是计算n1，一次是计算n2。

object Main extends App {
  private def incrementStream: Stream[Int] = {
    def increment1(x: Int): Int = {
      println("increment: " + x + ", " + (x + 1))
      x + 1
    }

    lazy val n: Stream[Int] = 1 #:: (n map increment1)
    n
  }

  println(incrementStream.take(3).toList)
}

然而，当我执行上面的代码时，我得到了以下结果。
增量：1，2
增量：2、3
列表（1，2，3）
从1到2只发生了一次！
我不明白这怎么可能。递归定义的lazy瓦尔如何计算？

scala

来源：https://stackoverflow.com/questions/77220706/how-recursively-defined-lazy-valwith-type-streamt-is-evaluated-in-scala

2条答案

按热度按时间

vuktfyat1#

Stream s（从Scala 2.13开始就被弃用，现在已经被LazyList s取代，下面也适用）memoize 结果，这意味着一旦一个项被计算出来，它就被存储在内存中，以便在后续调用中检索。
我不熟悉实现细节，但抽象地说，你可以把Stream看作是一个直通缓存，在计算（和缓存）之前，将在其中查找项。
在这种形式的惰性记忆会导致不必要的内存消耗的情况下，这是需要考虑的。

赞(0）回复(0）举报 12个月前

xbp102n02#

我不明白这怎么可能。递归定义的lazy瓦尔如何计算？
在scala中，你有parameters by name
By-name参数每次使用时都进行评估。如果它们未使用**，则根本不会对其进行评估。这类似于用传递的表达式替换by-name参数。它们与by-value参数相反。要创建一个名为by-name的参数，只需在其类型前加上=>。
如果你有一个函数接受一个by值参数，那么传递的值必须首先被求解

def paramByValue(i: Int) = i

paramByValue({
  println("by name must be computed")
  1
})

如果你有一个函数接受一个名字参数（它只是接收一个函数作为参数，也被称为高阶函数），如果不调用它，函数内部的东西将永远不会被执行

def paramByName(f: () => Int) = 
  if(1 != 1) {
    f() // this line is not being called, meaning what is passed will not be computed
  } else 0

paramByName(() => {
  println("won't be printed") // the message will not be printed because the function is not being invoked
  1
})

也就是说，LazyList的元素在被调用之前不会被计算。
如果您检查LazyList.cons[A]（hd：=> A，tl：=> LazyList[A]）：LazyList[A]，您将看到以下代码

/** A lazy list consisting of a given first element and remaining elements
      *  @param hd   The first element of the result lazy list
      *  @param tl   The remaining elements of the result lazy list
      */
    def apply[A](hd: => A, tl: => LazyList[A]): LazyList[A] = newLL(sCons(hd, newLL(tl.state)))

正如您所看到的，它按名称接收两个参数。首先是head，然后是tail。正因为如此，LazyList可以是无限的，因为在元素被消耗之前，尾部不会被加载到内存中。
如果我定义如下LazyList

val lazyList = LazyList.cons(
  { () =>
    println("the head")
    1
  }, {
    println("the tail")
    LazyList(2, 3, 4)
  }
)

然后执行以下操作

lazyList.head // print `the head`
lazyList.tail // doesn't print anything
lazyList.tail.head // print `the tail`

正如@stefanobaghino所说，LazyList在元素被消费后会记住它们。详细信息请参见scaladoc of the LazyList
这个类实现了一个不可变的链表。我们称之为“lazy”，因为它只在需要的时候才计算元素。
元素被记忆;也就是说，每个元素的值最多计算一次。
这意味着，如果每个元素都有副作用（比如print to stdout），那么最多只会执行一次。
以下文章可以给予更多细节

Scala - collections具体的不可变集合类
By-Value and By-Name Parameters in Scala
LazyList in Scala

赞(0）回复(0）举报 12个月前

我来回答

Scala中递归定义的惰性瓦尔(类型为Stream[T])如何求值

2条答案

相关问题

热门标签

最新问答