Commutative TypeClass and its relation to Associative TypeClass

[vakkadar]

In Zio prelude Commutative[A] extends Associative[A] even though everyone is aware of the fact that they two completely independent properties. The reason for this decision is that in most common business use cases commutative and associative properties are satisfied together. But there are few examples especially with respect to numerical computation and machine learning, it will fail are

1. Matrix Multiplication which is heavily used in many machine learning models
2. List Concatenation is associative but not commutative
3. https://en.wikipedia.org/wiki/Commutative_magma (Vector Multiplication as per this link has scenarios where it is commutative bu not associative)

So I propose to revisit this design.

Can we have

trait Associative[A] extends Closure[A] {

private [prelude] def associativeCombine(left;A, right:A): A

def combine(left;A, right:A): A = associativeCombine(left, right) }

trait Commutative[A] extends Closure[A] {

private [prelude] def combinerPar(left;A, right:A): A

def combine(left;A, right:A): A = combinerPar(left, right) }

Then trait CommutativeAssociative{A] extends Commutative[A] with Associative[A] can only have instances where both properties are satisfied. Otherwise such an instance is impossible to create as they will fail laws.

Please let me know if you need more details

[adamgfraser]

@vakkadar Thanks for raising this issue!

One important thing to keep in mind here is that since Commutative extends Associative we have a way to describe two kinds of operations:

1. Those that are associative but not commutative (by implementing Associative)
2. Those that are both associative and commutative (by implementing Commutative)

Both of the examples you gave (list concatenation and matrix multiplication) are operations that are associative but not commutative. So we can describe them quite easily by defining Associative instances for them. In fact, an Associative instance is already implemented for list concatenation and the only reason there is not one implemented for matrix multiplication is because there is no default implementation of a matrix in Scala's standard library.

So I feel like this comes back to where we were before, where yes theoretically there are some operations that are commutative but not associative (just like there are some operations that have an inverse but are not associative) but practically all the examples we see seem to be either only associative or associative and commutative.

[vakkadar]

@adamgfraser did you see my update on vector multiplication which talks about Non Associative Commutative Magma. Also I understand the rationale for such a decision but still for a library which will be critically reviewed, I think either this rationale needs to be articulated in the main README in a section like assumptions or reviewed with a newer design

[adamgfraser]

@vakkadar Thanks for pointing that out! I responded to your original post so I don't think I would have seen your update otherwise.

That is an interesting example with the rock, paper, scissors game. I think we are all in agreement that there are certain operations that are commutative but not associative (the arithmetic mean of two numbers was raised before and is also mentioned in the article you cite). However, it still seems to me that we are coming up with examples for the sake of coming up with examples versus because there are practical things we want to do but can't.

The mean can very easily be made associative by keeping track of the number of observations in addition to the mean. And vector multiplication is associative outside of cases where you embed an operation like the rock, paper, scissors example where you essentially do an ordering operation on something that is a cycle instead of having a total ordering.

I think one of our goals in this library is to be pragmatic and at least right now I'm still not seeing examples of commutative but not associative operations that programmers are going to use on a day to day basis.

On the other hand I think there are significant costs to splitting them out because I think in the vast majority of cases when you want an operation that is associative you actually want an operation that is commutative and associative so now people need two type classes instead of one.

I did try to add some additional documentation regarding this issue here.