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
?
A found a solution. Scala reference says in 6.12.3 Infix Operations:
Therefore it was enough to rename
>>
to>>:
.It took me some time to realize that while
a >> b
is desugared intoa.>>(b)
,a >>: b
is desugared intob.>>:(a)
. So I had to define>>:
as