Почему ленивая оценка полезна? - PullRequest
110 голосов
/ 05 ноября 2008

Мне давно интересно, почему ленивая оценка полезна. Мне еще предстоит, чтобы кто-нибудь объяснил мне так, чтобы это имело смысл; в основном это сводится к тому, чтобы «поверить мне».

Примечание: я не имею в виду запоминание.

Ответы [ 22 ]

90 голосов
/ 05 ноября 2008

В основном потому, что это может быть более эффективным - значения не нужно вычислять, если они не будут использоваться. Например, я могу передать три значения в функцию, но в зависимости от последовательности условных выражений фактически может использоваться только подмножество. В таком языке, как C, все три значения будут вычислены в любом случае; но в Haskell вычисляются только необходимые значения.

Он также позволяет создавать такие интересные вещи, как бесконечные списки. У меня не может быть бесконечного списка на языке, подобном C, но в Haskell это не проблема. Бесконечные списки используются довольно часто в определенных областях математики, поэтому может быть полезно иметь возможность манипулировать ими.

69 голосов
/ 12 ноября 2008

Полезным примером ленивой оценки является использование quickSort:

quickSort [] = []
quickSort (x:xs) = quickSort (filter (< x) xs) ++ [x] ++ quickSort (filter (>= x) xs)

Если мы теперь хотим найти минимум списка, мы можем определить

minimum ls = head (quickSort ls)

Который сначала сортирует список, а затем занимает первый элемент списка. Однако из-за ленивых вычислений вычисляется только голова. Например, если мы возьмем минимум из списка, [2, 1, 3,] quickSort сначала отфильтрует все элементы, которые меньше двух. Затем он выполняет быструю сортировку по этому (возвращая одноэлементный список [1]), чего уже достаточно. Из-за ленивых вычислений остальное никогда не сортируется, что экономит много вычислительного времени.

Это, конечно, очень простой пример, но лень работает так же для очень больших программ.

Однако есть и обратная сторона всего этого: становится все труднее прогнозировать скорость выполнения и использование памяти вашей программой. Это не значит, что ленивые программы работают медленнее или занимают больше памяти, но это полезно знать.

64 голосов
/ 05 ноября 2008

Мне ленивая оценка полезна для многих вещей.

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

Чистые языки позволяют рассуждать об определениях функций с использованием эквациональных рассуждений.

foo x = x + 3

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

Во-вторых, многие вещи, такие как «ограничение значения» в ML, не нужны в ленивых языках, таких как Haskell. Это приводит к значительному снижению синтаксиса. В языках, подобных ML, необходимо использовать такие ключевые слова, как var или fun. В Хаскеле эти вещи сводятся к одному понятию.

В-третьих, лень позволяет вам писать очень функциональный код, который можно понять по частям. В Haskell принято писать тело функции, например:

foo x y = if condition1
          then some (complicated set of combinators) (involving bigscaryexpression)
          else if condition2
          then bigscaryexpression
          else Nothing
  where some x y = ...
        bigscaryexpression = ...
        condition1 = ...
        condition2 = ...

Это позволяет вам работать «сверху вниз», понимая тело функции. ML-подобные языки вынуждают вас использовать let, которая оценивается строго. Следовательно, вы не осмеливаетесь «поднять» предложение let до основной части функции, потому что, если это дорого (или имеет побочные эффекты), вы не хотите, чтобы оно всегда оценивалось. Haskell может явно «вытолкнуть» детали к предложению where, поскольку он знает, что содержимое этого предложения будет оцениваться только при необходимости.

На практике мы, как правило, используем охранников и разрушаемся до:

foo x y 
  | condition1 = some (complicated set of combinators) (involving bigscaryexpression)
  | condition2 = bigscaryexpression
  | otherwise  = Nothing
  where some x y = ...
        bigscaryexpression = ...
        condition1 = ...
        condition2 = ...

В-четвертых, лень иногда предлагает гораздо более элегантное выражение определенных алгоритмов. Ленивая «быстрая сортировка» в Haskell является однострочной и имеет то преимущество, что если вы смотрите только на первые несколько предметов, вы оплачиваете только расходы, пропорциональные стоимости выбора только этих предметов. Ничто не мешает вам делать это строго, но вам, вероятно, придется каждый раз перекодировать алгоритм для достижения той же асимптотической производительности.

