[Haskell-cafe] Why are && and || right-associative?
lysxia at gmail.com
Fri Apr 12 06:48:39 UTC 2019
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
>> 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.
f :: Bool -> IO ()
f b =
&& True -- 9 more
(&.) :: Bool -> Bool -> Bool
(&.) = (&&)
infixl 1 &.
main :: IO ()
main = do
mapM_ f (replicate 1000000 False)
More information about the Haskell-Cafe