scala - 保留共享在惰性流中意味着什么？

Question

我正在关注 Scala 书中的函数式编程。这是来自 Stream 定义和函数的代码片段，用于构建 constant使用智能构造函数并使用 unfold :

sealed trait Stream[+A]
case object Empty extends Stream[Nothing]
case class Cons[+A](h: () => A, tl: () => Stream[A]) extends Stream[A]

object Stream {
  def cons[A](h: => A, tl: => Stream[A]): Stream[A] = {
    lazy val head = h
    lazy val tail = tl
    Cons(() => head, () => tail)
  }
  def empty[A]: Stream[A] = Empty

  def constant[A](a: A): Stream[A] = cons(a, constant(a))

  def unfold[A, S](z: S)(f: S => Option[(A, S)]): Stream[A] =
    f(z).fold(empty[A])(x => cons(x._1, unfold(x._2)(f)))

  def constantViaUnfold[A](a: A): Stream[A] = unfold(a)(x => Some((x, x)))
}

有一个脚注说:

Using unfold to define constant means that we won't get sharing as in the recursive definition. The recursive definition consumes constant memory even if we keep a reference to it around while traversing it, while the unfold-based implementation does not. Preserving sharing isn’t something we usually rely on when programming with streams, since it’s extremely delicate and not tracked by the types. For instance, sharing is destroyed when calling even xs.map(x => x).

作者说我们没有得到分享是什么意思？究竟共享了什么以及为什么它没有保留在 unfold 中版本？另外关于恒定内存消耗的句子也不清楚。

Answer 1

假设您创建了一个这样的新列表:

val n0 = Nil       //List()
val n1 = 1 :: n0   //List(1)
val n2 = 2 :: n1   //List(2,1)
val n3 = 3 :: n2   //List(3,2,1)

如果你建立一个这样的列表，很容易注意到 n3 实际上是 n2 加上 3 而 n2 只是 n1 加上 2 等等。所以对 1 的引用是 共享 由 n1、n2 和 n3 以及对 2 的引用由 n2 和
n2 等
你也可以这样写:

Cons(3, Cons(2, Cons(1, Nil)))

在 FPinS 的示例中，当您递归创建 Stream 时，情况也是如此。 You Stream 是从嵌套的 Cons 构建的，每个子流都与其父流共享元素。因此，当创建下一个 Stream 时，它只是用新元素将旧的 Stream 包裹在 Cons 中。但是由于 Stream 是惰性的，所有 Cons 层次结构的构建只有在您实现它时才会完成，例如通过调用 toList .

像这样构建流也会使您持续消耗内存，因为从前一个流创建下一个流只会为新元素消耗内存。

以及为什么它不是 unfold 的情况?因为它以“其他方式”构建 Stream。所以它是这样的:

Cons(x, next_iteration_of_unfold)                    //1st iteration
Cons(x, Cons(x, next_iteration_of_unfold))           //2nd iteration
Cons(x, Cons(x, Cons(x, next_iteration_of_unfold)))  //3rd iteration, etc.

所以正如你所看到的，没有什么可以共享的。

编辑:

您可以通过调用 take 来查看物化流的外观。最后 implementation在书上加上 toString至 Cons :

override def toString: String = s"Cons(${h()}, ${tl()})"

进而:

Stream.ones.take(3)

你会看见:

Cons(1, Cons(1, Cons(1, Empty)))