В-пятых, лень позволяет вам определять новые управляющие структуры в языке. Вы не можете написать новую конструкцию типа «если .. тогда .. еще ..» на строгом языке. Если вы попытаетесь определить функцию, например:

if' True x y = x
if' False x y = y

на строгом языке, тогда обе ветви будут оцениваться независимо от значения условия. Это ухудшается, когда вы рассматриваете петли. Все строгие решения требуют, чтобы язык предоставил вам какую-то цитату или явную лямбда-конструкцию.

Наконец, в том же духе, некоторые из лучших механизмов борьбы с побочными эффектами в системе типов, таких как монады, действительно могут эффективно выражаться только в ленивых условиях. Это можно увидеть, сравнив сложность рабочих процессов F # с Haskell Monads. (Вы можете определить монаду на строгом языке, но, к сожалению, вы часто будете нарушать закон монады или два из-за отсутствия лени и рабочих процессов, для сравнения заберите тонну строгого багажа.)

28 голосов
/ 21 ноября 2008

Существует разница между обычной оценкой заказа и ленивой оценкой (как в Haskell).

square x = x * x

Оценка следующего выражения ...

square (square (square 2))

... с нетерпением:

> square (square (2 * 2))
> square (square 4)
> square (4 * 4)
> square 16
> 16 * 16
> 256

... с обычной оценкой заказа:

> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * (square (square 2))
> ((2 * 2) * (square 2)) * (square (square 2))
> (4 * (square 2)) * (square (square 2))
> (4 * (2 * 2)) * (square (square 2))
> (4 * 4) * (square (square 2))
> 16 * (square (square 2))
> ...
> 256

... с ленивой оценкой:

> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * ((square 2) * (square 2))
> ((2 * 2) * (2 * 2)) * ((2 * 2) * (2 * 2))
> (4 * 4) * (4 * 4)
> 16 * 16
> 256

Это потому, что ленивая оценка просматривает синтаксическое дерево и выполняет преобразования дерева ...

square (square (square 2))

           ||
           \/

           *
          / \
          \ /
    square (square 2)

           ||
           \/

           *
          / \
          \ /
           *
          / \
          \ /
        square 2

           ||
           \/

           *
          / \
          \ /
           *
          / \
          \ /
           *
          / \
          \ /
           2

... тогда как нормальная оценка порядка выполняет только текстовые расширения.

Именно поэтому мы, используя ленивую оценку, становимся более мощными (оценка завершается чаще, чем другие стратегии), а производительность эквивалентна активной оценке (по крайней мере, в О-записи).

25 голосов
/ 30 января 2010

Ленивая оценка, связанная с процессором, так же, как сборка мусора, связанная с оперативной памятью. GC позволяет вам делать вид, что у вас неограниченный объем памяти и, таким образом, запрашивать столько объектов в памяти, сколько вам нужно. Среда выполнения автоматически восстанавливает непригодные для использования объекты. LE позволяет вам делать вид, что у вас есть неограниченные вычислительные ресурсы - вы можете делать столько вычислений, сколько вам нужно. Среда выполнения просто не будет выполнять ненужные (для данного случая) вычисления.

В чем практическое преимущество этих «притворных» моделей? Это освобождает разработчика (в некоторой степени) от управления ресурсами и удаляет некоторый шаблонный код из ваших источников. Но более важно то, что вы можете эффективно использовать свое решение в более широком контексте.

Представьте, что у вас есть список чисел S и числа N. Вам нужно найти ближайший к номеру N номер M из списка S. У вас может быть два контекста: один N и некоторый список L из Ns (например, для каждого N в L вы смотрите ближайший M в S). Если вы используете ленивую оценку, вы можете отсортировать S и применить бинарный поиск, чтобы найти ближайший M к N. Для хорошей ленивой сортировки потребуется O (размер (S)) шагов для отдельных N и O (ln (размер (S)) * (размер (S) + размер (L))) шаги для равномерно распределенных L. Если у вас нет ленивых вычислений для достижения оптимальной эффективности, вы должны реализовать алгоритм для каждого контекста.

