How to distinguish between commutativity and associativity

You confuse them a lot, and it's not your fault. They are similar in that they are both about order. Associativity is about the order of operations, and commutativity is about the order of arguments. We go through some examples to help clear up the distinction.

Transcript

Eric Normand: [laughs] Folks, this is the big one. How do you distinguish between commutativity and associativity? How do you tell the difference?

My name is Eric Normand, and I help people thrive with functional programming.

This is frustrating for me because I get these two confused all the time, even though I know the difference. I know I do.

I could write out the difference in math, but still, when I'm talking and when I just casually going through a problem, I make mistakes and it sucks. I think one of the problems is they are very closely associated, especially the way they're taught.

The examples that are given, which are usually addition and multiplication, don't distinguish between associativity and commutativity very well. Both addition and multiplication are both associative and commutative. If you use them as examples, you can't figure out from the examples which one is which.

In fact, it's hard if you find a function that's commutative. It's actually a little hard to find a commutative function that's not associative. You can find them. You can construct them. They're not that hard. It seems most of the simple, well-known mathematical functions that are commutative are also associative.

We're going to find some. We're going to talk about them in this episode. Let's get started.

I'm assuming that if you're listening to this, you understand some of the basics of doing math with parentheses. When you need parentheses, the order of operations, specifically in multiplication and addition, and the idea of arguments to your operators.

If we just have those basic ideas, we can clarify all of this.

One of the troubles is that both associativity and commutativity are about orders. I like to say commutativity is about order and associativity is about grouping. Maybe that just muddles it more because if you read on Wikipedia, they say associativity is about order of operations. They're talking about order again.

At least for this episode, I'm going to say that they're both about order. They're both about different orders, types of orders. Because when we write out a mathematical formula, x + y * z * w, then we've got different kinds of orders there.

First is the lexical order of everything written out. We needed to have some kind of linear order because that's how our paper works.

Then there's also a structural order to it. There's a nesting structure. That nesting is implicit when we write it out like that because we have this idea of order of operations. You're going to do the multiplications before you do the additions. We learn this in school.

If you're going to break that rule — you need to do an addition first before a multiplication — you put a parentheses around it. You put a pair of parentheses. That indicates, "Do this one before..." Break the rule for this one case. You're going to use these parentheses.

There's two orders. There's the lexical written order. Then there's the structural order that you're supposed to execute the computation in. That's the difference between the two orders. Associativity says the order of operations does not matter.

If you look at a + b + c + d, the order of operations does not matter. They're all plus. You could essentially draw parentheses around any way you want. You could start from the left, work a + b, then add c, and then add d. You start from the right. You could start with the d, then add the c, and then add the b. You could do that. You get the same answer.

That's what associativity means — that you could group it however you want. You could put the parentheses here, you could the parentheses here, you'd have the same answer.

This works because they're all plus. They're all the same operation. Once you throw times in there, it's not going to work anymore. You're going to have to obey the order of operations. When you've just got pluses, you can do that.

We could also call this grouping because that's what parentheses do. They group the operations with their operand. They group these expressions together. They tell you this one needs to stay together. This goes first. This one goes before everything else. They're indicating the order of operations, the order that you execute the expression in.

Commutativity is the order of arguments. This is the lexical order.

If I have a + b + c + d, it's a different expression to say d + c + b + a, but I'm going to get the same answer. I write it differently, but I get the same answer. That is commutativity. In a simpler expression, if I have a + b, it's the same as b + a. I've changed the order of the arguments. That's all commutativity is.

It saying you can change the order of the arguments without changing the meaning of that expression.

Let's look at an operation that is commutative but not associative. I don't want to fall into the same trap that we fall into with using plus for both associative and commutative. With commutative that means you can reverse the order of the arguments. Any order is going to give you the same result.

Here's an example — an average. If I want to give the average of two numbers, it doesn't matter what order they're in. I'm going to add the two up and I'm going to divide by two. That will give me the average of two numbers.

I know that this is not associative because I cannot say I want the average of a and b and c. Let's say I had an average operator. I can't do a average b average c. Why not? If I took the a and the b and I averaged them, I would get (a + b) / 2 and now I couldn't take that average and add in c and divide the whole thing by 2.

I'm going to get a different answer from if I do (b + c) / 2 and then add the a and then divide that whole thing by 2. That's not how you calculate an average. You have to add all of them up and then divide by the count. We've made this average function that works for two arguments but it's not associative now because of the way we implemented it.

Another example is equality. If I have something like a = b = c. That's something that we write casually in math that says that a and b and c are all equal; a = b = c. If I look at it like an operation that returns a boolean, let's say a, b, and c are numbers. I do a = b, that's going to return either true or false. Let's say it's true.

