## Thursday, February 5, 2015

### Monoids are easy

I've been avoiding the in-depth of functional programming for years. Now it seems I can't avoid it. So, without further a-do...

Monoids

Don't be put off by the esoterica you might expect with monoids. They're easy to understand.

From Functional Programming Scala:

"A monoid consists of the following:
• Some type A
• An associative binary operation, op, that takes two values of type A and combines them into one: op(op(x,y), z) == op(x, op(y,z)) for any choice of x:A, y:A, z:A
• A value, zero:A, that is an identity for that operation: op(x, zero) == x"

The first two properties describe a Semigroup.

Example of monoids include string concatenation, integer addition, float multiplication etc where the identities are the empty string, 0 and 1 respectively.

That's pretty easy. What about Options? Well, I've found two different ways of doing this. They give different answers but obey the same Monoid laws.

The first is in the FPS book. Chiusano and Bjarnason define their Monoid for Options as:

def optionMonoid[A]: Monoid[Option[A]] = new Monoid[Option[A]] {
def op(x: Option[A], y: Option[A]) = x orElse y
val zero = None
}

This basically gives you the first Option that's a Some or, failing that, a None.

Whereas the Scalaz guys invoke op on the contents of the Option if the Option contains another Semigroup. Their implementation looks like this:

implicit def optionMonoid[A: Semigroup]: Monoid[Option[A]] = new Monoid[Option[A]] {
def append(f1: Option[A], f2: => Option[A]) = (f1, f2) match {
case (Some(a1), Some(a2)) => Some(Semigroup[A].append(a1, a2))
case (Some(a1), None)     => f1
case (None, sa2 @ Some(a2)) => sa2
case (None, None)         => None
}

def zero: Option[A] = None
}

Where we invoke it with:

val stringOption  = Option("a string ")
val stringOption2 = Option("another string")

implicit val stringSemigroup: Semigroup[String]
= Semigroup.instance[String]((x, y) => x + y)

import scalaz.std.option.optionMonoid

val mySemigroup: Semigroup[Option[String]] = Semigroup[Option[String]]
println(mySemigroup.append(stringOption, stringOption2)) // Some(a string another string)

It gives a different answer but in both cases the actions are associative and once again, Nones are ignored.

There's a lot of Scala (black?) magic going on here with implicits but that's for another post.