Ленивая оценка.
Чтобы увидеть мир в песчинке и небо в полевом цветке
Держи бесконечность на ладони и вечность через час— Уильям Блейк
Несколько лет назад я посещал учебный курс по C #. Я помню, что мне было трудно понять две вещи, в частности. Одним из них был LINQ, отчасти из-за того, что я не мог полностью разобраться в синтаксисе. Я много лет изучал SQL, и этот язык, который был похож, но не совсем, смутил меня. Кроме того, я еще не узнал о функциональном стиле программирования; теперь, когда у меня есть, это имеет больше смысла для меня.
Другая вещь была ключевым словом yield . Но опять же, с пониманием функционального стиля это имеет гораздо больше смысла, и на самом деле это действительно очень просто. Документация .NET дает этот пример использования:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
|
public class PowersOf2{ static void Main() { foreach (var i in Power(2, 8)) Console.Write("{0} ", i); } public static IEnumerable<int> Power(int number, int exponent) { var result = 1; for (var i = 0; i < exponent; i++) { result = result * number; yield return result; } }} |
При запуске он печатает: 2 4 8 16 32 64 128 256
Что происходит, метод Power возвращает экземпляр IEnumerable, и цикл foreach вызывает для него MoveNext несколько раз. Однако метод Power явно не создает экземпляр IEnumerable. Используя оператор yield return , метод буквально становится итератором, который вычисляет свои повторяющиеся значения по требованию. Возвращаемое здесь значение является первым итеративным элементом. В этот момент управление возвращается в цикл foreach, после чего его тело выполняется один раз. Затем он снова вызывает MoveNext на итераторе, в результате чего элемент управления возвращается к методу Power сразу после оператора yield return. Внутреннее состояние метода Power сохраняется прежним, поэтому цикл for повторяется снова и возвращает следующий элемент с повторением. Таким образом, управление несколько раз переходит между циклом foreach и оператором yield return, пока, наконец, цикл for не завершится и Power не выйдет без повторного вызова yield return.
Как объясняется в документации , основной вариант использования для yield return заключается в реализации итератора для пользовательского типа коллекции в методе без необходимости создания новой реализации IEnumerable или IEnumerator, что позволяет избежать необходимости определять новый класс. Это дает другой пример, чтобы проиллюстрировать этот момент.
Но что, если метод итератора никогда не завершится?
Представьте, что мы удалили условие завершения, чтобы цикл, содержащий оператор yield return продолжался вечно:
|
1
2
3
4
5
6
|
public static IEnumerable<int> Numbers(){ var number = 1; for (;;) yield return number++;} |
Если мы назовем это так, мы распечатаем 1 2 3 4 5 6 7 8 9 10 :
|
1
2
3
4
5
6
7
8
9
|
static void Main(){ foreach (var i in Numbers()) { Console.Write("{0} ", i); if (i == 10) break; }} |
Теперь нам нужно выйти из цикла foreach, потому что метод Numbers явно никогда не завершится нормально. Так какой в этом смысл? На самом деле глубокая и глубокая мысль. Теперь у нас есть IEnumerable который якобы содержит все натуральные числа, а это бесконечное множество.
Конечно, это невозможно!
Это действительно так, но оказывается, что обещание гораздо важнее того, что его нельзя сдержать.
Если вы помните в части 4, у нас был этот код, который генерирует сито простых чисел и возвращает предикат для проверки, является ли число простым:
|
1
2
3
4
5
6
7
8
|
private Predicate<Integer> notInNonPrimesUpTo(int limit) { Set<Integer> sieve = IntStream.range(2, (limit / 2)) .boxed() .flatMap(n -> Stream.iterate(n * 2, nonPrime -> nonPrime += n) .takeWhile(nonPrime -> nonPrime <= limit)) .collect(Collectors.toSet()); return candidate -> !sieve.contains(candidate);} |
Я сказал, что Stream.iterate был интересным и что я вернусь к нему позже. Время пришло. Это еще один пример итератора, который предназначен для итерации бесконечного списка:
|
1
|
Stream.iterate(n * 2, nonPrime -> nonPrime += n) |
Он генерирует поток целых чисел, начинающийся с (n * 2) и увеличивающийся на n каждый раз. Обратите внимание, что нет верхней границы. Условие завершения — когда значение limit превышено — здесь:
|
1
|
.takeWhile(nonPrime -> nonPrime <= limit) |
Кроме того, если вы помните в предыдущей статье, мы видели несколько применений функции range в Clojure. В каждом случае я использовал это следующим образом:
|
1
|
(range 1 10) |
который оценивает список чисел от 1 до 10. Но мы можем также назвать range без аргументов:
|
1
2
|
user=> (take 5 (range))(0 1 2 3 4) |
Правильно, range без аргументов — это еще один предположительно бесконечный список целых чисел. Однако, если вы выполняете (range) в REPL сам по себе, он ничего не делает, а просто блокирует. Он ждет, чтобы что-то было принято. Как и в случае с Java Stream.iterate и Stream.iterate выхода C #, значения генерируются только тогда, когда они запрашиваются. Вот почему оценка называется ленивой. «Стремительно» оцененная последовательность генерирует все свои значения сразу после создания, как (range 1 10) . «Лениво» оцененная последовательность генерирует свои значения только по требованию. Именно это отложенное выполнение делает возможным притворство бесконечных последовательностей. С помощью подмигивания и знающего кивка, притворство может быть поддержано, при условии, что программа на самом деле никогда не просит выполнения обещания.
Петлевые индексы.
Как вы, наверное, уже поняли, мне нравится такой же хитрый трюк, как и следующему человеку, но мне больше нравится, если его можно использовать на практике, что делает мой код лучше. Так же и с ленивой оценкой.
Ранее в этой серии я утверждал, что принятие функционального стиля означает, что вам вряд ли когда-нибудь придется снова писать цикл. Отображение и сокращение действительно охватывают очень много вариантов использования, но, тем не менее, иногда вам нужно отслеживать свою итерацию с помощью какого-то счетчика. Теперь, если бы я программировал на таком языке, как C # или Java, оба из которых являются обязательными в глубине души, я бы не стал проходить через искажения, необходимые для того, чтобы сделать это в функциональном стиле. Я бы использовал традиционный цикл вместо:
|
1
2
3
4
5
6
|
public void IterateWithIndex(){ var numbers = new[] {"one", "two", "three", "four", "five"}; for (var i = 0; i < numbers.Length; i++) Console.WriteLine("{0}: {1}", i, numbers[i]);} |
Я предпочитаю не мутировать состояние без необходимости, но для меня простота — все еще более высокая добродетель, а в некоторых языках это по-прежнему самый простой способ решения проблемы. При прочих равных условиях я бы выбрал три строки простого кода, который изменяет состояние более чем на полдюжины строк непостижимого функционального кода, выполняющего ту же работу.
Некоторые языки предоставляют простой способ итерации последовательности в функциональном стиле, а также предоставляют счетчик итераций. Groovy предоставляет метод eachWithIndex который позволяет делать это без административной работы:
|
01
02
03
04
05
06
07
08
09
10
11
|
[ [symbol: 'I', value: 1], [symbol: 'V', value: 5], [symbol: 'X', value: 10], [symbol: 'L', value: 50], [symbol: 'C', value: 100], [symbol: 'D', value: 500], [symbol: 'M', value: 1000],].eachWithIndex { numeral, i -> println("${i}: ${numeral.symbol} ${numeral.value}")} |
В таком случае это хороший выбор. Но возвращая предмет к ленивой оценке, если вы работали с Clojure, проблему можно было бы решить интересным способом, используя (range) :
|
1
2
3
|
(map (fn [i number] (format "%d: %s" i number)) (range) '("one" "two" "three" "four" "five")) |
Напомним, что map для нескольких последовательностей продолжается до тех пор, пока не закончится самая короткая из последовательностей. Очевидно, что лениво оцененная последовательность не будет исчерпана первой, поэтому она продолжает считать до тех пор, пока другой список не будет исчерпан. Следовательно, результат:
|
1
|
("0: one" "1: two" "2: three" "3: four" "4: five") |
Тем не менее, Clojure также предоставляет функцию map-indexed по map-indexed которая выполняет работу, аналогичную eachWithIndex в Groovy:
|
1
2
|
(map-indexed (fn [i number] (format "%d: %s" i number)) '("one" "two" "three" "four" "five")) |
Не убежден. Покажите мне пример, где ленивая оценка действительно помогает.
Недавно в реальном мире я столкнулся с ситуацией, когда требовался индекс цикла, — я хотел писать параметризованные сообщения журнала. Для этого я выбрал формат шаблона, аналогичный используемому в C #, то есть:
|
1
|
The {0} has a problem. Cause of failure: {1}. Recommended solution: {2}. |
Это не было одним из реальных сообщений журнала, но вы поняли идею. Программа была на Java и решение довольно простое:
|
1
2
3
4
5
6
|
private String replaceParameters(String template, String... parameters) { var out = template; for (var i = 0; i < parameters.length; i++) out = out.replace(String.format("{%d}", i), parameters[i]); return out;} |
Это абсолютно необходимо, и оно бесстыдно изменяет свое внутреннее состояние. Если бы мы попытались переписать его в более функциональный стиль, он мог бы выглядеть примерно так:
|
1
2
3
4
5
6
7
8
|
private String replaceParameters(String template, String... parameters) { var i = new AtomicInteger(0); return Arrays.stream(parameters) .reduce(template, (string, parameter) -> string.replace( String.format("{%d}", i.getAndIncrement()), parameter));} |
Я не думаю, что это прагматично. Скорее, я думаю, что это использует функциональный стиль только ради него, а не потому, что он лучше. Вспомните, что я сказал о сладком месте для функционального программирования? Это не так Во-первых, ясность оригинала была принесена в жертву: мне пришлось разбить его на несколько строк, чтобы улучшить читабельность. И это на самом деле не более функционально — оно все равно AtomicInteger состояние, потому что AtomicInteger увеличивается.
Так что в Java я думаю, что традиционный цикл — лучший путь, но как насчет правильно функционирующего языка, который не дает нам такого выбора? В Clojure функция с map-indexed здесь не поможет. Вместо этого это задание для reduce , и нет функции с reduce-indexed . У нас есть zipmap , иногда называемый «zip» на других языках. Он назван так потому, что его поведение напоминает действие застежки-молнии:
|
1
2
|
user=> (zipmap [1 2 3] ["one" "two" "three"]){1 "one", 2 "two", 3 "three"} |
Мы можем использовать его для написания функции замены параметров, используя reduce следующим образом:
|
1
2
3
4
5
|
(defn- replace-parameter [string [i parameter]] (clojure.string/replace string (format "{%d}" i) parameter))(defn replace-parameters [template parameters] (reduce replace-parameter template (zipmap (range) parameters))) |
и это работает!
|
1
2
3
4
|
user=> (replace-parameters #_=> "The {0} has a problem. Cause of failure: {1}. Recommended solution: {2}." #_=> ["time machine" "out of plutonium" "find lightning bolt"])"The time machine has a problem. Cause of failure: out of plutonium. Recommended solution: find lightning bolt." |
Быть ленивым.
Мы немного поиграли с ленивыми последовательностями из коробки, поэтому давайте сделаем небольшое упражнение, которое включает в себя создание одного из наших собственных. Возможно, вы слышали о треугольнике Паскаля. В математическом плане треугольник Паскаля представляет собой треугольный массив биномиальных коэффициентов, но вам не нужно знать, что это значит, потому что его очень просто построить. Вы начинаете с размещения 1 на вершине, а затем строите треугольник, размещая ряды чисел ниже, со смещением влево и вправо от чисел выше, чтобы в каждой строке было на одно число больше, чем у выше. Каждое число равно сумме двух чисел над ним; для чисел на краю треугольника отсутствующие числа рассматриваются как ноль. Эта диаграмма должна прояснить:
|
1
2
3
4
5
|
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 |
Написание программы для ее создания — интересная проблема. Это станет намного проще, если вы заметите, что следующую строку можно сгенерировать, продублировав предыдущую строку, сдвинув одну из них влево или вправо, а затем суммировав цифры смещения, т.е.
|
1
2
3
|
1 4 6 4 1 0+ 0 1 4 6 4 1= 1 5 10 10 5 1 |
В терминах Clojure это можно выразить так:
|
1
2
3
|
(defn next-row [previous] (apply vector (map + (conj previous 0) (cons 0 previous)))) |
Быстрый тест показывает, что это работает:
|
1
2
3
4
5
6
7
|
#'user/next-rowuser=> (next-row [1])[1 1]user=> (next-row [1 1])[1 2 1]user=> (next-row [1 2 1])[1 3 3 1] |
и тогда мы можем лениво построить целый треугольник, используя iterate как это:
|
1
|
(def triangle (iterate next-row [1])) |
В Clojure итерация лениво создает последовательность, многократно применяя результат предыдущей итерации к функции next-row , начиная с начального значения [1] , которое представляет собой вектор, содержащий число 1.
Затем вы можете взять столько строк из triangle сколько пожелаете:
|
1
2
|
user=> (take 7 triangle)([1] [1 1] [1 2 1] [1 3 3 1] [1 4 6 4 1] [1 5 10 10 5 1] [1 6 15 20 15 6 1]) |
и даже запросить любую произвольную строку:
|
1
2
|
user=> (nth triangle 10)[1 10 45 120 210 252 210 120 45 10 1] |
Очевидно, что хотя кажется, что triangle является последовательностью, никакой реальной последовательности в памяти не существует, если только вам не удалось построить ее самостоятельно из результатов. Если вы сначала вернетесь к примеру yield return в C #, то увидите там то же самое поведение. Может показаться парадоксом, что неограниченные коллекции требуют меньше памяти, но это важный совет по производительности, о котором следует помнить.
Повторите себя.
Чтобы закончить наше исследование ленивых оценок, давайте немного повеселимся. Как однажды заметил кто-то, ката FizzBuzz популярна, поскольку позволяет избежать неловкости, когда никто в комнате не может вспомнить, как выполнять двоичный поиск в массиве. Если вы один из немногих людей в мире, которые не знакомы с игрой, то она очень проста: вы считаете числа, заменяя все кратные три на «Fizz», все кратные пяти на «Buzz», и все кратные оба с «FizzBuzz.»
NB. Обычно говорят, что она возникла как пьющая игра, и я действительно играл в такую игру в университете, хотя правила Уорика немного отличались. Пока мы играли, buzz было четыре, а не пять, и существовало дополнительное правило: когда десятичное число содержало цифру 3, тогда вы также должны были произносить «fizz», а когда оно содержало 4, вы должны были говорить «buzz». Таким образом, 12 было «fizzbuzz», 13 было «fizz», 14 было «buzz» и 15 снова «fizz». Это сделало его немного сложнее, и поэтому мы стали более пьяными.
Однажды мы попробовали во время выступления в группе играть с бинарными числами, но баритон-саксофон возразил на том основании, что он студент-юрист, а не ученый. Поэтому мы согласились сделать это римскими цифрами, убив две каты в одной.
Если есть каноническая реализация, в Java это выглядит примерно так:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
|
public class FizzBuzz { public static void main(String[] args) { for (var i = 0; i < 100; i++) System.out.println(fizzBuzz(i)); } private static String fizzBuzz(int i) { if (i % 3 == 0 && i % 5 == 0) return "FizzBuzz"; else if (i % 3 == 0) return "Fizz"; else if (i % 5 == 0) return "Buzz"; else return String.valueOf(i); }} |
(но определенно не так ).
Таким образом, это решение рассматривает это как арифметическую проблему, но, возможно, это не должно быть. Если мы проанализируем это, весь цикл будет повторяться непрерывно с периодом пятнадцать, как это:
номер, номер, Fizz, номер, Buzz, Fizz, номер, номер, Fizz, Buzz, номер, Fizz, номер, номер, FizzBuzz
и, возможно, мы можем относиться к этому в нашей программе. Clojure имеет функцию под названием cycle которая лениво повторяет предоставленный шаблон бесконечно:
|
1
2
|
user=> (take 10 (cycle [nil nil "Fizz"]))(nil nil "Fizz" nil nil "Fizz" nil nil "Fizz" nil) |
Если бы у нас была функция, которая отображала эти три ленивых последовательности, мы могли бы создать из них лениво оцененную реализацию FizzBuzz:
|
1
2
3
|
(def numbers (map inc (range))) ; goes 1 2 3 4 5 6 7 8 9 10 etc.(def fizzes (cycle [nil nil "Fizz"])) ; goes nil nil fizz nil nil fizz etc.(def buzzes (cycle [nil nil nil nil "Buzz"])) ; goes nil nil nil nil buzz nil nil nil nil buzz etc. |
map inc необходима, потому что range начинается с 0, и нам нужно, чтобы он начинался с 1, поэтому мы увеличиваем каждое значение в последовательности на 1. Теперь давайте попробуем написать функцию:
|
1
2
3
4
|
(defn fizzbuzz [n fizz buzz] (if (or fizz buzz) (str fizz buzz) (str n))) |
Это довольно просто; если fizz или buzz являются правдивыми (т. е. не nil), то объедините их вместе — при объединении строк nil обрабатывается как пустая строка — в противном случае возвращает n как строку. Когда мы отображаем все три ленивых последовательности, мы получаем FizzBuzz!
|
1
2
|
user=> (take 30 (map fizzbuzz numbers fizzes buzzes))("1" "2" "Fizz" "4" "Buzz" "Fizz" "7" "8" "Fizz" "Buzz" "11" "Fizz" "13" "14" "FizzBuzz" "16" "17" "Fizz" "19" "Buzz" "Fizz" "22" "23" "Fizz" "Buzz" "26" "Fizz" "28" "29" "FizzBuzz") |
Мы также можем использовать nth для получения любого значения из последовательности (учитывая, что nth считает от нуля, а не от одного):
|
1
2
|
user=> (nth (map fizzbuzz numbers fizzes buzzes) 1004)"FizzBuzz" |
Разве это не круто?
В следующий раз.
В следующей статье я завершу рассмотрение практических аспектов функционального программирования. Я взгляну на постоянные структуры данных, которые позволяют функциональным языкам реализовывать неизменяемые структуры данных, которые создают впечатление изменчивости, и в то же время максимально эффективно используют память, избегая ненужного дублирования данных.
Вся серия:
- Вступление
- Первые шаги
- Первоклассные функции I: лямбда-функции и карта
- Первоклассные функции II: фильтрация, уменьшение и многое другое
- Функции высшего порядка I: Композиция функций и монады
- Функции высшего порядка II: карри
- Ленивая оценка
| Опубликовано на Java Code Geeks с разрешения Ричарда Уайлда, партнера нашей программы JCG . Смотреть оригинальную статью здесь: Функциональный стиль — часть 7
Мнения, высказанные участниками Java Code Geeks, являются их собственными. |