# Глава 17. Лень Помните, в главе с первыми вопросами о Haskell я упомянул, что этот язык является ленивым? Сейчас мы наконец-то узнаем о ленивых вычислениях и познакомимся с их светлой и тёмной сторонами. ## Две модели вычислений Как мы уже знаем, Haskell-программа состоит из выражений, а запуск программы суть начало длинной цепочки вычислений. [Вспомним](/courses/haskell/chapters/haskell_chapter_0030#block-square) функцию `square`, возводящую свой единственный аргумент в квадрат: ```haskell {.example_for_playground .example_for_playground_001} main :: IO () main = print . square $ 4 ``` Здесь всё просто: функция `square` применяется к нередуцируемому выражению `4` и даёт нам `16`. А если так: ```haskell {.example_for_playground .example_for_playground_002} main :: IO () main = print . square $ 2 + 2 ``` Теперь функция `square` применяется уже к редуцируемому выражению `2 + 2`. Как вы думаете, что произойдёт раньше? Применение оператора сложения или же применение функции `square`? Вопрос хитрый, ведь правильного ответа на него нет, поскольку существует две модели вычисления аргументов, а именно: - энергичная (англ. eager), - ленивая (англ. lazy). При энергичной модели (называемой ещё «жадной» или «строгой») выражение, являющееся аргументом функции, будет вычислено ещё до того, как попадёт в тело функции. На фоне определения функции `square` будет яснее: ```haskell square x = x * x / \ square $ 2 + 2 \ / 4 = 4 * 4 = 16 ``` То есть видим выражение `2 + 2`, жадно на него набрасываемся, полностью вычисляем, а уже потом результат этого вычисления передаём в функцию `square`. При ленивой же модели всё наоборот: выражение, являющееся аргументом функции, передаётся в функцию прямо так, без вычисления. Изобразить это можно следующим образом: ```haskell square x = x * x / \ / \ / \ square $ 2 + 2 = (2 + 2) * (2 + 2) = 16 ``` Но какая разница, спросите вы? Всё равно в итоге получим `16`, хоть там сложили, хоть тут. Так и есть: модель вычисления не влияет на результат этого вычисления, но она влияет на путь к этому результату. Жадная модель нашла своё воплощение практически во всех современных языках программирования. Напишем на C: {#block-strange} ```c++ #include <stdio.h> int strange(int i) { return 22; } int main() { printf("%d\n", strange(2 / 0)); } ``` Функция `strange` действительно странная, ведь она игнорирует свой аргумент и просто возвращает число `22`. И всё же при запуске этой программы вы гарантированно получите ошибку `Floating point exception`, ибо компилятор языка C категорически не терпит деления на ноль. А всё потому, что язык C придерживается энергичной модели вычислений: оператор деления `2` на `0` будет вызван ещё до того, как мы войдём в тело функции `strange`, поэтому программа упадёт. Такой подход прямолинеен и строг: сказали нам сначала разделить на ноль — разделим, не задумываясь. Ленивая же модель придерживается иного подхода. Взгляните на Haskell-вариант: ```haskell {.example_for_playground} strange :: Int -> Int strange i = 22 main :: IO () main = print . strange $ 2 `div` 0 ``` Удивительно, но при запуске этой программы мы увидим: ```bash 22 ``` Впрочем, почему удивительно? Функция `strange`, проигнорировав свой аргумент, дала нам значение `22`, которое, попав на вход функции `print`, вылетело в наш терминал. Но где же ошибка деления `2` на `0`, спросите вы? Её нет. Ленивый подход вполне гармонирует со своим названием: нам лень делать работу сразу же. Вместо этого мы, подобно ребёнку, которого заставили убрать разбросанные по комнате игрушки, откладываем работу до последнего. Ленивая модель гарантирует, что работа будет выполнена лишь тогда, когда результат этой работы кому-то понадобится. Если же он никому не понадобится, тогда работа не будет выполнена вовсе. Функция `strange` ленива и потому рациональна. Она смотрит на свой аргумент `i`: ```haskell strange i = 22 ``` и понимает, что он нигде не используется в её теле. Значит, он не нужен. А раз так, то и вычислен он не будет. Кстати, если аргумент функции игнорируется, определение принято писать с универсальным образцом: ```haskell strange _ = 22 ``` Так и получается: ```haskell strange _ = 22 / \ strange $ 2 `div` 0 = 22 ``` Выражение, содержащее деление на ноль, попадает внутрь функции, будучи ещё невычисленным, но поскольку в теле функции оно нигде не используется, оно так и останется невычисленным. Девиз лени: если результат работы никому не нужен — зачем же её делать? Вот почему фактического деления на ноль здесь не произойдёт и программа не рухнет. Разумеется, если бы мы определили функцию `strange` иначе: ```haskell strange :: Int -> Int strange i = i + 1 ``` тогда другое дело: значение аргумента уже используется в теле функции, а значит вычисление аргумента непременно произойдёт: ```haskell strange i = i + 1 / \ / \ strange $ 2 `div` 0 = (2 `div` 0) + 1 ``` Оператору сложения требуется значение обоих своих аргументов, в том числе левого, а потому получите ошибку деления на ноль. ## Как можно меньше До тех пор, пока результат вычисления никому не нужен, оно не производится. Однако даже тогда, когда результат кому-то понадобился, вычисление происходит не до конца. Помните, выше я сказал, что при жадной модели вычисления выражение, являющееся аргументом, вычисляется «полностью»? А вот при ленивой модели мы вычисляем выражение лишь настолько, насколько это необходимо. Как вышеупомянутый ребёнок, убирающий игрушки в комнате, убирает их вовсе не до конца, а лишь до такой степени, чтобы его не ругали родители. С точки зрения вычисления любое выражение в Haskell проходит через три стадии: 1. невычисленное, 2. вычисленное не до конца, 3. вычисленное до конца. Невычисленным называется такое выражение, которое вообще не трогали. Вспомним вышеупомянутое деление на ноль: ```haskell 2 `div` 0 ``` Мы увидели, что программа не упала, и это говорит нам о том, что деления не было. То есть функция `div` так и не была применена к своим аргументам. Вообще. Такое выражение называют thunk (можно перевести как «задумка»). То есть мы задумали применить функцию `div` к `2` и к `0`, приготовились сделать это — но в итоге так и не сделали. Вычисленным до конца называют такое выражение, которое вычислено до своей окончательной, нередуцируемой формы. О таком выражении говорят как о выражении в «нормальной форме» (англ. normal form). А вот вычисленным не до конца называют такое выражение, которое начали было вычислять, но сделали это не до конца, то есть не до нормальной формы, а до так называемой «слабой головной формы» (англ. Weak Head Normal Form, WHNF). Вы спросите, как же это можно вычислить выражение не до конца? Рассмотрим пример: ```haskell {.example_for_playground} main :: IO () main = let cx = 2 / 6.054 -- thunk nk = 4 * 12.003 -- thunk coeffs = [cx, nk] -- thunk in putStrLn "Nothing..." ``` Есть у нас два коэффициента, `cx` и `nk`, и ещё список `coeffs`, в который мы поместили эти коэффициенты. Но, как мы видим, в итоге ни эти коэффициенты, ни этот список нам не понадобились: мы просто вывели строку и тихо вышли. В этом случае ни одно из этих выражений так и не было вычислено, оставшись в виде thunk. То есть оператор деления так и не был применён к `2` и `6.054`, оператор умножения не прикоснулся ни к `4`, ни к `12.003`, а список остался лишь в наших умах. Ленивая стратегия рациональна: зачем тратить компьютерные ресурсы на создание того, что в итоге никому не понадобится? Изменим код: ```haskell {.example_for_playground} main :: IO () main = let cx = 2 / 6.054 -- thunk nk = 4 * 12.003 -- thunk coeffs = [cx, nk] -- WHNF in print $ length coeffs ``` Ага, уже интереснее. В этот раз захотелось нам узнать длину списка `coeffs`. В этом случае нам уже не обойтись без списка, иначе как же мы узнаем его длину? Однако фокус в том, что выражение `[cx, nk]` вычисляется не до конца, а лишь до той своей формы, которая удовлетворит функцию `length`. Задумаемся: функция `length` возвращает число элементов списка, но какое ей дело до содержимого этих элементов? Ровным счётом никакого. Поэтому в данном случае список формируется из thunk-ов: ```haskell coeffs = [thunk, thunk] ``` Первым элементом этого списка является thunk, ассоциированный с невычисленным выражением `2 / 6.054`, а вторым элементом списка является thunk, ассоциированный с невычисленным выражением `4 * 12.003`. Фактически, список `coeffs` получился как бы не совсем настоящим, пустышечным: он был сформирован в памяти как корректный список, однако внутри обоих его элементов — вакуум. И всё же даже такая его форма вполне подходит для функции `length`, которая и так прекрасно поймёт, что в списке два элемента. О таком списке говорят как о выражении в слабой головной форме. Ещё чуток изменим код. Перечислите разделенные пробелом стадии, на которых находятся `cx`, `nk` и `coeff`: {.task_text} - thunk, если выражение невычисленное, - whnf, если вычисленное не до конца, - normal, если вычисленное до конца. {.task_text} ```haskell {.example_for_playground} main :: IO () main = let cx = 2 / 6.054 -- ? nk = 4 * 12.003 -- ? coeffs = [cx, nk] -- ? in print $ coeffs !! 1 ``` ```consoleoutput {.task_source #haskell_chapter_0170_task_0010} ``` Оператор `!!` извлекает из списка элемент по индексу, в данном случае нас интересует второй по счёту элемент. Теперь нам уже недостаточно просто сформировать список, нам действительно нужен его второй элемент, иначе как бы мы смогли вывести его на консоль? В этом случае выражение `4 * 12.003` будет вычислено до своей окончательной, нормальной формы, а результат этого вычисления ляжет вторым элементом списка, вот так: `coeffs = [thunk, 48.012]`. Однако первый элемент списка так и остался невостребованным, поэтому выражение `2 / 6.054` по-прежнему остаётся лишь нашей мыслью, не более чем. В этом случае список `coeffs` всё равно остаётся в слабой головной форме, ведь внутри первого его элемента всё ещё вакуум. {.task_hint} ```haskell {.task_answer} thunk normal whnf ``` И снова перепишем код. Перечислите разделенные пробелом стадии, на которых находятся `cx`, `nk` и `coeff`: {.task_text} - thunk, если выражение невычисленное, - whnf, если вычисленное не до конца, - normal, если вычисленное до конца. {.task_text} ```haskell {.example_for_playground} main :: IO () main = let cx = 2 / 6.054 -- ? nk = 4 * 12.003 -- ? coeffs = [cx, nk] -- ? in print coeffs ``` ```consoleoutput {.task_source #haskell_chapter_0170_task_0020} ``` Список `coeffs` должен быть выведен на консоль полностью, а следовательно, оба его элемента должны быть вычислены до своей нормальной формы, в противном случае мы не смогли бы показать их в консоли. Вот, теперь никакой лени. {.task_hint} ```haskell {.task_answer} normal normal normal ``` Вот философия ленивой стратегии: даже если нам нужно вычислить выражение, мы вычисляем его лишь до той формы, достаточной в конкретных условиях, и не более того. ## Рациональность Как уже было упомянуто, ленивая стратегия помогает программе быть рациональной и не делать лишнюю работу. Рассмотрим пример: ```haskell {.example_for_playground} main :: IO () main = print $ take 5 evens where evens = [2, 4 .. 100] ``` Список `evens`, формируемый через арифметическую последовательность, содержит в себе чётные числа от `2` до `100` включительно. Используется этот список в качестве второго аргумента стандартной функции `take`, которая даёт нам N первых элементов из переданного ей списка. При запуске этой программы мы получим ожидаемый результат: ``` [2,4,6,8,10] ``` В чём же здесь рациональность, спросите вы? А в том, что список `evens` в итоге содержал в себе лишь 5 элементов. Да, но ведь чётных чисел от `2` до `100` куда больше, нежели пять! Совершенно верно, но лень позволяет нам сделать лишь столько работы, сколько реально требуется. Раз уж список `evens` нужен лишь функции `take`, которая, в свою очередь, хочет только пять первых его элементов — зачем же создавать оставшиеся элементы? Нужно первые пять — получи пять. Если же напишем так: ```haskell {.example_for_playground} main :: IO () main = print $ take 50 evens where evens = [2, 4 .. 100] ``` тогда в списке `evens` окажется уже пятьдесят элементов, потому что именно столько запросила функция `take`. Повторю философию ленивого рационализма: сделаем не столько, сколько нам сказали, а лишь столько, сколько действительно понадобится. ## Бесконечность А что будет, если мы запросим из списка `evens` 500 элементов? Вот так: ```haskell {.example_for_playground} main :: IO () main = print $ take 500 evens where evens = [2, 4 .. 100] ``` Ничего страшного не случится, функция `take` проверяет выход за границы и в случае, если её первый аргумент превышает длину списка, она просто даёт нам тот же список. Да, но ведь мы хотим увидеть пятьсот чётных чисел, а не пятьдесят! Можно было бы увеличить список: ```haskell {.example_for_playground} main :: IO () main = print $ take 500 evens where evens = [2, 4 .. 100000] ``` но это ненадёжно, ведь потом опять может потребоваться ещё больше. Нужно что-нибудь универсальное, и в Haskell есть подходящее решение: бесконечная последовательность. Мы уже [обсуждали](/courses/haskell/chapters/haskell_chapter_0100/#infinite-range) ее в главе про последовательности. ```haskell {.example_for_playground} main :: IO () main = print $ take 500 evens where evens = [2, 4 ..] -- Бесконечная последовательность ``` Теперь не сомневайтесь: в списке `evens` будет не менее пятисот чётных чисел. Мы создали бесконечный список, указав начало и второй элемент, но пропустив указание последнего элемента. Так и получился бесконечный список: ```haskell [2, 4 ..] ``` Именно ленивая модель вычислений позволяет нам работать с бесконечными структурами данных. Вот прямо так, начиная с двойки и, с шагом через один, уходим в бесконечные дали... Шучу. На самом деле, список получится вовсе не бесконечным, а настолько большим, насколько нам это понадобится. В самом деле, если функция `take` требует от нас N элементов — зачем нам вообще задавать окончание диапазона списка? Всё равно в нём будет не более чем N. Бесконечная структура данных тем и полезна, что из неё всегда можно взять столько, сколько требуется. Конечно, если бы мы решили похулиганить: ```haskell main :: IO () main = print evens -- Дай нам всё! where evens = [2, 4 ..] ``` в этом случае в нашу консоль быстро посыпалось бы очень много чисел... Но при разумном использовании бесконечные последовательности хорошо себя зарекомендовали для решения целых классов задач. Вы уже [знаете](/courses/haskell/chapters/haskell_chapter_0140/) про две функции высшего порядка для работы со списками: `map` и `filter`. Есть и еще одна: `zip lst1 lst2`. Она принимает два списка и составляет из них единый список поэлементных пар. Функция полезна, если требуется обойти два списка одновременно. {.task_text} Например, вот такое применение `zip ['A', 'B'] [True, False, True]` создаст список `[('A', True), ('B', False)]`. Обратите внимание, что функция обрезала более длинный список до короткого. {.task_text} Напишите функцию `numerate`, которая принимает начальное значение и список строк. Функция нумерует эти строки, начиная с заданного значения. Она возвращает список пар, где первый элемент — номер, а второй — строка. {.task_text} Например, вот такое применение `numerate 1 ["Rust", "Python", "Go"]` создаст список `[(1, "Rust"), (2, "Python"), (3, "Go")]`. {.task_text} В своем решении используйте функцию `zip` и бесконечный список. {.task_text} ```haskell {.task_source #haskell_chapter_0170_task_0030} module Main where -- Your code here main :: IO () main = do print $ numerate 0 ["Rust", "Python", "Go"] print $ numerate 1 ["+", "-", "=", ">"] ``` Синтаксис создания бесконечного списка: `[firstElem, secondElem ..]`. {.task_hint} ```haskell {.task_answer} module Main where numerate :: Int -> [String] -> [(Int, String)] numerate num lst = zip [num, num+1 ..] lst main :: IO () main = do print $ numerate 0 ["Rust", "Python", "Go"] print $ numerate 1 ["+", "-", "=", ">"] ```