Принцип работы seq

Второй вариант делает твою функцию неленивой (strict) в первом аргументе.

Чудесный ЯП, просто чудесный.

Кажется, тебе показалось, что ты дал понятный ответ ).

неленивой (strict)

разве стрикт так переводится?

Кажется, тебе показалось, что ты дал понятный ответ ).

Ну, тот можно было бы расписать, что вторая запись форсит паттерг-матчинг. Я, честно говоря, видел объяснение в wiki, но не помню где. Можно Haskell Report порыть.

разве стрикт так переводится?

Понятия не имею. Я о хацкелле и программировании вообще не слишком часто говорю по-русски. Только на ЛОРе.

Исчерпывающе. Я вообще не представляю, что означает код из ОП, но аргумент ТС про идентичность вариантов ввиду подкапотного каррирования функций в Хаскелле показался мне правдоподобным и захотелось узнать простое объяснение разницы.

Я попробую расписать подробнее. Первый вариант можно переписать как

Prelude> (\x y -> case x of True -> "AAA") undefined `seq` 2
2

второй же будет выглядеть вот так

Prelude> (\x -> case x of True -> \y -> "AAA") undefined `seq` 2
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/Err.hs:79:14 in base:GHC.Err
  undefined, called at <interactive>:11:39 in interactive:Ghci5

Надеюсь, так понятнее?

аргумент ТС про идентичность вариантов ввиду подкапотного каррирования функций в Хаскелле показался мне правдоподобным и захотелось узнать простое объяснение разницы.

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

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

Если seq не разрешать, то по сути есть. В том смысле, что (\x y -> case x of True -> «AAA») и (\x -> case x of True -> \y -> «AAA») для всех аргументов возвращают одинаковые значения.

А если разрешать, то

seq (return <=< undefined :: a -> Identity b) () = ()
seq (undefined            :: a -> Identity b) () = undefined

seq (return <=< undefined :: a -> Maybe b) () = ()
seq (undefined            :: a -> Maybe b) () = undefined

Упс. Identity и Maybe не являются монадами.

Упс. Identity и Maybe не являются монадами.

Как это связано? У тебя в первом примере первый аргумент seq вычисляется до (<=<), аргументы которого не вычисляются из-за ленивости. Во втором примере же у тебя вычисление доходит до undefined, что мы и получаем. Если ты почитаешь про seq, там написано, что первый аргумент вычисляется до WHNF, не дальше.

В том смысле, что (\x y -> case x of True -> «AAA») и (\x -> case x of True -> \y -> «AAA») для всех аргументов возвращают одинаковые значения.

Это если не считать bottom, частным случаем которого является undefined.

Алсо, отсюда: https://wiki.haskell.org/Seq

Note that seq is the only way to force evaluation of a value with a function type (except by applying it, which is liable to cause other problems). As such, it is the only reason why Haskell programs are able to distinguish between the following two values:

undefined :: a -> b

const undefined :: a -> b

This violates the principle from lambda calculus of extensionality of functions, or eta-conversion, because f and \x -> f x are distinct functions, even though they return the same output for every input. For this reason, seq, and this distinction, is sometimes ignored e.g. when assessing the correctness of optimisation techniques or type class instances.

Как это связано?

Для монады return <=< x ≡ x. А пример наглядно демонстрирует, что return <=< undefined не тождественен undefined.

Это если не считать bottom, частным случаем которого является undefined.

Prelude> let f1 = \x y -> case x of True -> "AAA"
Prelude> let f2 = \x -> case x of True -> \y ->  "AAA"
Prelude> f1 True undefined
"AAA"
Prelude> f2 True undefined
"AAA"
Prelude> f1 undefined True
"*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/Err.hs:79:14 in base:GHC.Err
  undefined, called at <interactive>:5:4 in interactive:Ghci5
Prelude> f2 undefined True
"*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/Err.hs:79:14 in base:GHC.Err
  undefined, called at <interactive>:6:4 in interactive:Ghci5

