Purely algebraic structures in Scala: monoids

What is a monoid

Let’s consider algebra of string concatenation. We can add “foo” + “bar” to get “foobar”. Algebra refers to the laws associated with the operation. Laws associated with the operation are

• Existence of an identity element

(S + "") => s
("" + s) => s

• Law of associativity

Consider 3 strings p,q and r
p + (q + r) = (p + q ) + r

The exact same laws govern integer addition. It is associative (x+y)+z = x+(y+z). Also there exists an identity element (0). Ditto for multiplication operation (identity element is 1). Boolean operators like && and || are likewise associative, they have identity element true and false respectively.

The algebras satisfies laws of associativity and existence of an identity element are called monoids.

Monoids come up in every day programming like whether we are aware of them or not. Working with lists,concatenating strings,accumulation of loop values all these can be phrased in terms of monoids. Monoid is very helpful in paralleling our code and implementing polymorphism.

A monoid consists following

• Some type A
• An associative binary operation, op that takes two values of type A and combines them into One.
• A value A that is identity for the operation

Monoids with Scala traits

trait Monoid[A]{
    def op(a1:A,a2:A):A  //Associative operation 
    def zero:A           //Existence of an identity element
}

An example instance of this trait is this trait is the string monoid.

val StringMonoid = new Monoid[String] {
    //String concatenation is an associative operation
    def op (a1:String,a2:String):String =a1+a2 
     //Identity element in string concatenation is an empty string
    def zero = ""                              
}

The above monoid can also be instantiated to List concatenation. A monoid is a type together with a monoid operation and certain set of laws. A monoid is the algebra and nothing more.

Folding lists with monoids

Monoids have an intimate connection with lists. Let us look at fold-left and fold-right examples on list.

def foldRight[B](z:B)(f: (A,B) => B):B
def foldLeft[B](z:B)(f: (B,A)=>B):B

The component of monoid defined earlier fits these arguments. So if we have a list of strings,we could simply pass the op and zero of StringMonoid in order to reduce the list and concatenate the string. Note that it doesn’t matter whether we use fold-left or fold-right, results will be same. This happens exactly because it holds law of associativity. A left fold operation associates values to left, and right-fold does vice versa.

val words=["hello","welcome","all"]
val result = words.foldRight(StringMonoid.zero)(StringMonoid.op))
println(result)
// results in hellowelcomeall
val results_right = words.foldLeft(StringMonoid.zero)(StringMonoid.op)
println(results_right)
// results in hellowelcomeall

Associativity and parallelism

If we reduce the list using balanced fold, which can lead to more parallelism. For example consider a sequence a,b,c,d. Folding the list to right would look like.

op(a, op(b, op(c,d)))

Folding to left would look like

op(op(op(a,b),c),d)

But a balanced fold operation would look like this:

op(op(a,b),op(c,d))

Note that balanced fold allows more parallelism as two inner lists can be executed in parallel. Moreover balanced fold would save from more operation as the number of recreation of arrays will be less for example,moreover balanced lists will be more efficient as the cost of operation directly proportional to it’s parameter. In the fold operation after reducing (a,b) a new array will be created copying all the values of a&b it will take a time proportional to a.length + b.length. Complete trace of expression would look like.

Fold 0 - List("Hello", "World" , "Welcome" ,"All")
Fold 1 - List("Hello", "World" , "Welcome" ,"All")
res2="HelloWorld"
Fold 2 - List("Hello", "World" , "Welcome" ,"All")
res3="HelloWorldWelcome"
Fold 3 - List("Hello", "World" , "Welcome" ,"All")
res4="HelloWorldWelcomeAll"

A more efficient strategy would be,splitting the list into two halves “HelloWorld” and “WelcomeAll” and combine them together. Now consider a huge text file we want to parse, it would be very nice if we are able to split the text file into multiple chunks and parse them parallely. We are only able to perform the task because the function is associative.

Monoid homomorphism and isomorphism

Consider the following example of concatenation of two strings:

“foo”.length + “bar”.length == ( “foo” + “bar” ).length

Here taking the length of two strings and adding them up is same as concatenating the string and taking it’s length. Here length is function from string to integer that preserves the monoid structure. A monoid homomorphism f between M and N obeys the following general law for all values x and y.

Homomorphism comes from Greek, homo means “same” morphe means “shape”.

M.op( f(x),f(y)) == f(N.op(x,y))

Sometimes there will be homomorphism in both direction between two monoids, then we can say two monoids are isomorphic. For example String and List[char] concatenation monoids are isomorphic. The two boolean monoids (false,||) and (true,&&) are also isomorphic via negation function.