Блог Scala Функ. программирование Классы типов Алгоритмы Библиотеки Упражнения Ресурсы

Ленивые вычисления

Нестрогость (или ленивое вычисление) — это свойство функции. Сказать, что функция не является строгой, просто означает, что функция может решить не оценивать один или несколько своих аргументов. Напротив, строгая функция всегда оценивает свои аргументы. Строгие функции являются нормой в большинстве языков программирования. Если не указано иное, любое определение функции в Scala будет строгим.

В качестве примера рассмотрим следующую функцию:

def square(x: Double): Double = x * x

При вызове square(41.0 + 1.0), функция square получит оценочное значение 42.0, потому что она строгая. Напротив, сокращающие логические функции && и ||, встречающиеся во многих языках программирования, включая Scala, не являются строгими. Функция && принимает два логических аргумента, но оценивает второй аргумент только в том случае, если первый истинен:

false && { println("!!"); true }
// res0: Boolean = false

Аналогично || оценивает свой второй аргумент, только если первый false:

true || { println("!!"); false }
// res1: Boolean = true

Еще одним примером нестрогости является управляющая конструкция if в Scala:

val result = if input.isEmpty then sys.error("empty input") else input

Нестрогие вычисления не кэшируются и вычисляются каждый раз при вызове:

def maybeTwice(b: Boolean, i: => Int) = if b then i + i else 0
val x = maybeTwice(true, { println("hi"); 1 + 41 })
// hi
// hi
// x: Int = 84

Lazy List

Рассмотрим, как можно использовать нестрогость для повышения эффективности и модульности функциональных программ на примере ленивых списков. Цепочки преобразований в ленивых списках объединяются в один проход благодаря использованию нестрогости. Вот простое определение LazyList:

enum LazyList[+A]:
  case Empty
  case Cons(h: () => A, t: () => LazyList[A])

import LazyList.*

object LazyList:
  def cons[A](hd: => A, tl: => LazyList[A]): LazyList[A] =
    lazy val head = hd
    lazy val tail = tl
    Cons(() => head, () => tail)

  def empty[A]: LazyList[A] = Empty

  def apply[A](as: A*): LazyList[A] =
    if as.isEmpty then empty
    else cons(as.head, apply(as.tail*))

С помощью LazyList можно построить вычисление, которое производит последовательность элементов, не выполняя шаги этого вычисления до тех пор, пока эти элементы действительно не понадобятся. Вообще говоря, нестрогость позволяет отделить описание выражения от вычисления этого выражения. Это дает мощную возможность — можно описать «бОльшее» выражение, чем нужно, а затем вычислить только его часть.

В качестве примера может служить функция exists, которая проверяет, существует ли в LazyList элемент, соответствующий логической функции:

def exists(p: A => Boolean): Boolean = this match
  case Cons(h, t) => p(h()) || t().exists(p)
  case _ => false

|| не является строгим по второму аргументу, а значит если p(h()) возвращает true, то exists завершает обход досрочно и также возвращает true. Заметим, что конец LazyList — это lazy val. Таким образом, обход не только раньше завершается, но и остаток LazyList вообще никогда не оценивается! Таким образом, любой код, который сгенерировал бы остаток, на самом деле никогда не выполняется.

Аналогично с реализациями других методов: эти реализации являются инкрементными — они не полностью генерируют свои ответы. Только после того, как какое-то другое вычисление просмотрит элементы результирующего LazyList, вычисление для создания этого LazyList действительно не произойдет, и тогда оно выполнит ровно столько работы, сколько нужно для создания запрошенных элементов. Из-за этого инкрементного характера можно вызывать эти функции одну за другой без полного создания промежуточных результатов.

Инкрементальный характер ленивых преобразований списка также имеет важные последствия для использования памяти. Поскольку промежуточные ленивые списки не генерируются, преобразование ленивого списка требует ровно столько рабочей памяти, сколько необходимо для хранения и преобразования текущего элемента.

Бесконечные ленивые списки

Поскольку преобразования являются инкрементальными, написанные функции также работают с бесконечными LazyList. Вот пример бесконечного LazyList из единиц:

val ones: LazyList[Int] = LazyList.cons(1, ones)
ones.take(5).toList
// res2: List[Int] = List(1, 1, 1, 1, 1)
ones.exists(_ % 2 != 0)
// res3: Boolean = true

Корекурсия

Рассмотрим функцию unfold:

def unfold[A, S](state: S)(f: S => Option[(A, S)]): LazyList[A] = f(state) match
  case None         => Empty
  case Some((a, s)) => Cons(() => a, () => unfold(s)(f))

Функция unfold является примером того, что иногда называют корекурсивной функцией. В то время как рекурсивная функция потребляет данные, корекурсивная функция их производит. И в то время как рекурсивные функции завершаются рекурсией на меньших входных данных, корекурсивные функции не должны завершаться, пока они остаются продуктивными, что означает, что всегда можно оценить больше результата за конечное время. Функция развертывания продуктивна до тех пор, пока f завершается, поскольку нужно просто запустить функцию f еще раз, чтобы сгенерировать следующий элемент LazyList. Корекурсию также иногда называют защищенной рекурсией, а производительность также иногда называют котерминацией.

Резюме

Ссылки: