У меня есть ассоциативная операция >>. Проблема в том, что его стоимость линейно зависит от размера его левого операнда. Таким образом, выражение, образованное последовательностью n приложений >>, таких как
a >> a >> a >> a >> a >> ... >> a
он имеет квадратичную стоимость в терминах n, потому что по умолчанию операторы infix left-associative. Как сделать его право-ассоциативным, чтобы стоимость такого выражения сохранялась линейной в терминах n?
Я нашел решение. Справочник Scala говорит в разделе 6.12.3 Операции с инфиксами:
Ассоциативность оператора определяется оператором последнего символа. Операторы, оканчивающиеся на двоеточие: ассоциативны справа. Все остальные операторы левоассоциативны.
Поэтому было достаточно переименовать >> в >>:
Мне потребовалось некоторое время, чтобы осознать, что в то время как a >> b десугарируется в a.>>(b), a >>: b десугарируется в b.>>:(a). Поэтому я должен был определить >>: как
def >>:(x: T): T = x >> this