Как ленивая функция take вычисляет поток Scala?

В книге Мартина Одерского «Программирование в Scala» приведен пример вычисления последовательности Фибоначчи, начиная с двух чисел, переданных в качестве аргументов функции fibFrom.

def fibFrom(a: Int, b: Int): Stream[Int] =
       a #:: fibFrom(b, a + b)

Если вы примените метод take () к этой рекурсивной функции, например:

fibFrom(1, 1).take(15).print

Выход будет:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, empty

Возможно, этот вывод очевиден для более опытных людей, но я не понимаю, как именно этот метод take () заставляет поток вычисляться дальше. 15 как-то неочевидно передается в fibFrom ()?

Всего 2 ответа


С

a #:: fibFrom(b, a + b)

Вы создали объект Stream, и у этого объекта есть голова, которая является Int, и хвост, который является функцией. Take - это функция Stream, которая вычислит 15 элементов, используя хвост и голову. Вы можете проверить исходный код функции take ():

  override def take(n: Int): Stream[A] = (
    // Note that the n == 1 condition appears redundant but is not.
    // It prevents "tail" from being referenced (and its head being evaluated)
    // when obtaining the last element of the result. Such are the challenges
    // of working with a lazy-but-not-really sequence.
    if (n <= 0 || isEmpty) Stream.empty
    else if (n == 1) cons(head, Stream.empty)
    else cons(head, tail take n-1)
  )

Я думаю, что следует отметить, что Stream лениво оценивается :

Класс Stream реализует отложенные списки, где элементы оцениваются только тогда, когда они необходимы.

Цитируется с сайта scala-lang.org

Функция fibFrom возвращает Stream , поэтому мы понимаем, что функция не будет ничего делать, даже когда fibFrom ; он начнет вычислять числа только при попытке доступа к Stream .
Функция take также возвращает Stream и действует лениво.
Функция print - это та, которая фактически вызывает рекурсию и останавливается при заполнении вывода 15 числами (как в вашем примере).

Вы можете легко проверить это, выполнив функции одну за другой и увидев результат.
Давайте запустим только fibFrom :
введите описание изображения здесь
Мы видим, что возвращаемое значение является Stream а числа еще не рассчитаны.

Теперь давайте посмотрим, что делает take(15) :
введите описание изображения здесь
То же, что и наш первый тест.

В конце концов, выполнение print дает нам желаемый результат, таким образом, фактически выполняя fibFrom рекурсивно до достижения 15 чисел:
введите описание изображения здесь

Бонус: преобразование потока в любую не ленивую структуру данных приведет к вычислениям:
введите описание изображения здесь


Есть идеи?

10000