25 голосов
/ 10 декабря 2008

Если вы верите Саймону Пейтону Джонсу, ленивая оценка не важна как таковая , но только как «рубашка для волос», которая заставляла дизайнеров сохранять язык чистым. Я сочувствую этой точке зрения.

Ричард Берд, Джон Хьюз и, в меньшей степени, Ральф Хинце способны делать удивительные вещи с ленивой оценкой. Чтение их работ поможет вам оценить их. Хорошей отправной точкой являются Великолепный решатель птицы Судоку и статья Хьюза о Почему функциональное программирование имеет значение .

13 голосов
/ 26 декабря 2008

Рассмотрим программу крестики-нолики. Это имеет четыре функции:

  • Функция генерации ходов, которая берет текущую доску и генерирует список новых досок, каждое из которых применено одним ходом.
  • Затем есть функция «дерево ходов», которая применяет функцию генерации ходов для получения всех возможных позиций доски, которые могут следовать из этой.
  • Существует минимаксная функция, которая обходит дерево (или, возможно, только его часть), чтобы найти лучший следующий ход.
  • Существует функция оценки доски, которая определяет, выиграл ли один из игроков.

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

Теперь давайте попробуем реализовать шахматы вместо крестики-нолики. На «нетерпеливом» (то есть обычном) языке это не сработает, потому что дерево перемещений не помещается в памяти. Таким образом, теперь функции оценки доски и генерации ходов необходимо смешать с деревом ходов и минимаксной логикой, поскольку для решения, какие ходы генерировать, необходимо использовать минимаксную логику. Наша хорошая чистая модульная структура исчезает.

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

12 голосов
/ 02 октября 2011

Вот еще два момента, которые, я не думаю, были затронуты в ходе обсуждения.

  1. Laziness - это механизм синхронизации в параллельной среде. Это легкий и простой способ создать ссылку на некоторые вычисления и поделиться результатами среди множества потоков. Если несколько потоков пытаются получить доступ к неоцененному значению, только один из них выполнит его, а другие будут блокироваться соответствующим образом, получив значение, как только оно станет доступным.

  2. Лень имеет основополагающее значение для амортизации структур данных в чистом виде. Это подробно описано Окасаки в Чисто функциональных структурах данных , но основная идея заключается в том, что ленивая оценка - это контролируемая форма мутации, критически важная для эффективного внедрения определенных типов структур данных. В то время как мы часто говорим о лени, заставляющей нас носить чистую прическу, применяется и другой способ: это пара синергетических языковых особенностей.

9 голосов
/ 05 ноября 2008

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

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

8 голосов
/ 02 октября 2012
  1. Это может повысить эффективность. Это выглядит очевидным, но на самом деле это не самое главное. (Также обратите внимание, что лень тоже может убить эффективность - этот факт не сразу очевиден. Однако, сохраняя множество временных результатов, а не вычисляя их сразу, вы можете использовать огромное количество оперативной памяти.)

  2. Позволяет определять конструкции управления потоком в обычном коде пользовательского уровня, а не жестко кодировать его в языке. (Например, Java имеет циклы for; Haskell имеет функцию for. Java имеет обработку исключений; Haskell имеет различные типы монад исключений. C # имеет goto; Haskell имеет монаду продолжения ...)

  3. Позволяет отделить алгоритм для генерации данных от алгоритма для определения количества данных для генерации. Вы можете написать одну функцию, которая генерирует условно-бесконечный список результатов, и другую функцию, которая обрабатывает столько же этого списка, сколько решает. Более того, вы можете иметь пять функций генератора и пять функций-потребителей, и вы можете эффективно создавать любую комбинацию - вместо того, чтобы вручную кодировать 5 x 5 = 25 функций, которые объединяют оба действия однажды. (!) Мы все знаем, что разделение - это хорошо.

  4. Это более или менее вынуждает вас создавать функциональный язык pure . Всегда соблазнительно использовать короткие пути, но на ленивом языке малейшая нечистота делает ваш код дико непредсказуемым, что сильно препятствует использованию ярлыков.

...