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

	trait Monoid[T] extends Semigroup[T] {
	def identity: T
	}

view raw Monoid.scala hosted with ❤ by GitHub

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:

	trait Semigroup[T] {
	/**
	* Must be associative to T
	*/
	def add(x: T, y: T): T
	}

view raw Semigroup.scala hosted with ❤ by GitHub

Example implementation for String is:

	val strMonoid = new Monoid[String] {
	def add(x: String, y: String) = x + y
	def identity = ""
	}
	import strMonoid._
	val w1 = add(add("1", "2"), "3")
	val w2 = add("1", add("2", "3"))
	assert(w1 == w2)
	val origin = "str"
	val w3 = add(origin, identity)
	assert(w3 == origin)

view raw stringMonoid.scala hosted with ❤ by GitHub

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.

	def reduce[T](ts: List[T], m: Monoid[T]): T =
	ts match {
	case Nil => m.identity
	case x :: xs => m.add(x, reduce(xs, m))
	}

view raw reduce.scala hosted with ❤ by GitHub

Method signature is

def reduce[T](ts: List[T], element: T, func: (T, T) => T): T

view raw signatureR.scala hosted with ❤ by GitHub

That is very similar to

def foldRight[T, E](ts: List[T], start: E, func: (T, E) => E): E

view raw signatureF.scala hosted with ❤ by GitHub

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.

	implicit object StrMonoid extends Monoid[String] {
	def add(x: String, y: String) = x + y
	val identity = ""
	}
	implicit object IntMonoid extends Monoid[Int] {
	def add(x: Int, y: Int) = x + y
	val identity = 0
	}
	def reduce[T](ts: List[T])(implicit m: Monoid[T]): T =
	ts match {
	case Nil => m.identity
	case x :: xs => m.add(x, reduce(xs))
	}
	println (reduce(List[Int](1, 2, 3)))
	println(reduce(List[String]("1", "2", "3")))

view raw implicit.scala hosted with ❤ by GitHub