Что означает «Сохранить совместное использование» в ленивых потоках?

Question

Я слежу за функциональным программированием в книге Scala. Вот фрагмент кода из определения потока и функций для построения 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)))
}

Сноска гласит:

Использование unfold для определения constant означает, что мы не получим общий доступ, как в рекурсивном определении. Рекурсивное определение потребляет постоянную память, даже если мы сохраняем ссылку на нее при ее обходе, в то время как реализация на основе развертывания этого не делает. Сохранение общего доступа - это не то, на что мы обычно полагаемся при программировании с потоками, поскольку оно чрезвычайно деликатное и не отслеживается типами. Например, общий доступ уничтожается при вызове даже 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 рекурсивно. Вы Stream созданы из вложенных Cons , и каждый подпоток делит элементы со своим родителем. Поэтому, когда создается следующий 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.

Итак, как вы видите, ничто не может быть передано.

EDIT:

Чтобы увидеть, как выглядит материализованный поток, вызовите take в окончательной реализации в книге и добавьте toString к Cons:

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

А потом:

Stream.ones.take(3)

Вы увидите:

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

Answer 2

Я приведу оригинальную цитату из книги (издание 2014 года), чтобы избежать путаницы:

Использование функции развернуть для определения константы и единиц означает, что мы не получаем общий доступ, как в рекурсивном определении val единицы: Stream [Int] = cons (1, единицы) . Рекурсивное определение потребляет постоянную память, даже если мы во время обхода сохраняйте ссылку на него, в то время как реализация на основе разворачивания этого не делает. Сохранение общего доступа - это не то, на что мы обычно полагаемся при программировании с потоками, поскольку это чрезвычайно деликатный и не отслеживается по типам. Например, общий доступ уничтожается при вызове даже xs.map (x => x).

Как вы видите, проблема здесь немного другая. Речь идет о повторном использовании Cons экземпляра, поэтому Stream просто ссылается на себя здесь.

Таким образом, автор предполагал, что реализация будет такой:

//Imp1
def constant[A](a: A): Stream[A] = {
   lazy val ones: Stream[A] = cons(a, ones)
   ones
}

вместо

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

Как видите, Imp1 создает только один экземпляр Cons для всего потока. Imp2 и unfold версии из вашего примера генерируют новые Cons при каждом следующем вызове, поэтому оба метода генерируют потоки, которые не разделяют экземпляр Cons.