Monoids for Java Developers

This article will cover what Semigroups, Monoids and Groups are and why every Java developer should know about them and how to use them.

semigroups

A semigroup is an associative binary operation across at least two instances of the same type. It can be represented by JDK interfaces such as BinaryOperator and BiFunction

BinaryOperator<T>
BinaryFunction<T,T,T>

Associativity

Associativity implies that the order of application is not significant

BinaryOperator<T> fn;
fn.apply(fn.apply(a,b),c) = fn.apply(a,fn.apply(b,c))

associativity law

String concatenation

An example Semigroup is String concatenation

BinaryOperator<String> concat = (a,b)->a+b;

String concatenation is associative, applying “hello”,”world” followed by “c” to concat is the samething as apply “hello” to the result of the application of “world” and “c”

concat.apply(concat.apply("hello","world"),"c") = "helloworldc"
concat.apply("hello",concat.apply("world","c")) = "helloworldc"

List concatenation

List concatenation is also a semigroup

BinaryOperator<List<T>> concat = (a,b)->{
                                          a.addAll(b);
                                          return a;
                                         };
List<T> listA;
List<T> listB;
concat.apply(listA,listB);

Other types of Semigroup

Integer addition

BinaryOperator<Integer> intSum = (a, b) -> a + b;

Boolean Conjunction (AND’ing)

BinaryOperator<Boolean> booleanConjunction = (a, b) -> a && b;

Boolean Disjunction (Or’ing)

BinaryOperator<Boolean> booleanDisjunction = (a, b) -> a || b;

Semigroups are not commutative

Although semigroups are associative

BinaryOperator<T> fn;
fn.apply(fn.apply(a,b),c) = fn.apply(a,fn.apply(b,c))

they are not commutative.

BinaryOperator<T> fn;
fn.apply(a,b) != fn.apply(b,a)

E.g. for String concatenation

BinaryOperator<String> concat = (a,b)->a+b;
concat.apply("hello","world");
//helloworld
concat.apply("world","hello");
//worldhello

semigroups are not commutative

Semigroups are in Java APIs already

The Stream API makes use of semigroups

Stream.of(1,2,3)
      .reduce(0,(a,b)->a+b); //semigroup in bold
//6

In the example above we are passing the Integer Addition Semigroup to the result method which will be used to sum all the values in the Stream.

Defining an interface for Semigroups

We can define a separate interface for Semigroup to indicate that a given BinaryOperator obeys the semigroup associativity law. The Semigroup interface from cyclops-react is defined as follows :-

Semigroups companion class

The Semigroups companion class in cyclops-react also provides a large number of predefined semigroups.

monoids

Monoids are an extension of semigroups that include an identity or zero element. The identity element should be a value (A) that when applied to another value (B) of the same type using the semigrop leaves the other value (B) unchanged.

Identity element for container concatenation

If we define a function that can concatenate containers (e.g. Lists o Vectors) we could visualize it’s operation on two values as something like this

Concatenation of a container type

The identity element for container concatenation is an empty container (or empty List or Vector)

identity element for container concatenation

This is because when we concatenate an empty container with another container the result is identical to the other container.

Concatenation using the Identity Element

Identity values

String concatenation : “”

List concatenation : [] <-empty list

Integer addition : 0 (0+ 1 = 1, 0 + 5 = 5 etc)

Boolean conjunction : true (true & false = false, true & true = true)

Boolean disjunction : false (false || false = false, false || true = true)

Monoids are in Java APIs already

The Stream API makes use of Monoids.

Stream.of(1,2,3)
      .reduce(0,(a,b)->a+b); //monoid in bold
//6

In the example above we are passing in the Integer addition Monoid. The 0 is the identity element for integer addition (0 + 1 = 1, 0+50 =50 and so on). A common misconception is that the first parameter to reduce is a seed value (a mistake I have made myself).

Seeding reduce

If instead of passing the appropriate identity element to the reduce method, we pass an initial / seed or default value a sequential Stream will behave as most users expect. Note however we are not passing in a well behaved monoid.

Stream.of(1,2,3)
      .reduce(10,(a,b)->a+b); //this is NOT a monoid
//16

This is because, when a Stream executes sequentially the identity element passed to reduce will be applied to the semigroup just once.

However if make use of the parallel operator we may get indeterminant results

Stream.of(1,2,3)
      .parallel()
      .reduce(10,(a,b)->a+b); //this is NOT a monoid
//indeterminate

10 is not an identity element for addition, the second value being summed is changed (10+1=11, 10+3=13 and so on). In parallel execution mode the identity element may be applied to the semigroup multiple times depending on how the data gets split up.

Parallel Streams

Monoids obey a distributive law which implies that, for example, applying the Monoid for integer addition over the dataset 1,2,3 and separately 4,5,6 followed by applying it to the result of both these opeations is the same as performing Integer addition on the entire dataset of 1,2,3,4,5,6.

[1+2+3] = 6
[4+5+6] = 15
[6+15] = 21
[1+2+3+4+5+6] = 21

This is why Monoids are used in the interface for parallel Streams, they allow us to pre-split the data set, and then apply our combination rules to those smaller datasets in parallel. The outputs of which can also be combined (in parallel if needs be) to safely generate the same result that would be calculated with sequential execution.

Defining an interface for Monoids

A Java Monoid interface can simply extend Semigroup and add the identity (or zero) element.

Monoids companion class

The Monoids class in cyclops-react provides a large number of prepackaged Monoids for use.

groups

Groups are Monoids that can be inverted. The Group for String concatenation is the Monoid for String concatenation and a function that inverts a String.

Integer Addition Group

Semigroup : (a,b)->a+b;
Identity : 0
Inverse : -x

Group<Integer> add = Groups.intSum;
concat.reduceReverse(Stream.of(1,2,3));
//-6

The inversion of groups must also obey some laws. As pointed out in the comments by @antinoia String concatenation does not form a lawful group. The combination of the inverse of a value with the value itself should equal the identity element for that monoid.

sum.apply(10,invert(10)) = 0
concat.apply(“hello”,invert(“hello”)) != “”

Defining an interface for Groups

A Java Group interface can extend Monoid and add an inversion function.

Groups companion class

The Groups class in cyclops-react provides a large number of prepackaged Groups for use.