Даже для undefined f1 и f2 неразличимы. Или приведи пример аргументов, для которых f1 и f2 дадут разный результат.

Алсо, отсюда

Так и я про то же. «For this reason, seq, and this distinction, is sometimes ignored e.g. when assessing the correctness of optimisation techniques or type class instances». То есть монада должна быть монадой только в предположении, что seq не существует. Также как функция должна быть чистой только в предположении, что не существует unsafePerformIO.

Дело в том, что в первом случае у тебя частично применённая функция, поэтому нельзя начать pattern - matching до того, как получить все аргументы.

Во второму случае у тебя функция от одного аргумента, возвращающая другую, поэтому сразу происходит pattern matching и ошибка.

Лол. А для чего всё это надо? Для чего такой язык, в котором вопросов больше, чем ответов?

Prelude> (\x y -> case x of True -> "AAA") undefined `seq` 2
2

Prelude> (\x -> case x of True -> \y -> "AAA") undefined `seq` 2
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/Err.hs:79:14 in base:GHC.Err
  undefined, called at <interactive>:11:39 in interactive:Ghci5

Разница в том, что во втором случае по сути нет каррирования

Если seq не разрешать, то по сути есть. В том смысле, что (\x y -> case x of True -> «AAA») и (\x -> case x of True -> \y -> «AAA») для всех аргументов возвращают одинаковые значения

И всё же во втором случае каррирования нет просто по определению. При этом функции действительно равны экстенсионально. А что такое «каррирование по сути», и чем оно отличается от обычного каррирования?

То есть монада должна быть монадой только в предположении, что seq не существует.

Только bottom, а не seq. Ты точно так же можешь сунуть undefined в любое другое месте и компилятор это прохавает.

Также как функция должна быть чистой только в предположении, что не существует unsafePerformIO.

Ну да. Так и есть.

То есть монада должна быть монадой только в предположении, что seq не существует.

Только bottom, а не seq

bottom вместе seq. Убери что-нибудь одно (любое из двух), и все «чудеса» исчезнут.

Для монады return <=< x ≡ x. А пример наглядно демонстрирует, что return <=< undefined не тождественен undefined.

Кстати, как именно ты сравниваешь что-то с undefined? Потому что это возможно только по побочному эффекту типа «всё навернулось к чёртовой матери». Одно из возможных определений bottom будет выглядеть так:

Prelude> import Prelude hiding (undefined)
Prelude> let undefined = undefined
Prelude> :t undefined
undefined :: t

Identity и Maybe не являются монадами.

Тред не читал, но осуждаю.

Так что же получается, что seq все же доводит первый аргумент до нормальной формы? Но если в процессе редукций вычисления доходят до WHNF, то они они останавливаются, и тогда возвращается второй аргумент — я правильно понимаю это?

В этом случае ты даже по сайдэффекту сравнить не сможешь.

seq (return <=< undefined :: a -> Maybe b) () = ()
seq (undefined            :: a -> Maybe b) () -- зависает

То есть поведение программы всё равно не совпадает для тождественного монадного преобразования.

bottom вместе seq. Убери что-нибудь одно (любое из двух), и все «чудеса» исчезнут.

seq вообще-то определяется через bottom.

⊥ `seq` b = ⊥
a `seq` b = b

Если bottom запрещён, то seq становится по сути просто flip const.

seq всегда доводит элемент до нормальной формы, в этом случае тоже. В случае функции с двумя аргументами у нас получается частично примененное лябмда фунция, в как известно лябмда функция это ВХНФ форма. И.е. (xy.if x == True then 42 else undefined) при применении аргумента становится y.if False == True then .. - это WHNF. Во втором случае у нас x.if x == True then y.... else undefined при применении False - попадаем во вторую ветку с исключением. Мне лень с телефона писать case, так что написал if.

