Вопрос по haskell, strict – функция seq и строгость

37

Я много размышлял об этом, но не смог ничего найти по этому поводу.

При использованииseq функция, как это тогдаreally Работа? Везде просто объясняется, чтоseq a b оцениваетa, отбрасывает результат и возвращаетb.

Но что этоreally имею в виду? Будет ли следующий результат в строгой оценке:

foo s t = seq q (bar q t) where
      q = s*t

Я имею в виду, чтоq строго оценены перед использованием вbar? И будет ли следующее эквивалентно:

foo s t = seq (s*t) (bar (s*t) t)

Я немного затрудняюсь разобраться в функциональности этой функции.

Это может быть полезно:stackoverflow.com/questions/6872898/… «Его семантика заключается в том, что seq x y означает, что всякий раз, когда y оценивается как нормальная форма слабой головы, x также оценивается как нормальная форма слабой головы». shang

Ваш Ответ

2   ответа
32

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

foo s t = seq q (bar q t) where
      q = s*t

q оценивается раньшеbar q t оценивается. Еслиbar q t никогда не оценивается,q тоже не будет. Так что если у вас есть

main = do
    let val = foo 10 20
    return ()

какval никогда не используется, он не будет оцениваться. Такq также не будет оцениваться. Если у вас есть

main = print (foo 10 20)

результатfoo 10 20 оценивается (print), так в пределахfoo q оценивается до результатаbar.

Вот почему это не работает:

myseq x = seq x x

Семантически это означает, что первыйx будет оцениваться до второгоx оценивается. Но если второеx никогда не оценивается, первый не должен быть либо. Такseq x x в точности эквивалентноx.

Ваш второй пример может или не может быть то же самое. Здесь выражениеs*t будет оцениваться раньшеbarвыходной сигнал, но он может не совпадатьs*t в качестве первого параметраbar, Если компилятор выполняет общее удаление подвыражений, он может объединить два идентичных выражения. GHC может быть довольно консервативным в отношении того, где он проводит CSE, поэтому вы не можете полагаться на это. Если я определюbar q t = q*t он выполняет CSE и оцениваетs*t перед использованием этого значения в баре. Это не может сделать это для более сложных выражений.

Вы также можете узнать, что подразумевается подstrict evaluation. seq вычисляет первый аргумент для нормальной формы слабой головы (WHNF), что для типов данных означает распаковку самого внешнего конструктора. Учти это:

baz xs y = seq xs (map (*y) xs)

xs должен быть список, из-заmap, когдаseq оценивает его, он по существу преобразует код в

case xs of
  [] -> map (*y) xs
  (_:_) -> map (*y) xs

Это означает, что он определит, является ли список пустым или нет, а затем вернет второй аргумент. Обратите внимание, чтоnone of the list values are evaluated, Так что вы можете сделать это:

Prelude> seq [undefined] 4
4

но не это

Prelude> seq undefined 5
*** Exception: Prelude.undefined

Какой бы тип данных вы не использовалиseqПервый аргумент, оценка WHNF, зайдет достаточно далеко, чтобы выяснить конструктор, и не будет дальше. Если тип данных не имеет компонентов, которые помечены как строгие с шаблоном взрыва. Тогда все строгие поля также будут оцениваться в WHNF.

Редактировать: (спасибо Даниэлю Вагнеру за предложение в комментариях)

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

-- ok, lambda is outermost
Prelude> seq (\x -> undefined) 'a'
'a'

-- not ok.  Because of the inner seq, `undefined` must be evaluated before
-- the lambda is showing
Prelude> seq (seq undefined (\x -> x)) 'b'
*** Exception: Prelude.undefined

Если вы думаете о лямбда-привязке как (встроенном) конструкторе данных,seq на функции прекрасно согласуется с использованием его на данных.

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

полемика В разделе seq страницы HaskellWiki есть немного о некоторых последствияхseq по отношению к функциям.

Я никогда не проверял, насколько это часто встречается. AIUI обычным способом, которым это происходит, является то, что компилятор генерирует разные ветви в зависимости от того, расходится RHS или нет, или может статически определить, что он расходится, и в этом случае LHS может вообще не оцениваться. Здесь часто встречаются исключения, потому что они считаются расхождением.
Еслиseq не имеет фактического упорядочения, а просто требует, чтобы, когда правая сторона была WHNF или более, то левая сторона также была WHNF, тогда является ли распространенным явлением то, что правая сторона фактически оценивается первой? Страница здесьwiki.haskell.org/Seq говорит "На практике это почти никогда не происходит ...".
Ваш ответ предполагает, чтоseq a b оцениваетa сначала, но то, что следует этой статье, не обязательно верно. следовательноpseq существует.wiki.haskell.org/Seq "Однако, это тот случай, когда вычисление b и затем a, а затем возвращение b - совершенно законная вещь; именно для предотвращения этой двусмысленности был изобретен pseq, но это уже другая история. & Quot;
Просто чтобы прояснить: нет никаких споров оwhen seq должен быть неактивным по функциям. Он не работает точно, когда функция «имеет лямбду, показывающую», и не запрещается, когда некоторые вычисления должны быть выполнены до того, как лямбда окажется самой верхней (и, следовательно, готовой к применению). Спор о том, должны ли мы думать об использованииseq при разработке оптимизаций - сseq занимает неудобное место в семантике Haskell.
@NiklasPeter, исправь этоseq a b не гарантирует порядок между ними, скорее это гарантирует, что еслиa расходится тогдаseq a b также расходится. Я сформулировал ответ таким образом, так как думаю, что его легче понять, но, возможно, есть лучший способ сделать это, который является четким и точным.
4

Вы можете думать оseq как:

seq a b = case a of
            _ -> b

Это оценитa к нормальной форме головы (WHNF), а затем продолжить оценкуb.

Edit after augustss comment: этотcase ... of этострогий, GHC Core один, который всегда заставляет свои аргументы.

Кроме того что Haskell не оцениваетa.

Похожие вопросы