Short circuiting (&&) in Haskell
Asked Answered
M

4

20

A quick question that has been bugging me lately. Does Haskell perform all the equivalence test in a function that returns a boolean, even if one returns a false value?

For example

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

If the first test returns false, will it perform the second test after the &&? Or is Haskell lazy enough to not do it and move on?

Mccurdy answered 22/11, 2009 at 14:52 Comment(0)
V
24

Should be short circuited just like other languages. It's defined like this in the Prelude:

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

So if the first parameter is False the 2nd never needs to be evaluated.

Vallo answered 22/11, 2009 at 15:1 Comment(5)
Is this also the same in the case of list comprehensions?Mccurdy
Short circuit is not spoken correctly. You simply don't know whether the values are evaluated since you have no way to prove it without side effects, but it's unlikely that they will unless needed.Paschasia
I think it's the same as C++: the language says the right-hand side doesn't get evaluated. But of course if the compiler can tell there aren't any side effects, it may evaluate it anyway--and some C++ compilers do so, since conditional branches are expensive.Dispel
Note that evaluating thunks in Haskell can have side effects: errors or infinite loops. So just like C++, the compiler has to check for possible side effects first, if it wants to evaluate something it's technically not supposed to.Dispel
Yes it works the same way in list comprehensions. Haskell is a pure language. Since this function is not defined in a monad there cannot be side effects. A good test would be something like this: False && (length [1..]) < 0 So throw something that will never complete on the right hand side.Vallo
A
5

Like Martin said, languages with lazy evaluation never evaluate anything that's value is not immediately needed. In a lazy language like Haskell, you get short circuiting for free. In most languages, the || and && and similar operators must be built specially into the language in order for them to short circuit evaluation. However, in Haskell, lazy evaluation makes this unnecessary. You could define a function that short circuits yourself even:

scircuit fb sb = if fb then fb else sb

This function will behave just like the logical 'or' operator. Here is how || is defined in Haskell:

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

So, to give you the specific answer to your question, no. If the left hand side of the || is true, the right hand side is never evaluated. You can put two and two together for the other operators that 'short circuit'.

Avionics answered 22/11, 2009 at 21:36 Comment(0)
O
1

A simple test to "prove" that Haskell DO have short circuit, as Caleb said.

If you try to run summation on an infinite list, you will get stack overflow:

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

But if you run e.g. (||) (logical OR) on in infinite list, you will get a result, soon, because of short circuiting:

Prelude> foldr (||) False $ repeat True
True
Obau answered 7/1, 2021 at 13:52 Comment(1)
Interesting. This is kinda hard to accept to me since foldr uses the second argument and the function in the last element of the list. As in this case this is a infinite list, it's a bit weird to think about the application of this function. Thanks for the clarification tho.Zig
A
0

Lazy evaluation means, that nothing is evaluated till it is really needed.

Anandrous answered 22/11, 2009 at 15:6 Comment(0)

© 2022 - 2025 — McMap. All rights reserved.