Если bottom запрещён, то seq становится по сути просто flip const.

Становится в смысле равенства значений, только вычисляться они будут по-разному, даже если нет bottom.

только вычисляться они будут по-разному

С учётом права компилятора на оптимизацию, не факт. С точки зрения алгоритма ведь различить невозможно.

С учётом права компилятора на оптимизацию, не факт. С точки зрения алгоритма ведь различить невозможно.

Это ты уже про strictness analysis говоришь. Он и сейчас работает в ghc, хотя казалось бы, bottom же есть в языке.

Замени undefined на какое-нибудь мегадлинное вычисление. Та же фигня. Опять же, здесь дело в ленивости и только в ней.

Это ты уже про strictness analysis говоришь. Он и сейчас работает в ghc, хотя казалось бы, bottom же есть в языке.

Э-э-э... strictness analysis и используется, чтобы определить где bottom в аргументе функции приведёт к расходимости. Если bottom в языке быть не может (все функции тотальны и завершимы, вроде в Agda так), то seq станет равен flip const + намёк оптимизатору вычислить первый аргумент.

Но если значение первого аргумента где-то используется, то оптимизатор и так может его вычислить заранее, а если нигде не используется, то оптимизатор может выкинуть весь код, относящийся к его вычислению. Поэтому seq в таком языке не более полезен, чем ключевое слово register в C/C++.

Замени undefined на какое-нибудь мегадлинное вычисление. Та же фигня.

Какая фигня? Для любого нерасходящегося выражения результат будет совпадать. А если компилятор при анализе строгости не затупит (сможет доказать, что мегадлинное вычисление конечно), то даже по времени отличаться не будут.

Опять же, здесь дело в ленивости и только в ней.

Не в ленивости, а в том, что seq делает в ленивости дырку. Также как unsafePerformIO делает дырку в чистоте и проверке типов.

Если bottom в языке быть не может (все функции тотальны и завершимы, вроде в Agda так), то seq станет равен flip const + намёк оптимизатору вычислить первый аргумент.

Да, так. Только не намёк, а требование.

Но если значение первого аргумента где-то используется, то оптимизатор и так может его вычислить заранее, а если нигде не используется, то оптимизатор может выкинуть весь код, относящийся к его вычислению. Поэтому seq в таком языке не более полезен, чем ключевое слово register в C/C++.

А вот тут стоп. Я покажу, что seq очень полезен, даже если мы убрали bottom. И автоматической оптимизацией тут не обойтись. Рассмотрим такой код

f b = if b then easy else hard where
    easy = length [1..10^2]
    hard = length [1..10^9]


g b = hard `seq` if b then easy else hard where
    easy = length [1..10^2]
    hard = length [1..10^9]

Представим, что в языке нету bottom. Как по-твоему должна происходить компиляция и оптимизация функций f и g? Эквивалентны ли эти функции для оптимизитора, всё же или нет? Должен ли оптимизатор предвычислять hard при компиляции f или нет? И тот же вопрос для функции g.

Только не намёк, а требование.

Если результат вычислений не используется, оптимизатор может выкинуть вычисление этого результата.

Должен ли оптимизатор предвычислять hard при компиляции f или нет?

Не должен, но имеет право. Может вернуть для результата f False как число, так и замыкание. Если оптимизатор докажет, что результат используется всегда, тогда обязан вернуть число.

И тот же вопрос для функции g.

Если g b всюду вызывается с True, может вообще его свернуть до g _ = easy и заинлайнить. Имеет право вычислить при первом вызове с False и запомнить. Имеет право предвычислить при компиляции. Предвычислит при компиляции с большей вероятностью, чем для f. Обязан вернуть число, а не замыкание для g False, если оптимизатор не может доказать, что результат нигде не используется (тогда выкидывается весь вызов g False).

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

Если результат вычислений не используется, оптимизатор может выкинуть вычисление этого результата.

