Haskell Parsing: x ++ y : z

Question

In Haskell, why is x ++ y : z parsed as x ++ (y : z) and not as (x ++ y) : z?

For instance, [1] ++ 2 : [3] evaluates to [1,2,3].

Both (++) and (:) are right-associative with precedence 5.

Answer 1

The fact that they are right associative means that these are parsed "right-to-left" so to speak. It thus means that x ⊕ y ⊕ z is parsed as x⊕ (y ⊕ z). So that means that x ++ y : z is indeed parsed as x ++ (y : z).

There are good reasons to make both (:) and (++) right associative. For the "cons" (:) operator, it means that we can write 1 : 4 : 2 : [], since it is parsed as 1 : (4 : (2: [])), which is correct in terms of the types. If would parse it like ((1:4):2:[]), then 1:4 would for example be wrong, since it expects an item as the first operand, and list of these items as the second operand. We can of course still let the Haskell parser parse it as a list, but that would result in a large amount of extra parenthesis.

For (++) it is better to parse it right-to-left as well due to performance reasons. x ++ y takes linear time in the size of x. So that means that if we parse x ++ (y ++ z), it will take |x| + |y| steps. If we would parse this as (x ++ y) ++ z, it would take 2×|x|+|y|, since the first time we apply (x ++ y) it runs in the size of x, but then (x ++ y) ++ z runs in the size of x ++ y. This thus would mean that if we concatenate n lists each with a size of m, it will not run in O(n×m), but in O(n²×m).