3

If I say an operation is left-associative, is that equivalent to saying it "associates from the left" and "associates to the right"?

My confusion comes from an example in my functional programming Haskell textbook. It states:

Function application associates to the left. e.g. mult x y z means ((mult x)y)z. i.e. mult takes an integer x, returns a function mult x, which takes an integer y, and returns a function mult x y, which takes an integer z and returns the result of x*y*z.

But if I say it "associates to the left", I think of it being right-associative, i.e. evaluation starts from the right and to the left. However, since evaluation of mult starts from the left and to the right, is this left-associative? Should the author have said function application "associates to the right"? Or am I missing something and the author is correct?

Data
  • 689
  • 7
  • 23
  • 4
    You may be right that the terminology is a bit strange, but in practice it's clear enough: we always refer to _the side where the virtual parentheses are_. – leftaroundabout Apr 04 '18 at 09:59
  • They should mean the same thing although I've never seen this expression used. It's either left or right associative. Function application is left associative: x y z v = (((x y) z) v). You cannot say apply associates to the right though. – white_wolf Apr 04 '18 at 10:07
  • So whether we say it associates "to" or "from" the left, it is just simply "left associative", even though they imply opposite directions of association? – Data Apr 04 '18 at 10:10
  • Then it becomes a word game. Left and right associativity are perfectly understood as they are about grouping operators and I think using the opposition direction and the "to" is confusing. – white_wolf Apr 04 '18 at 10:15
  • I read "associates *from* the right" as "subexpressions coming from the right", and "associates *to* the right" as "subexpressions going off to the right" which both mean the same thing – luqui Apr 04 '18 at 11:11
  • 2
    [Precedence and evaluation order are distinct notions.](https://stackoverflow.com/a/45276894/3234959) – chi Apr 04 '18 at 13:32
  • If I can throw in my own unchecked terminology rationalisations - I always thought "left associative" and "right associative" were a bit close to "associative" - all relate to expressions with the brackets missing but the latter means bracketing doesn't matter, kind-of opposite to specifying where those brackets must go, yet general English grammar (unreliably) suggests "left associative" might be a special case of "associative". So "associates to/from the left/right" (which admittedly I find confusing) is, I've long assumed, probably a deliberate attempt to avoid "left/right associative". –  Apr 04 '18 at 13:57
  • 2
    @Steve314 That, on its own, is a good topic for a question. I would put it like this: "left associative" and "right associative" are *syntactic* concepts: they just mean `a @ b @ c` should be read as `(a @ b) @ c` or as `a @ (b @ c)` respectively. "Associative", however, is not a matter of mere syntax: it means `(a @ b) @ c = a @ (b @ c)`, which is truly a property of whatever `@` represents. We might perhaps say that being associative implies being both left and right associative, but that would be confusing, and mix up notions that work at different levels. – duplode Apr 05 '18 at 01:35

1 Answers1

14

You just need to stop thinking about evaluation order.

Bracketing is actually about expression structure, that is, which of these we mean when we say mult x y, not about how we may later decide to evaluate it.

      $           $
     / \         / \
    $   y     mult  $
   / \             / \
mult  x           x   y

Yes, we were taught in school that brackets are about the order you do things in. That's because we learned it in the context of arithmetic operators. Since these are all strict, there's less freedom to decide how to evaluate a given expression and the bracketing mostly determines an order. Plus we probably never thought much about expressions as abstract things distinct from the way they are written down.

In the more general context of Haskell we can't conflate parsing and evaluation. When we say something "associates left" or "to the left" we're only talking about how it's parsed. It tells you that the x belongs in a subexpression with the mult on its left and not with the y on its right.

(I haven't seen anyone use the phrase "associates from" and it doesn't really make sense unless maybe you read it as "associates away from".)

David Fletcher
  • 2,590
  • 1
  • 12
  • 14
  • “Associate from the left” is a translation of how it's commonly said in my native language, Czech. It can be imagined as that successive adding of parentheses around the part with the highest priority in the operation sequence wraps the sequence in parentheses from left to right, so, during the wrapping, a left part already is wrapped, and a right part isn't yet wrapped but will be later. – matj1 Apr 21 '22 at 16:22