[Haskell-cafe] Why are && and || right-associative?

[Li-yao Xia]

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)