# Better Encoding With Monoids in Scala

· Java Zone · Tutorial
Save
2.25K Views

Monoid has its root in abstract algebra. It is a semigroup with an identity; in other words, it has an associative binary operation and an identity element. In Scala, we can define it as follows:

Scala

`xxxxxxxxxx`
1

1
`trait Monoid[A] {`
2
`  def id: A`
3
`  def op(a1: A, a2: A): A`
4
`}`
5

In this article, we will discuss the law of Monoid from a Scala developer’s perspective, how it works in Scala, and various useful encoding patterns using Monoid.

## The Monoid Law

The Monoid law is the combination of the law of associativity and the law of identity. A monoid consists of the following:

• A type: A;
• An associative binary operation takes two parameters of type A and returns a value of type A;
• A value that does not change other values when applied with the binary operation.

The law of associativity states that the grouping of the binary operation does not change the result. For instance, the binary operation can be addition:

(a + b) + c = a + (b+c)

Or the binary operation can be multiplication:

(a*b)*c = a*(b*c)

The law of identity indicates both left identity and right identity; when applied with any value of type A in the associative operation; it does not change the result. For instance, 0 is the identity for addition:

0 + a = a + 0 = a

And, 1 is the identity for multiplication:

1*a = a*1 = a

Thus, an instance of monoid shall have all three terms defined: a type, an associative operator, and an identity value. For instance, `Monoid(Int, addition, 0)`, `Monoid(Int, multiplication, 1)`, are all different instances of monoid that comply with the law of monoid.  Thus, in Scala, a monoid instance is a tuple of three terms of Monoid trait: a type parameter, an identity value, and an associative function:

Scala

`xxxxxxxxxx`
1

1
`case class MonoidInstance[A](z: A, f: (A, A) => A) extends Monoid[A]`

where A defines a type, z is the identity value, and f is an associative function.

## Monoid Type Classes

Monoid implementation is typically type classes. As an important design pattern in Scala, type class is an approach to ad-hoc polymorphism; thus, each implementation of a parameterized type is an ad-hoc to Monoid trait. There are many great articles introducing type classes in Scala, for instance, here and here.

Let's see some very simple monoid type class implementations.

### `intAddition` Monoid

This monoid has a type of `Int`, an identity value of `0`, with an addition operation (`+`) as the associative operation. It can be implemented as:

Scala

`xxxxxxxxxx`
1

1
`MonoidInstance[Int](0, _ + _)`

### `intMultiplication` Monoid

This monoid has a type of `Int`, an identity value of `1`, with multiplication operation (`*`) as the associative operation, implemented as:

Scala

`xxxxxxxxxx`
1

1
`MonoidInstance[Int](1, _ * _)`

### `stringContact` Monoid

This monoid has a type of `String`, an identity value of empty string `""`, and string concatenation as the associative operation, implemented as:

Scala

`xxxxxxxxxx`
1

1
`MonoidInstance[String]("", _ + _)`

### `booleanOr`

For `Boolean`type, or operation takes `false`as the initial value, implemented as:

Scala

`xxxxxxxxxx`
1

1
`MonoidInstance[Boolean](false, _ || _)`

### `booleanAnd`

For `Boolean` type, and operation take `true` as its initial value, implemented as:

Scala

`xxxxxxxxxx`
1

1
`MonoidInstance[Boolean](true, _ && _)`

### `listMerge`

For a list of any given data element, `listMerge`can be a monoid: a type of `List`, an identity value of `empty` list, and list concatenation `++`, implemented as:

Scala

`xxxxxxxxxx`
1

1
`MonoidInstance[List[A]](List.empty[A], _ ++ _)`

### `Set` and Set Union

Can form a monoid, with its identity value of an `empty` set, implemented as:

Scala

`xxxxxxxxxx`
1

1
`MonoidInstance[Set[A]](Set.empty[A], _ ++ _)`

### `Map` and Map Merge

Can form a monoid, with identity value of an `empty` map, implemented as:

Scala

`xxxxxxxxxx`
1

1
`MonoidInstance[Map[K,V]](Map.empty[K, V], _ ++ _)`

### `Fold` With Monoid

Folding is a process to iterate over a collection of certain data elements. For instance,`List`has various folding options such as `foldLeft` and `foldRight`. We can abstract this folding trait as `Foldable`; by providing a monoid implicitly, we dedicate folding to the given monoid. A `Foldable`trait can be represented as follows:

Scala

As we can see, the trait has a type parameter `F` to represent the type of a collection. The type of the data element encapsulated in the collection is not important; it only becomes significant when the fold is actually called, while a monoid instance of this type is implicitly provided. This allows us to abstract folding without the knowledge of the identity value and the associativity function. This layer of abstraction by `Foldable` separates the concern of folding and the monoid, which can be implemented under different contexts and make them more re-usable.

Like monoid, `Foldable`is also type classes that implement the actual folding and composition, for instance, a `Foldable`of a list can be implemented as:

Scala

Thus, to concatenate a list of strings, we can do the following:

Scala

To find the sum of a list of integer, we can do:

Scala

### `foldMap` With Monoid

Folding is often coupled with a map that performs transformation to the encapsulated data elements. For instance, given a list of strings, we want to find the total length of the strings, we will map each string to its length and do a sum (literally a fold).

To understand `foldMap`, comparing to `flatMap`, which removes the inner grouping of data elements and making a transformation at the same time; `foldMap` iterates the data elements for calculation defined by the monoid, and making a transformation at the same time:

`foldMap` interface can be defined as:

Scala

As we can see, compared to `fold`, `foldMap`takes a function A => B, a function that transforms type A to type B. `foldMap` can be implemented generically as:

Scala

`xxxxxxxxxx`
1

1
`fold(s.map(f))(m)`

Thus, to find the total length of a list of strings, we can do the following:

Scala

where `_.length` is provided to transform a string to its length.

## Summary

Monoid abides by the law of associativity and identity. It’s very simple yet powerful in everyday programming. In this article, we discussed the law of monoid, the implementation of monoid type classes, and demonstrated various coding patterns of using monoid that can help us to write more generic and robust encodings in Scala.

The sample code in this article can be found on GitHub here.

Topics:
scala, functional programing, monoids, java, tutorial

Opinions expressed by DZone contributors are their own.