Тот факт, что они ассоциативно справа , означает, что они анализируются "справа налево", так сказать. Таким образом, это означает, что x ⊕ y ⊕ z анализируется как x⊕ (y ⊕ z) . Таким образом, это означает, что x ++ y : z действительно анализируется как x ++ (y : z).
Существуют веские причины для правильной ассоциации (:) и (++). Для оператора "cons" (:) это означает, что мы можем написать 1 : 4 : 2 : [], поскольку он анализируется как 1 : (4 : (2: [])), что правильно с точки зрения типов. Если бы он анализировался как ((1:4):2:[]), то, например, 1:4 был бы неправильным, поскольку он ожидает элемент в качестве первого операнда и список этих элементов в качестве второго операнда. Конечно, мы все еще можем позволить анализатору Haskell анализировать его как список, но это приведет к большому количеству лишних скобок.
Для (++) лучше также проанализировать его справа налевоиз-за соображений производительности. x ++ y занимает линейное время в размере x. Так что это означает, что если мы проанализируем x ++ (y ++ z), потребуется | x |+ | y | шагов. Если бы мы проанализировали это как (x ++ y) ++ z, это заняло бы 2 × | x | + | y | , так как в первый раз, когда мы применяем (x ++ y), он работает в размере x, но затем(x ++ y) ++ z работает в размере x ++ y. Таким образом, это будет означать, что если мы объединяем n списков, каждый из которых имеет размер m , он не будет работать в O (n × m) , а в ** тысяча сорок-одна О (п * 1 042 * 2 * 1 043 * × м) . * * тысяча сорок-пять