Haskell Laziness and seq - PullRequest
Новая
       6

Haskell Laziness and seq

0 голосов
/ 13 ноября 2018

Я пытаюсь понять Laziness и seq в Haskell.

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

В 2. верно ли, что v 'вычисляется перед каждым рекурсивным вызовом,так что не требуется оценка v в базовом случае?Если нет, то как мне выполнить эту строгую оценку?

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

main = do
  f [1, 2, 3, 4] 0
  f' [1, 2, 3, 4] 0

g x = 42 * x -- this could be whatever

-- 1. lazy
f [] v = print v -- base case
f (x:xs) v = f xs v'
  where v' = v + g x

-- 2. strict
f' [] v = print v -- base case
f' (x:xs) v = seq v' f' xs v'
  where v' = v + g x

Я знаю, что foldl и foldl 'делают то, чтоЯ хочу в этих случаях.Меня больше интересует понимание того, как это реализовано.

1 Ответ

0 голосов
/ 13 ноября 2018

Да, вы правы.

Оперативно, в случае 1, переменная v привязана к thunk, неоцененному выражению, которое становится все больше и больше, пока print не вызовет свою оценку.Объем памяти не постоянен.

В случае 2 переменная v всегда связана с вычисленным числом.Рекурсия выполняется в постоянном пространстве.

Кстати, идиоматично писать seq v' f' xs v' как 

v' `seq` f' xs v'

или, используя $!

f' xs $! v'

Другой распространенный выбор - использовать шаблон взрыва и забыть seq

f' [] !v = print v -- base case
f' (x:xs) !v = f' xs v'
  where v' = v + g x

Взрывы ! гарантируют, что v требуется немедленно, поэтому, даже если это thunk, он оценивается перед продолжением,Это также обеспечивает постоянный объем памяти.

В качестве инструмента профилирования для строгости вы можете попробовать Debug.Trace.trace, который будет печатать отладочное сообщение всякий раз, когда требуется какой-либо блок.Это не должно использоваться для общего вывода, но для общей отладки вполне подойдет.

...