не может seq это создание зависимости данных, говорящее, что в выражении a `seq` b, говорящее, что если `b` вычисленно до WHNF, то и `a` будет вычислено до WHNF. Вычисление, а никак не может быть выкинуто, даже если оно не производит эффектов и не может привести к bottom. Дело в том, что оно может при вычислении вычислять значения, использующиеся в других местах программы и если этого не будет сделано, то ресурсоемкость вычисления может возрастать (из-за ленивости).

Прикольный пример. С undefined, вообще, надо быть очень осторожным. Его иногда вместо нулевого указателя используют, чтобы освободить ссылку от старого значения. Или при прототипировании кода. Больше примеров не видел.

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

Или наоборот...

hard = [1..10^9]

f x = sum hard

g b = hard `seq` if b then 1 else length hard

При вызове g он обязан сохранить в hard развёрнутый список в памяти? При том, что sum и length вполне способен оптимизировать в цикл.

Больше примеров не видел

error в Haskell является undefined. Используется достаточно часто.

Если результат вычислений не используется, оптимизатор может выкинуть вычисление этого результата.

Похоже, что да, хаскельный seq действительно не обязан форсировать первый аргумент до WHNF при вычислении второго, при условии отсутствия bottom. Любопытно. qnikst

https://wiki.haskell.org/Seq

⊥ `seq` b = ⊥
a `seq` b = b

Strictly speaking, the two equations of seq are all it must satisfy, and if the compiler can statically prove that the first argument is not ⊥, or that its second argument is, it doesn't have to evaluate anything to meet its obligations. In practice, this almost never happens, and would probably be considered highly counterintuitive behaviour on the part of GHC (or whatever else you use to run your code). However, it is the case that evaluating b and then a, then returning b is a perfectly legitimate thing to do; it was to prevent this ambiguity that pseq was invented, but that's another story.

А по поводу моего примера с функциями f и g — преполагается, что их надо компилировать «здесь и сейчас», то есть они находятся в отдельном модуле, и компилятор не знает, как они будут использоваться в дальнейшем. Вопрос в том, должен ли оптимизатор выкинуть seq внутри g или нет.

при вызове g он должен сделать так что при вычислении 1 или length hard, g будет в WHNF. Для списка WHNF (_:_) или []. Но в данном случае весь список будет в памяти. После этого список может быть собран GC.

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

Я предпочитаю читать документацию и исходный код, а не wiki.

seq :: a -> b -> b

The value of seq a b is bottom if a is bottom, and otherwise equal to b. seq is usually introduced to improve performance by avoiding unneeded laziness.

A note on evaluation order: the expression seq a b does not guarantee that a will be evaluated before b. The only guarantee given by seq is that the both a and b will be evaluated before seq returns a value. In particular, this means that b may be evaluated before a. If you need to guarantee a specific order of evaluation, you must use the function pseq from the «parallel» package.

The only guarantee given by seq is that the both a and b will be evaluated before seq returns a value.

так что нет, не может.

Я не про error, я про непосредственное использование значения undefined

Хотя, да, error будет вести себя похоже

они одинаково себя ведут, т.к. это одно и тоже.

-- | A special case of 'error'.
-- It is expected that compilers will recognize this and insert error
-- messages which are more appropriate to the context in which 'undefined'
-- appears.
undefined :: forall (r :: RuntimeRep). forall (a :: TYPE r).
             HasCallStack => a
undefined =  error "Prelude.undefined"

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

В С++ делает. И вычисления выкидывает и во время компиляции чистые функции вычисляет и даже цикл по арифметической последовательности сворачивает.

А в Haskell вместо sum приходится писать sum' = foldl' (+) 0, чтобы не тормозило. В результате после декларативного описания алгоритма начинаешь перебирать весь код и расставлять вручную оптимизации, чтобы он не сильно тормозил. Причём, чтобы сделать мемоизацию (например, для тригонометрии), приходится делать функцию нечистой и менять ей тип.

