что такое ленивые вычисления в с
Ленивые вычисления.
Обсудим стратегию вычислений в Haskell.
Большинство языков программирования используют строгую модель вычислений. Haskell использует нестрогие вычисления (иногда называемые “ленивыми”).
На базовом уровне, нестрогие вычисления означают, что большинство выражений вычисляются только при необходимости. Когда процесс вычисления начинается, для каждого выражения создаётся “задумка” (thunk – иногда можно встретить кальку “санк” или “занк”, реже “клауза”; устоявшегося перевода видимо пока нет). “Задумку” можно представить как инструкцию для вычисления и область памяти для хранения результата этого вычисления в графе вычисления программы.
Если результат вычисления используется в какой-то момент в процессе выполнения программа, “задумка” вычисляется и результат вычисления сохраняется (так, что вычисление происходит только один раз). Если результат не используется, то “задумка” не вычисляется и впоследствии удаляется сборщиком мусора.
Общий принцип такой: выражения не вычисляются, пока они не нужны, и не вычисляются повторно, если этого можно избежать. Мы обсудим как это работает, какие есть исключения, и как добавить строгость при необходимости.
Расходящиеся вычисления
В рамках анализа типов в строго типизированных тьюринг-полных языках обычно вводят тип Bottom, который является подтипом всех типов. Этот тип назначается результатам расходящихся вычислений – вычислений, которые никогда не завершаются или завершаются ошибкой. У типа Bottom нет никаких значений, и он вводится исключительно как теоретическая конструкция – действительно, при проверке типов невозможно назначить тип Bottom ничему, поскольку для этого нужно было бы решить проблему останова (которая как известно алгоритмически неразрешима).
Если бы Haskell был строгим, любое использование undefined или error гарантированно приводило бы к ошибке времени выполнения. Однако при нестрогих вычислениях, если значение ⊥ не используется, то оно не вычисляется, и, следовательно, не генерирует ошибку времени выполнения. Мы используем этот факт в дальнейшем при обсуждении строгости.
Отличие нестрогости и ленивости
Технически, стандарт Haskell определяет вычисления как нестрогие, но не ленивые. Основное отличие в том, что истинно ленивый язык запоминает результаты всех вычислений с целью переиспользования. Такой подход на практике потребляет неприемлемо большой объём памяти, поэтому за исключением исследовательских проектов практически не применяется. Нестрогость не требует сохранения результатов вычислений, а только того, что неиспользуемые результаты не вычисляются.
В качестве примера, следующий код работает только в силу нестрогости:
Стандарт таким образом требует только чтобы конечное поведение соответствовало нестрогой семантике, и не накладывает конкретных ограничений на детали реализации и повторные вычисления.
Порядок вычисления
При обсуждении стратегий редукции λ-исчисления, мы уже обсуждали строгие и нестрогие вычисления. “На пальцах” можно считать, что строгие вычисления производятся “изнутри наружу”, т.е. сначала вычисляются внутренние термы, затем внешние. Нестрогие вычисления производятся “снаружи внутрь”, т.е. сначала вычисляется внешний терм. Как следствие, порядок вычисления и что именно вычисляется, может определяться вводом.
Рассмотрим следующий код:
Та же идея с аналогичным поведением в более читаемом Haskell:
Когда мы говорим, что вычисление работает “снаружи внутрь”, мы говорим о вычислении вложенных выражений. Причём мы не только начинаем с самого внешнего выражения, мы ещё и не вычисляем подвыражения, которые не используются непосредственно в результате.
Нестрогость делает Haskell более выразительным, в том смысле, что мы можем ссылаться на значения, которые ещё не вычислены. В строгих языках, нельзя просто связать вычисление с именем, не произведя это вычисление.
Этот паттерн применим и к структурам данных. Так, например, мы можем вычислить длину списка, не трогая его значений:
Принудительная строгость
Семантика seq в терминах ⊥ определяется следующим образом:
Weak Head Normal Form
Когда мы говорим, что seq форсирует вычисление первого аргумента, на самом деле мы имеем ввиду что вычисление производится к слабой головной нормальной форме (WHNF), а не к полной нормальной форме. Вычисление WHNF означает, что вычисление останавливается на первом встреченном конструкторе данных или лямбда-выражении:
Форсирование без seq
notForcing не производит непосредственно сопоставления с шаблоном, только связывает вычисление с именем _ (которое игнорируется).
GHC Core
GHC использует двухуровневую модель компиляции, первый этап транслирует Haskell в язык GHC Core, в целом более простой (в смысле количества конструкций), а GHC Core уже компилируется в машинный код.
Вывод будет иметь вид:
В языке GHC Core выражения case всегда форсируют вычисления. Из этого вывода мы можем сказать, что значение вычисления, обозначенного b_a1yq должно быть вычислено до вычисления результата. I# 0# это представление числовых литералов в GHC Core.
Если аналогично рассмотреть предыдущий пример, то получится следующее:
Если мы выведем Core для кода
мы обнаружим, что имени x в выводе вообще нет:
GHC видит, что x не используется, и убирает его сразу же. Если же мы его форсируем при помощи seq
то увидим следующий код:
Следует отметить, что в Haskell выражения case форсируют значения только при сопоставлении с шаблоном, выражение
не форсирует значение x поскольку сопоставления с шаблоном нет. В Core, выражения case всегда форсируют вычисление.
“Задумки”
Также вычисление прекращается как только обнаружено выражение, не являющееся конструктором данных:
Несмотря на то, что id 3 – примитивное вычисление, GHC оставляет его как есть.
И это не относится к полиморфным значениям:
Здесь list’ – не вычисляется, поскольку ++ – это функция.
Разделение
Именованные вычисления могут повторно использоваться в любом месте, где они встречаются. Это означает, что результаты вычисления разделяются между местами использования. Разделение вычислений позволяет более эффективно использовать память. Следует отметить, что GHC может произвольно включать и выключать разделение в чистом коде – в основном это делается с целью ускорения выполнения. В монаде IO разделение вычислений всегда отключается.
Рассмотрим два примера:
Как мы видим, в первом случае, и x и y вычисляются. Во втором случае, x вычисляется только один раз, хотя используется дважды. Отдельно следует отметить, что компилятор не обязательно применяет разделение для функций с одинаковыми аргументами. Например следующая программа:
то есть функция trace «x» 1 вычисляется дважды.
выведет x только один раз.
Из этого можно вывести следующее правило: если вычисление используется несколько раз, лучше связать его с именем. Это также может повысить читаемость кода.
Функции могут разделяться, но только если они не имеют именованных аргументов. Так, при вычислении следующих двух функций порядок вычисления различный:
Бесточечная нотация таким образом позволяет более эффективно разделять память.
Разделению так же препятствует полиморфизм: полиморфные значения не заделяются. Причина в том, что ограничения классов типов в Core выражаются дополнительными аргументами, а функции не разделяются.
Опровержимые и неопровержимые шаблоны
При разговоре о сопоставлении с шаблоном и строгости, необходимо делать разницу между опровержимыми и неопровержимыми шаблонами.
Неопровержимые шаблоны – это шаблоны, сопоставление с которыми всегда успешно. К неопровержимым шаблонам относятся имена без конструкторов, например
y является неопровержимым шаблоном.
Ключевое, что необходимо помнить: неопровержимые шаблоны не форсируют вычисление
Haskell позволяет пометить шаблоны неопровержимыми, чтобы отложить сопоставление с шаблоном до места использования (или вообще не производить в случае отсутствия использования). Для этого перед шаблоном ставится символ
. Это может быть удобно для типов данных с одним конструктором:
Следует однако отметить, что форсирование аргументов может быть хорошей идеей для более предсказуемого поведения.
Дополнительно следует иметь ввиду, что шаблоны в левой части let-выражения по умолчанию являются неопровержимыми:
соответственно шаблон в левой части ведёт себя точно так же, как аргумент функции.
Использование fail с GHC 8.0 требует класса MonadFail :
Если при использовании шаблона в левой части компилятор сообщает об отсутствующем экземпляре MonadFail – теперь Вы знаете почему.
Форсирование шаблонов
Это расширение позволяет пометить неопровержимые шаблоны как строгие, например:
По сути это эквивалентно использованию seq :
Более того, если сравнить вывод Core, то он одинаковый:
Но нотация строгих шаблонов короче и часто легче читается.
Строгость в конструкторах данных
Конструкторы данных вообще говоря являются нестрогими, т.е. для
тогда вычисление значений к WHNF так же будет вычислять и строгие аргументы:
вызов test (Test undefined) завершится ошибкой.
Идея в том, что иногда дешевле сразу вычислить значение, чем хранить “задумку” этого вычисления – если мы уверены, что результат рано или поздно всё равно понадобится, или вычисление само по себе очень быстрое. Такие аннотации строгости часто встречаются в вычислительном коде, где множества Int и Double дешевле вычислить сразу, чем конструировать и хранить “задумки” их вычислений.
Расширения Strict и StrictData
В GHC 8.0 добавлены расширения языка Strict и StrictData. Первое делает неопровержимые шаблоны, не помеченные явно
Ленивые вычисления
____ Много есть информации под boost, так же не отстает шарп и опережает всех хаскель. В плюсах только со стандарта C++0x. Даже попалась цельная Qt-шная библиотека для этого дела. Вообще концепция ленивых вычислений зародилась для функциональных языков. Но это все придумано, если возвращаться к C++, для удобства оперирования функторами и еще каких-то таинств. Но по сути же простые «ленивые вычисления» доступны во многих языках, компиляторы которых действуют по некоему принципу call by value. То есть когда значение получено, дальше его обсчитывать смысла нет. Если первый операнд операции && ложен, то вычислять следующие не нужно.
____ Общий смысл «ленивых вычислений» в том, что экономится время на проведении вычислений, результаты которых заведомо не будут использованы в дальнейшем программой. Соответственно, за счет снижения объемов вычислений повышается и производительность программы, а за счет отсутствия необходимости хранить в памяти результаты вычислений снижаются и требования программы к памяти. Помимо этого, ленивые вычисления избавляют программиста от необходимости следить за тем, какие именно вычисления будут в дальнейшем востребованы программой, а какие, напротив, окажутся совершенно бесполезными. Последнее не всегда хорошо, учитывая опять же гибкость плюсов, в которых компилятор не даст, вопреки обычному подходу, поступать как заблагорассудится программисту. Но на то в принципе и расчет.
Принцип «ленивого вычисления» проще всего рассмотреть на следующем примере:
Ленивые вычисления в C++
Как переопределить операторы так, чтобы можно было запомнить формулу, чтобы вычислить её по.
Получение i-ого элемента массива без вычисления всех элементов (Ленивые вычисления)
Здравствуйте! Необходимо в цикле получать каждый i-й элемнент. Работаю с массивами массивов целых.
Ленивые вычисления
Добрый вечер, Уважаемые форумчане! Есть вот такое задание: С помощью класса Stream опишите.
Ленивые вычисления или «я что-то пропустил и в c# есть ссылки на строки?»
Доброго дня, уважаемые члены форума! Прошу знающих людей подсказать верный путь к решению такой.
Ленивые вычисления
Одной из «визитных карточек» Хаскеля являются отложенные, или ленивые, вычисления. Эта особенность языка не только открывает множество возможностей, но и создаёт некоторые проблемы, особенно со скоростью работы программ.
В этой статье я постараюсь объяснить: что такое ленивые вычисления, для чего они могут применяться и как избежать потери производительности при их использовании.
Что такое ленивые вычисления?
В обычных, не ленивых, языках программирования вычисления строгие — то есть аргументы функции вычисляются перед выполнением самой функции.
Например, в каком-то абстрактном строгом языке программирования:
А в ленивых языках, в том числе Хаскеле, вычисления отложенные. Все вычисления (кроме некоторых функций ввода-вывода), не выполняются сразу, а как бы откладываются до реальной надобности.
Тот же пример в Хаскеле:
На этом примере хорошо видно, что вычисление подвыражений (5+3 и 4*4) откладывалось до последнего, а именно до момента, когда их пришлось сравнить.
Здесь «силой» что заставила вычисление выполниться можно считать вывод на консоль, т.е. IO. Но это не единственный способ.
Обещания
Возьмём такой пример:
z представляет собой обещание (англ. thunk), просто не вычисленное значение.
А что будет если сравнить с образцом z?
Чтобы проверить, что y — список, компилятор вычисляет его до вида: *обещание* : *обещание*
Потом, он вычисляет первое обещание: ‘l’ : *обещание*
И удостоверившись, что y — список, начинающийся с ‘l’, он производит сопоставление с образцом: ‘l’:ys = ‘l’:*обещание*
В данном примере, ys будет обещанием, соответствующим оставшейся части списка y.
Давайте посмотрим на то, как менялась глубина вычисления для z на протяжении всех примеров:
*обещание*
(*обещание*, *обещание*)
(*обещание*, ‘l’:*обещание*)
Ленивые функции
Есть простой способ проверить ленива ли функция в каком-либо аргументе. Нужно просто передать ей заместо аргумента undefined, и если результатом будет ошибка, то функция строга в этом аргументе, а если нет, то ленива.
Не приведут к ошибке:
const 5 undefined
Just undefined
length undefined
head undefined
Ленивое сравнение с образцом
Ленивыми могут быть не только функции, но и сравнения с образцом. В отличии от строгих сопоставлений с образцом, которые мы уже рассматривали, ленивые не заставляют обещания вычисляться, то есть не «развёртывают» их во время компиляции.
Например:
(x, y) = 1
> f undefined
1
(x, y) — ленивый образец. Он имеет то же свойство, что и аргумент ленивой функции: когда мы передаём туда undefined, ошибки не возникает.
Такое сравнение с образцом можно встретить в Control.Arrow:
> (const 1 *** const 2) undefined
(1, 2)
Но нужно помнить, что ленивый образец стоит использовать, только когда у типа один конструктор.
К примеру:
Так как мы указали, что не надо вычислять аргумент функции пока он не потребуется, не возможно узнать, что перед нами: пустой список или одно его звено. Функция будет всегда возвращать undefined, ведь в первом выражении мы использовали неопровержимый образец.
Использование ленивых вычислений
Вычисление по требованию
Самый очевидный плюс ленивых вычислений — если что-то не требуется, оно не будет вычислено.
Например:
(&&) False _ = False
(&&) True a = a
Если первый аргумент функции and — False, зачем вычислять второй, если и так понятно, что результатом будет False? Возможно чтобы узнать значение второго аргумента, потребуется произвести множество трудоёмких вычислений, которых, используя ленивые вычисления, можно избежать.
Представим, что Вы хотите найти 3 наименьших элемента списка.
В Хаскеле это можно сделать так:
Но в строгом языке это расточительно, так как придётся отсортировать весь список. Но с ленивыми вычислениями, мы отсортируем список до третьего элемента и остановимся, потому что продолжать вычисление не имеет смысла.
Мемоизация
Рассмотрим такую функцию:
Сколько раз была вычислена сумма 5 и 3? Правильный ответ: один раз. Сначала (5+3) — просто обещание, но когда оно было передано функции plus, оно вычислилось и его ответ заместил само обещание. Когда значение a потребовалось во второй раз, программа просто взяла готовый результат из бывшего обещания, не производя никаких вычислений. В этом заключается одно из важнейших свойств ленивых вычислений — мемоизация. Обещание в ленивом языке вычисляется только один раз, а потом результат вычисления «затирает» собой обещание, тем самым давая программе возможность просто узнать ответ, без необходимости вычислять его опять.
Такое свойство ленивых вычислений находит применение в динамическом программировании, что было хорошо показано в статье Динамическое программирование и ленивые вычисления.
Бесконечные и цикличные структуры данных
Ещё одно, довольно известное применение отложенных вычислений — создание бесконечных структур данных.
Здесь мы создаём бесконечный список нечётных чисел, и берём его 10-ый элемент.
Теперь перейдём к цикличным структурам данных.
Как нам связать два элемента этого типа в кольцо, так, чтобы поле next одного объекта указывало на другой?
Если бы мы хотели осуществить это в императивном языке, мы бы использовали указатели, но в Хаскеле указателей нет. Так как создать такую структуру?
Очень просто:
let x = List «x» y
y = List «y» x
in x
Вот и всё. Так как поле next у List ленивое (надо помнить, что конструктор типов такая же функция, и его аргументы могут быть ленивыми) создание такого «кольца» не приведёт к зависанию программы в попытках вычислить всю структуру.
Ленивый ввод-вывод
Действительно строгими являются только простые функции ввода-вывода, а остальные — ленивые. Это даёт возможность читать и писать в файлы на лету, как по конвейеру, без использования буферов.
Например:
Программа будет выводить текст в верхнем регистре по мере его поступления.
Проблемы, связанные с использованием ленивых вычислений
На протяжении всей статьи я использовал термин «обещание», чтобы обозначить некую единицу ленивого вычисления, но дело в том, что это не просто абстрактное понятие. Скомпилированная программа на Хаскеле в действительности использует обещания, которые занимают место в памяти и на стеке. То есть, к расходам на обычные вычисления добавляется сборка мусора, выделение памяти, разворачивание обещаний. В этом и заключается главная проблема ленивых вычислений — за их неграмотное использование можно поплатиться сильным снижением производительности, переполнениями стека и большим потреблением памяти.
Но существуют способы, как сделать вычисления менее ленивыми, которые мы сейчас и рассмотрим.
Рассмотрим такой простой пример:
Здесь мы находим сумму чисел от 1 до 1e6 и выводим её в консоль. Но если вы попытаетесь запустить программу, то увидите такое сообщение:
Так как вычисление sum’ ls откладывается, мы получаем множество вложенных обещаний, занимающих место на стеке. Чтобы избавиться от этого, надо как-то заставить обещания вычисляться, а не накапливаться. И для этого у нас есть функция seq. Она принимает два аргумента, первый из которых вычисляется, а второй возвращается. Давайте попробуем применить её здесь.
Для начала перепишем функцию sum’ на использование хвостовой рекурсии:
Теперь заставить сложение вычисляться будет не сложно:
Seq заставляет сумму вычислиться, заместо того, чтобы отложить сложение на потом.
Теперь ошибки не происходит.
Попробуем чуть усложнённый пример: кроме суммы элементов подсчитаем и их число.
Немного некрасиво, но работает. Ситуация, когда нужно вычислить что-либо полностью, не так редка, так что для этого был создан специальный модуль. Давайте его опробуем:
Функция deepseq вычисляет значения полностью, до Normal Form.
Bang patterns
Для более удобного указания строгости, было создано расширение компилятора — Bang patterns. Оно позволяет указывать строгость аргументов просто восклицательным знаком. С использованием этого расширения, мы можем переписать наш код так:
Всё будет работать, как и прежде.
Bang patterns позволяют нам указывать строгость не только аргументов функций, но и полей структур данных, например:
SPair — строгая пара. Значения в её полях будут всегда вычислены, что, опять же, не позволяет обещаниям скапливаться.
Заключение
В этой статье, я постарался объяснить как совладать с ленивыми вычислениями. Надеюсь после её прочтения Вы начнёте понимать, где и как лучше применять отложенные вычисления, зачем они вообще нужны.
butaji
the story of my tech.life
Lazy Computation in C# (Ленивые вычисления в C#)
Немного теории.
Большинство современных языков разработки, используемых на практике (таких как C#, VB.NET, C++, Python и Java) реализуют так называемые немедленные вычисления, это означает, что операция выполняется, так только становятся известны значения её операндов. Однако, ясно, что немедленное вычисление многих функций не всегда необходимо и рационально с точки зрения производительности, поэтому само собой напрашивается решение, позволяющее отложить эти вычисления на тот момент, когда они нам будут действительно нужны.
Мартин Фаулер в свой книге PoEAA вводит понятие паттерна Lazy Load (загрузка по требованию, ленивая загрузка), суть которого состоит в том, что объект не содержит данные, но знает где их взять, если они ему станут нужны. Это как раз то, о чём мы и ведем речь, следовательно воспользуемся этим шаблоном.
Реализовать данный шаблон можно несколькими различными вариантами:
Примеры реализации.
В рассмотренном ниже примере мы воспользуемся первым способом, как наиболее наглядным и простым в реализации.
Данный класс имеет три поля:
Как же можно использовать данный класс
Результат работы программы:
Мы наглядно видим, как в поле func заносится лямба-выражение, результат которого выводится после вызова свойства Value. Причём повторный вызов свойства выводит кэшированные данные.
Далее, думаю стоит написать обертку-помощник для нашего класса, с целью повышения наглядности работы с ним.
Используя класс Lazy мы можем создать экземпляр нашего типа, вызвав метод Lazy.New вместо написания new Lazy к примеру. Для ещё пущего повышения наглядности будем использовать атрибут var.
Все наши приобритения продемонстрированы Выше в примере, расчитывающий сумму и произведения двух чисел.
Далее хотелось бы рассмотреть пример со значениями аргументов в качестве значений, инициализируемых по требованию, что несомненно очень удобно при использовании такого языка, как C#, в котором инициализация аргументов происходит немедленно.
Как хорошо видно в данном примере, один из аргументов метода может не использоваться вовсе.
Напишем обработчик для данного метода и посмотрим, какие из аргументов будут проинициализированы:
Повторим запуск приложения:
Пример: Список шрифтов с предосмотром.
.png "что такое ленивые вычисления в с. Смотреть фото что такое ленивые вычисления в с. Смотреть картинку что такое ленивые вычисления в с. Картинка про что такое ленивые вычисления в с. Фото что такое ленивые вычисления в с")
Наш класс для хранения информации о шрифтах будет следующим:
Метод для генерации и отрисовки изображения шрифта:
На загрузке формы нашего приложения связываем наши значения с методом выбора шрифта из списка.
При изменении выбранного шрифта перерисовываем изображение:
Заключение
В данной статье Вы ознакомились с реализацией паттерна “загрузка по требованию” на языке C#, данный шаблон предоставляет великолепные возможности откладывать вычисления до того момента, пока они не будут действительно необходимы. Так же вспомнили те возможности C# версии 3.0, которые делают код нагляднее, а его написание проще (Неявное объявление типов, анонимные методы и лямбда-выражения, операторы запросов, и анонимные типы)
Ленивые вычисления
Одной из «визитных карточек» Хаскеля являются отложенные, или ленивые, вычисления. Эта особенность языка не только открывает множество возможностей, но и создаёт некоторые проблемы, особенно со скоростью работы программ.
В этой статье я постараюсь объяснить: что такое ленивые вычисления, для чего они могут применяться и как избежать потери производительности при их использовании.
Что такое ленивые вычисления?
В обычных, не ленивых, языках программирования вычисления строгие — то есть аргументы функции вычисляются перед выполнением самой функции.
Например, в каком-то абстрактном строгом языке программирования:
А в ленивых языках, в том числе Хаскеле, вычисления отложенные. Все вычисления (кроме некоторых функций ввода-вывода), не выполняются сразу, а как бы откладываются до реальной надобности.
Тот же пример в Хаскеле:
На этом примере хорошо видно, что вычисление подвыражений (5+3 и 4*4) откладывалось до последнего, а именно до момента, когда их пришлось сравнить.
Здесь «силой» что заставила вычисление выполниться можно считать вывод на консоль, т.е. IO. Но это не единственный способ.
Обещания
Возьмём такой пример:
z представляет собой обещание (англ. thunk), просто не вычисленное значение.
А что будет если сравнить с образцом z?
Чтобы проверить, что y — список, компилятор вычисляет его до вида: *обещание* : *обещание*
Потом, он вычисляет первое обещание: ‘l’ : *обещание*
И удостоверившись, что y — список, начинающийся с ‘l’, он производит сопоставление с образцом: ‘l’:ys = ‘l’:*обещание*
В данном примере, ys будет обещанием, соответствующим оставшейся части списка y.
Давайте посмотрим на то, как менялась глубина вычисления для z на протяжении всех примеров:
*обещание*
(*обещание*, *обещание*)
(*обещание*, ‘l’:*обещание*)
Ленивые функции
Есть простой способ проверить ленива ли функция в каком-либо аргументе. Нужно просто передать ей заместо аргумента undefined, и если результатом будет ошибка, то функция строга в этом аргументе, а если нет, то ленива.
Не приведут к ошибке:
const 5 undefined
Just undefined
length undefined
head undefined
Ленивое сравнение с образцом
Ленивыми могут быть не только функции, но и сравнения с образцом. В отличии от строгих сопоставлений с образцом, которые мы уже рассматривали, ленивые не заставляют обещания вычисляться, то есть не «развёртывают» их во время компиляции.
Например:
(x, y) = 1
> f undefined
1
(x, y) — ленивый образец. Он имеет то же свойство, что и аргумент ленивой функции: когда мы передаём туда undefined, ошибки не возникает.
Такое сравнение с образцом можно встретить в Control.Arrow:
> (const 1 *** const 2) undefined
(1, 2)
Но нужно помнить, что ленивый образец стоит использовать, только когда у типа один конструктор.
К примеру:
Так как мы указали, что не надо вычислять аргумент функции пока он не потребуется, не возможно узнать, что перед нами: пустой список или одно его звено. Функция будет всегда возвращать undefined, ведь в первом выражении мы использовали неопровержимый образец.
Использование ленивых вычислений
Вычисление по требованию
Самый очевидный плюс ленивых вычислений — если что-то не требуется, оно не будет вычислено.
Например:
(&&) False _ = False
(&&) True a = a
Если первый аргумент функции and — False, зачем вычислять второй, если и так понятно, что результатом будет False? Возможно чтобы узнать значение второго аргумента, потребуется произвести множество трудоёмких вычислений, которых, используя ленивые вычисления, можно избежать.
Представим, что Вы хотите найти 3 наименьших элемента списка.
В Хаскеле это можно сделать так:
Но в строгом языке это расточительно, так как придётся отсортировать весь список. Но с ленивыми вычислениями, мы отсортируем список до третьего элемента и остановимся, потому что продолжать вычисление не имеет смысла.
Мемоизация
Рассмотрим такую функцию:
Сколько раз была вычислена сумма 5 и 3? Правильный ответ: один раз. Сначала (5+3) — просто обещание, но когда оно было передано функции plus, оно вычислилось и его ответ заместил само обещание. Когда значение a потребовалось во второй раз, программа просто взяла готовый результат из бывшего обещания, не производя никаких вычислений. В этом заключается одно из важнейших свойств ленивых вычислений — мемоизация. Обещание в ленивом языке вычисляется только один раз, а потом результат вычисления «затирает» собой обещание, тем самым давая программе возможность просто узнать ответ, без необходимости вычислять его опять.
Такое свойство ленивых вычислений находит применение в динамическом программировании, что было хорошо показано в статье Динамическое программирование и ленивые вычисления.
Бесконечные и цикличные структуры данных
Ещё одно, довольно известное применение отложенных вычислений — создание бесконечных структур данных.
Здесь мы создаём бесконечный список нечётных чисел, и берём его 10-ый элемент.
Теперь перейдём к цикличным структурам данных.
Как нам связать два элемента этого типа в кольцо, так, чтобы поле next одного объекта указывало на другой?
Если бы мы хотели осуществить это в императивном языке, мы бы использовали указатели, но в Хаскеле указателей нет. Так как создать такую структуру?
Очень просто:
let x = List «x» y
y = List «y» x
in x
Вот и всё. Так как поле next у List ленивое (надо помнить, что конструктор типов такая же функция, и его аргументы могут быть ленивыми) создание такого «кольца» не приведёт к зависанию программы в попытках вычислить всю структуру.
Ленивый ввод-вывод
Действительно строгими являются только простые функции ввода-вывода, а остальные — ленивые. Это даёт возможность читать и писать в файлы на лету, как по конвейеру, без использования буферов.
Например:
Программа будет выводить текст в верхнем регистре по мере его поступления.
Проблемы, связанные с использованием ленивых вычислений
На протяжении всей статьи я использовал термин «обещание», чтобы обозначить некую единицу ленивого вычисления, но дело в том, что это не просто абстрактное понятие. Скомпилированная программа на Хаскеле в действительности использует обещания, которые занимают место в памяти и на стеке. То есть, к расходам на обычные вычисления добавляется сборка мусора, выделение памяти, разворачивание обещаний. В этом и заключается главная проблема ленивых вычислений — за их неграмотное использование можно поплатиться сильным снижением производительности, переполнениями стека и большим потреблением памяти.
Но существуют способы, как сделать вычисления менее ленивыми, которые мы сейчас и рассмотрим.
Рассмотрим такой простой пример:
Здесь мы находим сумму чисел от 1 до 1e6 и выводим её в консоль. Но если вы попытаетесь запустить программу, то увидите такое сообщение:
Так как вычисление sum’ ls откладывается, мы получаем множество вложенных обещаний, занимающих место на стеке. Чтобы избавиться от этого, надо как-то заставить обещания вычисляться, а не накапливаться. И для этого у нас есть функция seq. Она принимает два аргумента, первый из которых вычисляется, а второй возвращается. Давайте попробуем применить её здесь.
Для начала перепишем функцию sum’ на использование хвостовой рекурсии:
Теперь заставить сложение вычисляться будет не сложно:
Seq заставляет сумму вычислиться, заместо того, чтобы отложить сложение на потом.
Теперь ошибки не происходит.
Попробуем чуть усложнённый пример: кроме суммы элементов подсчитаем и их число.
Немного некрасиво, но работает. Ситуация, когда нужно вычислить что-либо полностью, не так редка, так что для этого был создан специальный модуль. Давайте его опробуем:
Функция deepseq вычисляет значения полностью, до Normal Form.
Bang patterns
Для более удобного указания строгости, было создано расширение компилятора — Bang patterns. Оно позволяет указывать строгость аргументов просто восклицательным знаком. С использованием этого расширения, мы можем переписать наш код так:
Всё будет работать, как и прежде.
Bang patterns позволяют нам указывать строгость не только аргументов функций, но и полей структур данных, например:
SPair — строгая пара. Значения в её полях будут всегда вычислены, что, опять же, не позволяет обещаниям скапливаться.
Заключение
В этой статье, я постарался объяснить как совладать с ленивыми вычислениями. Надеюсь после её прочтения Вы начнёте понимать, где и как лучше применять отложенные вычисления, зачем они вообще нужны.