Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to make a right-associative infix operator?

I have an associative operation >>. The problem is that its cost linearly depends on the size of its left operand. So an expression formed by a sequence of n applications of >> like

a >> a >> a >> a >> a >> ... >> a 

it has quadratic cost in terms of n, because by default infix operators are left-associative. How to make it right-associative so that the cost of such an expression is kept linear in terms of n?

like image 634
Petr Avatar asked Mar 13 '13 12:03

Petr


People also ask

How do you make an operator right associative?

The right-associativity of the = operator allows expressions such as a = b = c to be interpreted as a = (b = c) . In C++, the assignment a = b is an expression that evaluates to the same value as the expression a , with the side effect of storing the R-value of b into the L-value of a .

Is * right associative?

Operators Associativity is used when two operators of same precedence appear in an expression. Associativity can be either Left to Right or Right to Left. For example: '*' and '/' have same precedence and their associativity is Left to Right, so the expression “100 / 10 * 10” is treated as “(100 / 10) * 10”.

Which operator has associativity from right to left?

The grouping of operands can be forced by using parentheses. For example, in the following statements, the value of 5 is assigned to both a and b because of the right-to-left associativity of the = operator.


1 Answers

I found a solution. Scala reference says in section 6.12.3 Infix Operations:

The associativity of an operator is determined by the operator’s last character. Operators ending in a colon ‘:’ are right-associative. All other operators are left-associative.

Therefore it was enough to rename >> to >>:.

It took me some time to realize that while a >> b is desugared into a.>>(b), a >>: b is desugared into b.>>:(a). So I had to define >>: as

def >>:(x: T): T = x >> this 
like image 188
Petr Avatar answered Sep 27 '22 22:09

Petr