Christoph Schiessl's Blog

Custom Infix Operators in Haskell

Custom infix operators are a common occurrence in Haskell. Apart from built-in operators (such as + and *), there are many libraries exposing custom operators. For instance, Data.Monoid defines the infix operator <> as an alias for mappend.

To understand how these operators work or to create your own, you have to consider two things: Precedence and associativity. Both of these properties are necessary for unambiguous parsing of expressions later on.

Precedence (aka Operator Binding)

Let’s start with precedence, because it’s easier to explain. All operators in Haskell have a precedence, which is expressed with a simple integer value. 0 is the lowest possible value, whereas 9 is the highest.

Example: The expression 2 * 4 + 4 * 5 == 28 is True, because * has a higher precedence than + (i.e. 7 vs. 6). Consequently, you could rewrite it as (2 * 4) + (4 * 56) == 28.

There’s one important exception to the rule: Normal function application (i.e. space) has a precedence of 10, which is higher than the maximum precedence for infix operators.

Example: The expression square 6 / 3 == 12 is True, because normal function application has a higher precedence than / (i.e. 10 vs. 7). Consequently, you could rewrite it as (square 6) / 3 == 12.

Associativity (aka Fixity)

Associativity is less obvious, so let’s first define it.

Left-Associativity: A binary operator is left-associative iff its applications in an expression can be grouped together from the left to the right without affecting the expression’s meaning. In mathematical notation:

abc=(ab)c a \star b \star c = (a \star b) \star c

wherea,b,cDand:(D×D)D \text{where} \quad a, b, c \in D \quad \text{and} \quad \star : (D \times D) \mapsto D

Right-Associativity: On the other hand, iff the operator’s applications in an expression can be grouped together from the right to the left it is right-associative. In mathematical notation:

abc=a(bc) a \star b \star c = a \star (b \star c)

wherea,b,cDand:(D×D)D \text{where} \quad a,b,c \in D \quad \text{and} \quad \star : (D \times D) \mapsto D

Full-Associativity: A binary operator is fully-associative iff it is both left- and right-associative.

In other words, the operator’s applications in an expression can be arbitrarily grouped together. It doesn’t matter where (or if) you place parentheses. The expression’s evaluation always results in the same value.

Non-Associativity: A binary operator is non-associative iff it is neither left- nor right-associative.


There are three ways to define infix operators in Haskell: infixl, infixr, and infix. In the following sections we are going to try each of these keywords by defining the operator @@ as an alias for the following function:

1
2
multiplyAndIncrement :: (Num a) => a -> a -> a
multiplyAndIncrement x y = x * y + 1

To demonstrate why precedence and associativity matter, we are also going to evaluate the expression 2 @@ 3 @@ 3 + 1 each time (and get a different result each time).

Left-associative Operator with infixl

The following code snippet defines the left-associative operator @@ with a precedence of 5:

1
2
infixl 5 @@
(@@) = multiplyAndIncrement

This scenario leads to the following evaluation of 2 @@ 3 @@ 3 + 1:

  1. + has a higher precedence than @@ (i.e. 6 vs. 5). Therefore, the first step is to compute 3 + 1, leaving us with 2 @@ 3 @@ 4.
  2. @@ is left-associative. Therefore, the second step is to compute 2 @@ 3, leaving us with 7 @@ 4.
  3. Finally, if we apply the @@ operator again to compute 7 @@ 4, we get 29 as our final result.

Right-associative Operator with infixr

Right-associative operator @@ with a precedence of 8:

1
2
infixr 8 @@
(@@) = multiplyAndIncrement

This scenario leads to the following evaluation of 2 @@ 3 @@ 3 + 1:

  1. @@ has a higher precedence than + (i.e. 8 vs. 5). Therefore, we have to apply @@ before we apply +. Within the sub-expression 2 @@ 3 @@ 3 we have to compute 3 @@ 3 first, because of @@’s right-associativity, leaving us with 2 @@ 10 + 1.
  2. The argument from the first step still holds: @@ has a higher precedence than +. So, we have to compute 2 @@ 10 next, leaving us with 21 + 1.
  3. Finally, if we apply the + operator to compute 21 + 1, we get 22 as our final result.

Non-associative Operator with infix

Non-associative operator @@ with a precedence of 2:

1
2
infix 2 @@
(@@) = multiplyAndIncrement

This scenario leads to the following evaluation of 2 @@ 3 @@ 3 + 1:

  1. + has a higher precedence than @@ (i.e. 6 vs. 2). Therefore, the first step is to compute 3 + 1, leaving us with 2 @@ 3 @@ 4.
  2. Now we have a problem: @@ is non-associative, so what should our next step be? 2 @@ 3 or 3 @@ 4?

As a matter of fact, our expression is simply not well defined. Unambiguous parsing is not possible. If you try to evaluate it in GHCi, it fails with an error message. Observe:

1
2
3
4
5
6
7
GHCi> 2 @@ 3 @@ 3 + 1

<interactive>:27:1:
    Precedence parsing error
        cannot mix ‘@@’ [infix 2]
        and ‘@@’ [infix 2] in the
        same infix expression

Conclusion

As you can see, both operator precedence and associativity may change the meaning of your program or even make it invalid.

comments powered by Disqus