Понимание ленивой оценки

Question

Я пытаюсь понять, что происходит под капотом с точки зрения ленивых оценок в Haskell.

Если у меня есть вызов функции вроде:

negate $ 5 * sqrt 16

Насколько я понимаю, Haskell сначала обработает sqrt 16, создавая thunk, позволяющий вычислять значение при необходимости.

Но оценивается ли sqrt 16, когда оно передается в умножение или только когда оно каким-то образом выводится на консоль?

Другими словами, в каком порядке будет оцениваться каждая часть выражения при вводе в GHCi (например)?

Answer 1

По умолчанию каждый вызов функции и конструктора становится thunk. Итак, в этом случае оценка происходит так:

evaluate "negate $ 5 * sqrt 16" -> <thunk> $ <thunk>
 evaluate "negate"               -> <func>
 evaluate "5 * sqrt 16"          -> <thunk> * <thunk>
  evaluate "5"                    -> 5.0
  evaluate "sqrt 16"              -> 4.0

<thunk> означает что-то, что является thunk, а <func> означает, что это значение функции, которое не может быть представлено в виде строки.

Отступ означает, что «родитель» будет оценивать «потомков» до того, как сам оценит себя.

Итак, если вы напишите print (negate $ 5 * sqrt 16), среда выполнения выполнит следующие шаги:

eval thunk:
  <thunk 1> $ <thunk 2>
eval thunk 1:
  <func> $ <thunk 2>
eval thunk 2:
  <func> $ <thunk 3> * <thunk 4>
(cheating a little here, because (*) is strict, so these three are actually
 one step:)
eval thunk 3:
  <func> $ 5 * <thunk 4>
eval thunk 4 by applying sqrt:
  <func> $ 5 * 4
apply (*):
  <func> $ 20
apply ($):
  -20

Answer 2

Вы можете думать об этом как о входе вовнутрь, т.е. сначала вызывается negate. Затем он заставит оценку своего аргумента, что может вызвать оценку других выражений и так далее. Вы можете поиграть с Debug.Trace.trace, который печатает свой первый аргумент и возвращает второй при оценке, чтобы точно определить, в каком порядке все происходит в GHCi:

> trace "A" (negate (trace "B" (5 * (trace "C" (sqrt 16)))))
A
B
C
-20.0

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

Answer 3

Прежде всего, создается группа для всего выражения. * является строгим, поэтому в нем может быть создан или не создан thunk для sqrt 16, в зависимости от оптимизации (может использоваться прямой вызов sqrt). Затем, когда оно принудительно (его значение необходимо), negate принудительно заставит свой аргумент , который является выражением *, и, будучи строгим, * вызовет оба аргумента и выдаст значение, 20.

Кстати, я думаю, когда вы говорите о Haskell, вам следует говорить о нестрогой семантике. «Thunk» и «lazy» относится к особенностям реализации.

Answer 4

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

f = negate $ 5 * sqrt 16

Только когда вы используете f, вы оцениваете. negate потребуется 5 * sqrt 16, что в свою очередь потребует sqrt 16. Оценка продолжается до тех пор, пока не достигнет базового случая, который будет оцениваться, а затем будет использоваться для предыдущего / более высокого выражения (теперь в обратном направлении), пока не будет оценено все выражение.

Answer 5

Способ мышления об этом, который я читал где-то, что действительно помогло мне в этом вопросе, состоит в том, чтобы посмотреть на это так:

• Каждое выражение производит thunk .
• Thunks будет принудительным , когда их значение «необходимо».
• Понятие «потребность» - это то, что вы можете назвать «условное принуждение»: «Предполагая, что переходник T принуждается, какие еще громовые толчки будут вызваны? "Функция является строгой в своем аргументе, если форсирование thunk, который применяет эту функцию, вызывает принудительный вызов ее аргумента.

Таким образом, значения выводятся на консоль путем вызова соответствующегоshow метод на них;т. е. печать на консоль вызывает выражение вида show x (для некоторых x).Вынужденные show x силы x.Предположим, что x равно negate $ 5 * sqrt 16;поскольку negate является строгим в своем аргументе, форсирование thunk также заставляет thunk для 5 * sqrt 16.Аналогично, * и sqrt оба являются строгими в своих аргументах, поэтому также необходимо принудительно указывать на 5, sqrt 16 и 16.

Другая вещь, которую нужно понять, это то, как данныеконструкторы и сопоставление с образцом влияют на тункинг.По сути, если нет специальных аннотаций строгости, конструкторы похожи на нестрогие функции, в этом форсирование thunk не вызывает аргументы конструктора.Если не используется специальный синтаксис сопоставления с ленивым образцом, сопоставление с конструктором вызывает аргумент thunk.Итак имеем:

identity x = x  -- irrefutable pattern; `x` is not forced

uncons (x:xs) = (x, xs)  -- match against (:) constructor; argument 
                         -- must be forced, but x and xs aren't forced

foo (x:x':xs) = (x, x', xs) -- two matches against (:) constructor;
                            -- the argument thunk is forced, as is its
                            -- tail thunk.