Then I compare that "true" to c, which is a number, it's going to be false. It doesn't really make sense anymore. I can't really call that associative. You noticed what's happening is we're returning a different type. We started with numbers. Take two numbers, compared them equal and we return a boolean.

One of the requirements of being associative is that you return the same type as your arguments. That's what lets the grouping happen structurally. If you add two numbers you're getting another number out, and so that lets you nest them. You can't really nest an equality check, and do an equality check to another number. You can't do that.

There are ways to make average and equality checks that are associative, but they're not the typical ways you would write them. Maybe one day, we'll go over those in another episode, but we're not going to go over those now. That's actually a pretty cool exercise. You should try it out.

Now, let's go over an operation that is associative but not commutative. Because it's dissociative, the order of operations does not matter. That's a double negative, sorry.

Because it's not commutative, the order of arguments does matter. Remember, associativity is the order of grouping does not matter, the order of operations doesn't matter, and then commutativity is the order of arguments does not matter. This one is a little easier to find because there are a lot of associative data structures — let's call them that — that do depend on the order of arguments.

String concatenation is associative. It's pretty clear to see it meets our requirements. If I take two strings, I concatenate them, I get a string out. Very easy. If I take three strings, and I concatenate them, it doesn't matter how I group them. If I have the string A, the string B, and the string C. If I group the A and B first, I have the string AB. Then I can add the C to the end, so that's ABC.

If I put the B and the C first, so I have BC as the string, then I put the A on the front, then I have ABC. I get the same string out. Notice, I cannot change the order of arguments. A concatenated with B is different from B concatenated with A. One, I get the string AB. The other, I get the string BA. Pretty clear. I just have to say it out loud for the recording.

This is an example of something that is associative, but not commutative. Much easier to find.

Another example is map merge. Map merge means given two maps, I make a new map that has all the keys of the first map, the first argument, and all the keys to the second. It returns a new map, and it takes two maps.

The reason the order matters, that you can't reverse the order of the of the two maps, is if there's a key collision, if map A and map B both have the same key with a different value, one of them is going to overwrite the other. Typically, we make the second argument overwrite the first argument.

That gives it an order, so you can't just reverse A and B, but it's still associative. If I have three maps, then I can group them either way. You can try that out yourself. It's going to be hard to talk about as a recording.

Let me recap. Both associativity and commutativity are about order. They both say that the order doesn't matter, but it's two different orders.

There's actually different orders going on. There's the lexical order that you have to write the thing out in. You have a + b + c. The a, b, c are in a certain order.

Then there's the structural order, which you can impose on that linear order that says how you're going to calculate this. You can calculate from the left or from the right, even from the middle if you wanted to. You can break it up in two. There's all sorts of ways you can do that.

Associativity and commutativity are trying to distinguish between those orders and say when and when it doesn't matter. Associativity says the order of operations doesn't matter. How you break up this big calculation and start tackling it into smaller operations, that is the order of operations. Associativity says it doesn't matter.

Commutativity says the order of arguments doesn't matter. Usually, this means changing the lexical order of how it's written. You go a + b + c. You go b + a + c. You're changing the order of how it's written. Sometimes, it matters. Sometimes, it doesn't. When it doesn't matter, it's called commutative.

We went over two operations that were commutative but not associative. You have average. Average of two numbers takes two numbers and adds them. That's associative and commutative, the addition is. Once you divide it by two, it's no longer associative, but it's still commutative. You're going to get the same answer no matter what order the arguments are in, but now, you can't group it in the same way.

Likewise, equality. It has a type change. What you're doing is — I'm talking about average again — you're taking two values, and you're returning an average value, which is basically a different type. It doesn't have the same properties of a measured value, like I measured all these people's heights. Now, I'm going to average them. It's a different thing.

Equality takes, let's say, two numbers and it returns a boolean. That's not associative, but it's still commutative. a = b is the same as b = a. You're going to get the same answer.

Finally, we have two examples of things that are associative but not commutative. String concatenation is associative but not commutative. You cannot do the string A + the string B and get the same as the string B + the string A. Map merge, also associative, not commutative.

Cool. Listen. If you want to see other episodes of this podcast or subscribe to this podcast, you can go to lispcast.com/podcast. There, you'll find all the old episodes, all the future episodes. In the future, you will find them. There's text transcripts, audio recordings, and video of all the podcasts.

You'll also find subscribe links and social media, such as email, Twitter, LinkedIn. Find me on those. Get in touch. Let's talk if you have a comment, a question. I love to get into discussions. If you find this too difficult, if you still want questions, if it's too easy, let me know. We'll talk.

I guess that's the end of this one. Rock on.