В С++ делает. И вычисления выкидывает и во время компиляции чистые функции вычисляет и даже цикл по арифметической последовательности сворачивает.

И Haskell оптимизатор делает много, но как и в плюсах - недостаточно много, т.к. автоматические случае покрывают только то, что очень малые возможности. Более того в С++ невозможен fusion поскольку выделение памяти и создание объектов в плюсах это эффект и его нельзя убирать. Так, что лучше поосторожнее С++ как альтернативу приводить.

А в Haskell вместо sum приходится писать sum' = foldl' (+) 0, чтобы не тормозило.

Естественно, и это правильно. Почему сам ответишь? Могу подсказку дать.

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

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

Причём, чтобы сделать мемоизацию (например, для тригонометрии), приходится делать функцию нечистой и менять ей тип.

Почему глобальную мемоизацию делать автоматически нельзя практически нигде ясно же. Дарю информацию про пакет memotrie, чтобы в следующий раз не страдать.

Естественно, и это правильно. Почему сам ответишь? Могу подсказку дать.

Почему foldl' быстрее чем sum? Это очевидно.

Или почему в стандартной библиотеке sum не определён через foldl' (или аналогичный строгий хвостовызовной алгоритм)? Дай подсказку, пожалуйста. Вроде бесконечные последовательности в sum всё равно бессмысленно запихивать.

Почему глобальную мемоизацию делать автоматически нельзя практически нигде ясно же.

Почему её нельзя делать на основании данных оптимизатора в чистом языке, совсем неясно. В С++ ведь оптимизатор упрощает арифметику и вроде даже на таблицу местами вычисления заменяет (та же мемоизация только этапа компиляции), а в Haskell даже f x = g x + g x не превращается в f x = y + y where y = g x.

Дарю информацию про пакет memotrie, чтобы в следующий раз не страдать.

Что-то я туплю. А как для Floating сделать экземпляр класса HasTrie? И/или где документация? Hackage посылает в wiki, wiki на github, а github в hackage...

Пытался читать исходник, но после

