Associativity and parallel programming

3 min readOct 26, 2020

Associativity is very important and sometimes mendatory in order to run a proper parallel computation oncollections.

For example doing an addition in parallel is easy all we have to do is devide the collection in two parts (length/2), run a addition function in parallel and then add the two parts. It is possible to make it recursive in order to run more that two parallel processes by setting a threshold(minimum quantity of elements to use parallel computation ) and deviding the length of the collenction by two :

def recursivePara(list : List[Int]) : Int = 
  if(list.length < threshold ){
    list.reduce(_+_)
  }else{
    val middle = list.length/2
    parallel(recursivePara(list.slice(0, middle)),         recursivePara(list.slice(middle, list.length)))
  }

Note : you can´t run this directly since you need to define the abstract function parallel, but this gives you an idea of how it works.
Also it is not recommanded to use lists for parallel computations since we can´t always know its tail element. We will see this in a future story.

Definition of associativity :

lets now see what associativity has to do with all of that, lets first define it :

we say that a function is associative iff for every x,y,z we have :
f(f(x,y),z) = f(z,f(x,y))

last time we did a parallel computation on a list with addition function, we had no problem doing that since the funciton f (a,b) = a +b is associative which implies that we can devide the list in two parts and sum them without paying attention to the order (no matter what part computs first) since : 2 + (3 + 4)= (2 + 3) + 4, but what if instead of the sum function we had the difference function

list.reduce(_-_)

The final result would change according to the part that was computed first, for instance we have : 2–(3–4)= 3 and (2–3)-4 = -5.

Testing associativity :

it is possible to test associativity by comparing the returned values of the functions ReduceLeft and ReduceRight, I invite you to have a look at the use of these two functions through the following tutorial that explains them very well : https://levelup.gitconnected.com/scala-journals-part-4-data-manipulation-continued-99622b13c14a

Prove associativity :

It is possible to mathematically prove that a function is associative, for that lets start by defining commutativity :

definition of commutatitvity :

we say that a function f is commutative iff : f(a,b) = f(b,a) for every a and b

we can actually make a function commutative, by adding a simple if statement : for instance lets make the function minus commutative, we know that a-b ≠ b-a

def minus(a : Int, b : Int) 
def f(a,b) = if (a<b) minus(b,a) else minus(a,b)

now we have f(a,b) = f(b,a), and it is easy to make it general for all types by making the minus and f function polymorphic and by adding a function less :

def minus[A](a : A, b : A) 
def f[A](a: A, b : A) if (less(a,b)) minus(a,b) else minus(b,a=

Prove that a function is associative :

A function f is associative for every a,b and c if and only if :

f is commutative
f is rotative : f(f(a,b),c) = f(f(b,c)a)

therefore we can prove easly that the function is associative.