Как работает лень Хаскелла?
Рассмотрим эту функцию, которая удваивает все элементы в списке:
doubleMe [] = []
doubleMe (x:xs) = (2*x):(doubleMe xs)
Затем рассмотрим выражение
doubleMe (doubleMe [a,b,c])
Кажется очевидным, что во время выполнения это сначала расширяется до:
doubleMe ( (2*a):(doubleMe [b,c]) )
(Это очевидно, потому что, насколько я вижу, других возможностей не существует).
Но мой вопрос заключается в следующем: почему именно это теперь распространяется на
2*(2*a) : doubleMe( doubleMe [b,c] )
вместо
doubleMe( (2*a):( (2*b) : doubleMe [c] ) )
?
Интуитивно я знаю ответ: потому что Хаскелл ленив. Но может ли кто-нибудь дать мне более точный ответ?
Есть ли что-то особенное в списках, которое вызывает это, или идея более общая, чем просто списки?
7 ответов
doubleMe (doubleMe [a,b,c]) не расширяется до doubleMe ( (2*a):(doubleMe [b,c]) ), Расширяется до:
case doubleMe [a,b,c] of
[] -> []
(x:xs) -> (2*x):(doubleMe xs)
То есть внешний вызов функции раскрывается первым. В этом главное отличие ленивого языка от строгого: при расширении вызова функции вы сначала не оцениваете аргумент - вместо этого вы заменяете вызов функции его телом и оставляете аргумент как есть на данный момент.
Теперь doubleMe Необходимо расширить, потому что сопоставление с образцом должно знать структуру его операнда, прежде чем его можно будет оценить, поэтому мы получаем:
case (2*a):(doubleMe [b,c]) of
[] -> []
(x:xs) -> (2*x):(doubleMe xs)
Теперь сопоставление с образцом может быть заменено телом второй ветви, потому что теперь мы знаем, что вторая ветвь является той, которая соответствует. Таким образом, мы подставляем (2*a) за x а также doubleMe [b, c] за xs, давая нам:
(2*(2*a)):(doubleMe (doubleMe [b,c]))
Так вот как мы приходим к этому результату.
Ваш "очевидный" первый шаг на самом деле не так очевиден. На самом деле, то, что происходит, выглядит примерно так:
doubleMe (...)
doubleMe ( { [] | (_:_) }? )
doubleMe ( doubleMe (...)! )
и только в этот момент он действительно "входит" во внутреннюю функцию. Так продолжается
doubleMe ( doubleMe (...) )
doubleMe ( doubleMe( { [] | (_:_) }? ) )
doubleMe ( doubleMe( a:_ ! ) )
doubleMe ( (2*a) : doubleMe(_) )
doubleMe ( (2*a):_ ! )
теперь здесь внешний doubleMe функция имеет "ответ" на это [] | (_:_) вопрос, который был единственной причиной, что что-либо во внутренней функции было оценено вообще.
На самом деле, следующий шаг тоже не обязательно то, что вы, хотя: это зависит от того, как вы оцениваете внешний результат! Например, если все выражение было tail $ doubleMe ( doubleMe [a,b,c] ), то это на самом деле будет расширяться как
tail( { [] | (_:_) }? )
tail( doubleMe(...)! )
tail( doubleMe ( { [] | (_:_) }? ) )
...
tail( doubleMe ( doubleMe( a:_ ! ) ) )
tail( doubleMe ( _:_ ) )
tail( _ : doubleMe ( _ ) )
doubleMe ( ... )
то есть на самом деле это никогда не дойдет до 2*a!
Другие уже ответили на общий вопрос. Позвольте мне добавить кое-что по этому конкретному вопросу:
Есть ли что-то особенное в списках, которое вызывает это, или идея более общая, чем просто списки?
Нет, списки не являются специальными. каждый data Тип в Haskell имеет ленивую семантику. Давайте попробуем простой пример, используя тип пары для целых чисел (Int, Int),
let pair :: (Int,Int)
pair = (1, fst pair)
in snd pair
Выше, fst,snd являются проекциями пары, возвращающими первый / второй компонент пары. Также обратите внимание, что pair является рекурсивно определенной парой Да, в Haskell вы можете рекурсивно определять все, а не только функции.
При ленивой семантике вышеприведенное выражение примерно оценивается так:
snd pair
= -- definition of pair
snd (1, fst pair)
= -- application of snd
fst pair
= -- definition of pair
fst (1, fst pair)
= -- application of fst
1
Для сравнения, используя энергичную семантику, мы оценили бы ее следующим образом:
snd pair
= -- definition of pair
snd (1, fst pair)
= -- must evaluate arguments before application, expand pair again
snd (1, fst (1, fst pair))
= -- must evaluate arguments
snd (1, fst (1, fst (1, fst pair)))
= -- must evaluate arguments
...
В энергичной оценке мы настаиваем на оценке аргументов перед применением fst/snd, и мы получаем программу с бесконечной петлей. В некоторых языках это вызовет ошибку "переполнения стека".
В отложенной оценке мы скоро применяем функции, даже если аргумент не полностью оценен. Это делает snd (1, infiniteLoop) вернуть 1 немедленно.
Таким образом, ленивая оценка не является специфичной для списков. В Haskell все лениво: деревья, функции, кортежи, записи, определяемые пользователем data типы и т. д.
(Nitpick: если программист действительно запрашивает их, можно определить типы, имеющие строго / жадно оцениваемые компоненты. Это можно сделать с помощью аннотаций строгости или с помощью расширений, таких как распакованные типы. Хотя иногда они имеют свои применения, они обычно не встречаются в программах на Haskell.)
Это хорошее время для выведения эквациональных рассуждений, что означает, что мы можем заменить функцию для ее определения (по модулю переименования вещей, чтобы не было столкновений). Я собираюсь переименовать doubleMe в d для краткости, хотя:
d [] = [] -- Rule 1
d (x:xs) = (2*x) : d xs -- Rule 2
d [1, 2, 3] = d (1:2:3:[])
= (2*1) : d (2:3:[]) -- Rule 2
= 2 : d (2:3:[]) -- Reduce
= 2 : (2*2) : d (3:[]) -- Rule 2
= 2 : 4 : d (3:[]) -- Reduce
= 2 : 4 : (2*3) : d [] -- Rule 2
= 2 : 4 : 6 : d [] -- Reduce
= 2 : 4 : 6 : [] -- Rule 1
= [2, 4, 6]
Так что теперь, если мы должны были выполнить это с 2 слоями doubleMe/d:
d (d [1, 2, 3]) = d (d (1:2:3:[]))
= d ((2*1) : d (2:3:[])) -- Rule 2 (inner)
= d (2 : d (2:3:[])) -- Reduce
= (2*2) : d (d (2:3:[])) -- Rule 2 (outer)
= 4 : d (d (2:3:[])) -- Reduce
= 4 : d ((2*2) : d (3:[])) -- Rule 2 (inner)
= 4 : d (4 : d (3:[])) -- Reduce
= 4 : 8 : d (d (3:[])) -- Rule 2 (outer) / Reduce
= 4 : 8 : d (6 : d []) -- Rule 2 (inner) / Reduce
= 4 : 8 : 12 : d (d []) -- Rule 2 (outer) / Reduce
= 4 : 8 : 12 : d [] -- Rule 1 (inner)
= 4 : 8 : 12 : [] -- Rule 1 (outer)
= [4, 8, 12]
Кроме того, вы можете уменьшить в разные моменты времени, в результате чего
d (d [1, 2, 3]) = d (d (1:2:3:[]))
= d ((2*1) : d (2:3:[]))
= (2*(2*1)) : d (d (2:3:[]))
= -- Rest of the steps left as an exercise for the reader
= (2*(2*1)) : (2*(2*2)) : (2*(2*3)) : []
= (2*2) : (2*4) : (2*6) : []
= 4 : 6 : 12 : []
= [4, 6, 12]
Это два возможных расширения для этого вычисления, но оно не относится только к спискам. Вы можете применить его к типу дерева:
data Tree a = Leaf a | Node a (Tree a) (Tree a)
Где сопоставление с образцом Leaf а также Node было бы похоже на совпадение на [] а также : соответственно, если вы рассмотрите определение списка
data [] a = [] | a : [a]
Причина, по которой я говорю, что это два возможных расширения, заключается в том, что порядок, в котором оно раскрывается, зависит от конкретной среды выполнения и оптимизации для компилятора, который вы используете. Если он видит оптимизацию, которая заставит вашу программу работать намного быстрее, он может выбрать эту оптимизацию. Вот почему лень часто является благом, вам не нужно думать о порядке, в котором все происходит так часто, потому что компилятор делает это за вас. Это не было бы возможно в языке без чистоты, таком как C#/Java/Python/etc. Вы не можете переставлять вычисления, поскольку у этих вычислений могут быть побочные эффекты, которые зависят от порядка. Но при выполнении чистых вычислений у вас нет побочных эффектов, поэтому компилятору легче оптимизировать ваш код.
doubleMe [] = []
doubleMe (x:xs) = (2*x):(doubleMe xs)
doubleMe (doubleMe [a,b,c])
Я думаю, что разные люди расширяют их по-разному. Я не имел в виду, что они дают разные результаты или что-то в этом роде, просто среди людей, которые делают это правильно, на самом деле нет стандартной записи. Вот как бы я это сделал:
-- Let's manually compute the result of *forcing* the following expression.
-- ("Forcing" = demanding that the expression be evaluated only just enough
-- to pattern match on its data constructor.)
doubleMe (doubleMe [a,b,c])
-- The argument to the outer `doubleMe` is not headed by a constructor,
-- so we must force the inner application of `doubleMe`. To do that,
-- first force its argument to make it explicitly headed by a
-- constructor.
= doubleMe (doubleMe (a:[b,c]))
-- Now that the argument has been forced we can tell which of the two
-- `doubleMe` equations applies to it: the second one. So we use that
-- to rewrite it.
= doubleMe (2*a : doubleMe [b,c])
-- Since the argument to the outer `doubleMe` in the previous expression
-- is headed by the list constructor `:`, we're done with forcing it.
-- Now we use the second `doubleMe` equation to rewrite the outer
-- function application.
= 2*2*a : doubleMe (doubleMe [b, c])
-- And now we've arrived at an expression whose outermost operator
-- is a data constructor (`:`). This means that we've successfully
-- forced the expression, and can stop here. There wouldn't be any
-- further evaluation unless some consumer tried to match either of
-- the two subexpressions of this result.
Это то же самое, что ответы sepp2k и leftaroundabout, только то, что они пишут это смешно. Ответ sepp2k имеет case выражение, появляющееся, казалось бы, из ниоткуда - мульти-уравнительное определение doubleMe был неявно переписан как единый case выражение. Левый ответ о { [] | (_:_) }? вещь в нем, которая, по-видимому, является обозначением для "Я должен заставить аргумент, пока он не выглядит как [] или же (_:_)".
Ответ bhelkir похож на мой, но он также рекурсивно форсирует все подвыражения результата, чего не произойдет, если у вас не будет потребителя, который этого требует.
Так что никого не уважаю, но мне больше нравится мой.:-П
Напишите \lambda ym, чтобы обозначить абстрагированную версию doubleMe, и t для списка [a,b,c]. Тогда термин, который вы хотите уменьшить
\y.m (\y.m t)
Другими словами, есть два переопределения. Haskell предпочитает сначала запускать внешние переопределения, так как это нормальный язык упорядочивания. Однако это не совсем так. doubleMe на самом деле не \ym, и действительно имеет переопределение только тогда, когда его "аргумент" имеет правильную форму (форму списка). Поскольку это еще не переопределение, и внутри (\ym) нет переопределений, мы переместимся вправо от приложения. Поскольку Хаскелл также предпочел бы сначала оценить крайние левые переопределения. Теперь t действительно имеет форму списка, так что переопределение (\ym t) срабатывает.
\y.m (a : (\y.m t'))
И затем мы возвращаемся к вершине и делаем все это снова. За исключением этого времени, самый внешний термин имеет переопределение.
Это происходит из-за того, как списки определены и лень. Когда вы запрашиваете заголовок списка, он оценивает тот первый элемент, который вы запросили, и сохраняет остальное на потом. Все операции по обработке списков основаны на концепции "голова-покой", поэтому промежуточные результаты никогда не появляются.