{-# LANGUAGE GADTs, TypeFamilies, TypeOperators, ScopedTypeVariables, CPP #-}
{-# LANGUAGE StandaloneDeriving, FlexibleInstances #-} 
{-# LANGUAGE DefaultSignatures, FlexibleContexts, LambdaCase #-}

Или почему в стандартной библиотеке sum не определён через foldl' (или аналогичный строгий хвостовызовной алгоритм)? Дай подсказку, пожалуйста. Вроде бесконечные последовательности в sum всё равно бессмысленно запихивать.

не бесмыссленно, у числовых последовательностей и стримов есть вполне адекватные реализации Num.

В С++ ведь оптимизатор упрощает арифметику и вроде даже на таблицу местами вычисления заменяет (та же мемоизация только этапа компиляции), а в Haskell даже f x = g x + g x не превращается в f x = y + y where y = g x.

У GHC, особенно с llvm бекендом оптимизаций тоже не мало. Почему не нету последней оптимизации, я не помню сходу, но причины есть. При это я не уверен, что при простой арифметики её не будет.

Так, не тот пакет, data-memocombinators или что-то такое. У Конала он прикольный и красивый, но не очень практичный.

не бесмыссленно, у числовых последовательностей и стримов есть вполне адекватные реализации Num.

Мы опять про разное. Я не про то, что sum :: [a] -> a; a будет какой-то бесконечной структурой. Я про то, что foldr лучше чем foldl' только когда в [a] бесконечное число элементов. Но sum в любом случае пробегает всю последовательность.

Можешь привести пример, где sum работает, а foldl' (+) 0 — нет? Или зачем стандартный sum неоптимизирован?

data-memocombinators или что-то такое

http://hackage.haskell.org/package/data-memocombinators ?

Выглядит ещё хуже. Предыдущий хоть для АТД работал. А этот только для типов, явно указанных в пакете. Вопрос для Floating остаётся открытым.

Я не про то, что sum :: [a] -> a; a будет какой-то бесконечной структурой.

а я, про это.

Я про то, что foldr лучше чем foldl' только когда в [a] бесконечное число элементов.

Это абсолютно невереное утверждение, foldr лучше, чем foldl' для функций ленивых по второму аргументу, всегда, исключений нет.

Более того foldl определяется в терминах foldr:

foldl :: forall a b. (b -> a -> b) -> b -> [a] -> b
{-# INLINE foldl #-}
foldl k z0 xs =
  foldr (\(v::a) (fn::b->b) -> oneShot (\(z::b) -> fn (k z v))) (id :: b -> b) xs z0

-- | A strict version of 'foldl'.
foldl'           :: forall a b . (b -> a -> b) -> b -> [a] -> b
{-# INLINE foldl' #-}
foldl' k z0 xs =
  foldr (\(v::a) (fn::b->b) -> oneShot (\(z::b) -> z `seq` fn (k z v))) (id :: b -> b) xs z0

так что утверждение, что foldl' лучше, чем foldr, слегка бесмысленно в данном конексте.

Но sum в любом случае пробегает всю последовательность.

Это зависит от реализации (+) для типа, сходу придумать разумный тип где где сложение будет ленивым по второму аргументу мне не придумать.

Но самое интересное, что sum реализована через foldl, что несколько разбивает аргументацию выше :)

-- | The 'sum' function computes the sum of a finite list of numbers.
sum                     :: (Num a) => [a] -> a
{-# INLINE sum #-}
sum                     =  foldl (+) 0

Поэтому, про sum это не вопрос foldr vs foldl, а foldl' vs foldl и единственная претензия к sum может быть, что он не форсит аргумент, тем самым накапливая чанки, что может выглядит неверным (а может и есть).

Это зависит от реализации (+) для типа, сходу придумать разумный тип где где сложение будет ленивым по второму аргументу мне не придумать.

Отсюда и вопрос про реализацию sum.

не вопрос foldr vs foldl, а foldl' vs foldl

Зачем нужен foldl я вообще не могу представить. Выбор всегда между foldr (если последовательность может быть бесконечной) и foldl' (для любой конечной структуры).

единственная претензия к sum может быть, что он не форсит аргумент, тем самым накапливая чанки, что может выглядит неверным (а может и есть).

Так в этом и вопрос.

Выбор всегда между foldr (если последовательность может быть бесконечной) и foldl' (для любой конечной структуры).

fix: Выбор всегда между foldr (если функция-аргумент может не использовать свой второй аргумент) и foldl' (для всех остальных случаев).

foldr лучше, чем foldl' для функций ленивых по второму аргументу, всегда, исключений нет

(\x y = y) ленива по второму аргументу? Или если хоть как-то аргумент использует, то уже не ленива?

Выбор всегда между foldr (если функция-аргумент может не использовать свой второй аргумент) и foldl' (для всех остальных случаев).

Зачем нужен foldl я вообще не могу представить.

Если функция может не использовать свой первый аргумент, очевидно

Зачем нужен foldl я вообще не могу представить.

Практически нету юзкейсов, даже те, что есть можно переписать по другому. Можно ради прикола написать что-то вроде

https://github.com/haskell/hackage-server/blob/1dcb855ca962ff89b550153f940c66...

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

fix: Выбор всегда между foldr (если функция-аргумент может не использовать свой второй аргумент) и foldl' (для всех остальных случаев).

Повторюсь foldr всегда когда функция аргумент ленивая по второму аргументу. Например, <> или ++ всегда использует второй аргумент, но является по нему ленивой (для многих типов), для таких функций стоит использовать foldr. Ленивая значит, что для того, чтобы вычислить результат функции нам не нужно вычислять аргумент хотя бы до WHNF. (\x y -> y) ленивая по второму аргументу.