How merge operation is associative in monoids?


#1

Like in video tutorial Introduction and Monoids, in this, they discuss about Category Theory and Monoids. But in one example where the instructor pick the example for merge operation, where he pick the sample for hash map. According to the instructor, the merge operation is Associative means change the sequence but the answer is remain same, but I have doubt on it. for example.

Following are HashMaps:

hm1 = {a -> 1, b -> 2 }
hm2 = {a -> 10, b -> 20 }
hm3 = {a -> 100, b -> 200 }

If we merge hm1 -> hm2 -> hm3 our results are
{a -> 1, b -> 2} // hm1 overdrives hm2 values and after result overrides hm3 values

If we merge hm3 -> hm2 -> hm1
{a -> 100, b -> 200} // reasons are same above.

So, Please correct me If am wrong. I am picking this example because in the case of commutative, the instructor pick this sample.


#2

Hi @Harmeet,

Thanks for the great question.

It looks like you’re confusing Associative and Commutative.

Associative means

hm3 -> (hm2 -> hm1) = (hm3 -> hm2) -> hm1

Notice that the order is the same, but the grouping is different.

Commutative means

hm1 -> hm2 = hm2 -> hm1

The order doesn’t matter.

Hashmaps are associative but not commutative.

Rock on!
Eric


#3

Thanks Eric, Now I got my answer, and it is really helpful for learning.


#4

Hi,

I have the same question, but I don’t understand when you say the order is the same. What are the brackets for, then? How is grouping different from ordering in that context?


#5

Hey @habibalamin,

Brackets are for grouping. Order is the order you write them in.

I do a pretty good job of explaining Associative vs Commutative in this talk:

Hope that helps!

Rock on!
Eric


#6

Hey @ericnormand,

I watched the video, but I was still lost. I think my point of confusion was that changing grouping seems to change order anyway, or if not, the brackets were confusing me. I was writing a response to explain my confusion, which helped clear it up in my head, so I’m going to post anyway, in case it might help anyone else.

a = { key: :a }
b = { key: :b }
c = { key: :c }

# associative
a.merge(b).merge(c) # => { key: :c }
a.merge(b.merge(c)) # => { key: :c }

# not commutative
b.merge(a) # => { key: :a }
a.merge(b) # => { key: :b }

What might help is to understand that there are orders in both of those; the first is concerned with the order of the multiple calls to merge, the second with the order of the arguments to the merge calls.

Let me know if I got anything wrong. I hope this explains why some people might get confused.


Incidentally, the Oxford dictionary doesn’t help:

associative | əˈsəʊʃ(ɪ)ətɪv, əˈsəʊsɪətɪv |
adjective
2 Mathematics involving the condition that a group of quantities connected by operators gives the same result whatever their grouping, i.e. in whichever order the operations are performed, as long as the order of the quantities remains the same, e.g. (a × b) × c = a × (b × c).


#7

Yeah, that’s confusing!

The order they are referring is the linear order the operands are written in, as in a + b + c.

That is, in

(a + b) + c = a + (b + c)

both sides of the equation have a then b then c. It is not the order you would do the calculations in to arrive at the answer (which does depend on grouping).

Good catch!

I like to think of order as “if I gave this work to different people, does it matter what order I get the answers back in? or can I just combine them as I get them?” For instance, if I had 20 people merging hashmaps, and some people are faster and some slower, I do care what order I get them back in. I would probably want them numbered to be able to reorder them.

However, I don’t care about the grouping. I could give 3 hashmaps to merge to the first person, 2 to the second, 15 to the third, etc. Or I could give 1 to the first person, 20 to the second person, etc. As long as the order is maintained, I can group them arbitrarily.

I hope this helps! I think you’ve got it, though.

Eric