On 4/12/19 6:42 AM, Joachim Durchholz wrote:
Am 12.04.19 um 04:26 schrieb Ivan Perez:
Could it be so that you can shortcut in the expected order (left to right)?
Left associative: a && b && c = (a && b) && c which means going into a && b, which means going into a, and if it is False, then going up in the expression tree.
For compile-time evaluation of known-to-be-constant values, this is what would indeed happen, but it wouldn't matter because such evaluation is done O(1) times. Generated code will simply evaluate the conditions one after the other and abort as soon as it sees False.
If you have a conjunction of n booleans, the complexity of evaluating this expression is linear with respect to the position of the first False (in the case of &&). In the left-associative case, it is linear in the number of &&s. This isn't the case.
The program below is evidence that it *is* the case: the way the expression is associated has an effect on run time. Adding more (&&) in the condition of the following function doesn't change the run time, but substituting the infixl variant (&.) does result in a measurable growth linear in the number of (&.). Of course, this is true only without optimizations, but the distinction is there, and many people do not have intuition about what is and isn't optimized by GHC, so this is certainly a worthwhile point of discussion. Li-yao import Control.Monad f :: Bool -> IO () f b = if b && True -- 9 more && True && True && True && True && True && True && True && True then error "oops" else return () (&.) :: Bool -> Bool -> Bool (&.) = (&&) infixl 1 &. main :: IO () main = do mapM_ f (replicate 1000000 False)