Короткое замыкание (&&) в Haskell

Быстрый вопрос, который беспокоил меня в последнее время. Выполняет ли Haskell все проверки эквивалентности в функции, которая возвращает логическое значение, даже если оно возвращает ложное значение?

Например

f a b = ((a+b) == 2) && ((a*b) == 2)

Если первый тест вернет false, будет ли он выполнять второй тест после &&? Или Haskell достаточно ленив, чтобы не делать этого и двигаться дальше?


boolean combinators haskell
person Jonno_FTW    schedule 22.11.2009    source источник

Ответы (4)


arrow_upward
23
arrow_downward

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

(&&)                    :: Bool -> Bool -> Bool
True  && x              =  x
False && _              =  False

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

person Caleb    schedule 22.11.2009
comment
То же самое и в случае понимания списков? - person Jonno_FTW; 22.11.2009
comment
Short circuit произносится неправильно. Вы просто не знаете, оцениваются ли значения, поскольку у вас нет способа доказать это без побочных эффектов, но маловероятно, что они будут оцениваться, если в этом нет необходимости. - person Dario; 22.11.2009
comment
Я думаю, что это то же самое, что и C++: язык говорит, что правая часть не оценивается. Но, конечно, если компилятор может сказать, что никаких побочных эффектов нет, он все равно может их оценить — и некоторые компиляторы C++ так и поступают, поскольку условные переходы обходятся дорого. - person Jason Orendorff; 22.11.2009
comment
Обратите внимание, что обработка переходников в Haskell может иметь побочные эффекты: ошибки или бесконечные циклы. Так что, как и в C++, компилятор должен сначала проверить возможные побочные эффекты, если он хочет оценить что-то, что он технически не должен делать. - person Jason Orendorff; 22.11.2009
comment
Да, это работает так же в списках. Хаскель - чистый язык. Поскольку эта функция не определена в монаде, у нее не может быть побочных эффектов. Хорошим тестом было бы что-то вроде этого: False && (length [1..]) ‹ 0 Итак, добавьте что-то, что никогда не завершится в правой части. - person Caleb; 22.11.2009

arrow_upward
6
arrow_downward

Как сказал Мартин, языки с ленивой оценкой никогда не оценивают ничего, что не нужно немедленно. В ленивом языке, таком как Haskell, вы получаете короткое замыкание бесплатно. В большинстве языков || и &&, и подобные операторы должны быть специально встроены в язык, чтобы они могли сократить вычисление. Однако в Haskell ленивые вычисления делают это ненужным. Вы можете определить функцию, которая замыкает себя даже накоротко:

scircuit fb sb = if fb then fb else sb

Эта функция будет вести себя так же, как логический оператор «или». Вот как || определяется в Haskell:

True  || _ = True
False || x = x

Итак, чтобы дать вам конкретный ответ на ваш вопрос, нет. Если левая часть || верно, правая часть никогда не оценивается. Вы можете сложить два и два для других операторов, у которых «короткое замыкание».

person Rayne    schedule 22.11.2009

arrow_upward
1
arrow_downward

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

person Martin    schedule 22.11.2009

arrow_upward
1
arrow_downward

Простой тест, чтобы доказать, что Haskell ДЕЙСТВИТЕЛЬНО имеет короткое замыкание, как сказал Калеб.

Если вы попытаетесь выполнить суммирование бесконечного списка, вы получите переполнение стека:

Prelude> foldr (+) 0 $ repeat 0
*** Exception: stack overflow

Но если вы запустите, например. (||) (логическое ИЛИ) в бесконечном списке, вы скоро получите результат из-за короткого замыкания:

Prelude> foldr (||) False $ repeat True
True
person hadi_sfr    schedule 07.01.2021