Scala: Monoid

One of the simplest constructions in function programming is Monoid. Thanks to simple nature we are using it even without knowledge how it is named. Despite on this it's very interesting to review this in details. By the way this magic comes from Category Theory - which should be known by sophisticated developers;)

Comes from Semigroup:

In Function Programming Semigroup is set (presented by type T) and binary associative operation. Fast drop to both binary and associative:

Binary

Binary operation is any operation that requires two operands, for example

    2 * 2

    5 / 10

    list1 ::: list2

Associative

Formally, a binary operation on a set S is called associative if it satisfies the associative law:

Still not easy to refresh basic algebra, here are examples for associative operations:

     (1 + 3) + 9 = 1 + (3 + 9)

     (2 * 5) * 10 = 2 * (5 * 10)

And non associative operations:

     (5 - 1) - 1 ≠ 5 - (1 - 1)

     (6 / 3) / 3 ≠ 6 / (3 / 3)

As we can feel associative is simple property, but if your are implementing new business types, you should determine on design phase is your operation in type is associative or not.

Presenting Semigroup in Scala

But has an identity

Monoid can be presented via Semigroup (binary associative operation) and Identity. Identity is a special element type which leaves other element unchanged when combined with them in binary operation. While operation is binary and associative than both should be true:

    e * a = a for all a in S

and 

    a * e = a  for all a in S,

where e = identity. Usually it much faster to understand this from example for different binary operators:

For + identity is 0, proving the same: 0 + n = n and n + 0 = n.

For * operation identity is 1 and for logical and (∧) it's true.

Talking in Scala: Monoid is:
Example implementation for String is:

Folding on List

Formally there are 2 methods inside Monoid:
    1. accepts two arguments
    2. returns identity

Duel nature is looking very similar to List. As you can remember List consists from Monadic Zero (Nil) and elements linked with cons function (::), which takes two parameters: object of Type T and List of T (List[T]). With help of Monoid you can reduce list. Reduce function is function that takes a Sequence of objects type T (in our case List[T]) and iterates throw this values, producing T at the end. T can be presented via Identity as well.
Method signature is That is very similar to As we can see Monoid reduce approach is a special case of folding, but all laws are applicable to folding as well. It's possible to fold from left or from right because of associative method and stop event is determined via identity.

Monoids practices in Scala

I already highlighted View Bound construction in Scala. There are best practices with implicit parameter, it's easy to find example with Semigroup, and of corse Monoid when reduce is needed. Example with reduce is exactly the same as in the previous sub-chapter.