Abstract alge..what?: Monoids

We are like the fascicles of tin soldier collections and the free enrollment at gyms … back in September! And with something that seems a little harsh but that surely after reading a few lines will be easier. Today we initiate a series of posts in which we’ll discuss some functional abstractions, that are very related to the world of mathematics, with the aim of being gradually introduced into the world of purely functional Scala libraries, such as as Scalaz or Cats. To do this, we will rely on some features and techniques that have already been discussed, such as type classes.

Today, we’ll start with monoids.

Monoids, monoids everywhere…

Monoid? Weird word. Let’s see what Wikipedia has to say about monoids:

“Algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are semigroups with identity.”

i-dont-understand

Hmmm… yes, right. What the hell? Let’s face it gradually.

  • Binary operation: ok, I get this one. It’s an operation with two operands. In order to follow the same convention, we are going to call this operation in a generic way with the symbol |+|.

However, the binary operation must comply with two rules:

  1. It must comply with the associative property, ie:  a |+| (b + c) = (a + b) |+| c
  2. And besides, it must have a neutral element.:   a |+| neutralElement = a

Hmmmm, that makes sense. For instance, the addition of integers follows the rules of monoids:

  • Associative property: 1 + (2 + 3) = (1 + 2) + 3
  • The neutral element is zero: 1 + 0 = 1

Same reasoning applies to the multiplication of integers (whose neutral element is 1), and the concatenation of strings as well (being the empty string “”, the neutral element). Great! I’m starting to get it.

Monoids in Scalaz

In order to work with monoids, in this post we will be using the Scalaz library. Scalaz offers us a wide range of options, abstractions and functionalities. Today we will only give you a glimpse of Scalaz in order to write an example. We promise to talk at great length about this library in the future 🙂

The first thing to do is to import Scalaz in our project. To do so, we have to include this library in the dependencies of our project:

libraryDependencies += "org.scalaz" %% "scalaz-core" % "7.1.3"

and now we write the following imports:

import scalaz._, Scalaz._

If we get a sneak peek at the library, we can find the Monoid  Monoid class, or the class Semigroup. They define the functionality we will make use of.

The Monoid class defines the zero method,, which serves us to indicate which is the neutral element. Furthermore, in the MonoidLaw trait, the fundamental rule that a neutral element must comply with is defined.

But, where is the information regarding the associative property?. Well, it is in the Semigroup class. It seems that monoids are an specialization of semigroups. Semigroups are responsible for the associative rule, while monoids add the rule of the neutral element. In fact, if we go to the Semigroup class, we can find the append method, which represents our binary operation |+|, and a bit further down we can see how the associative property is defined.

The next thing we must know is that Scalaz is based on a structure of type classes. This is why we will have to implement implicit objects, defining the inherent behaviour of our structures with respect to the monadic properties.

After this brief but (I hope) sufficient explanation, we will see how to apply all this knowledge to a simple example.

Creating our first monoid

Now finally, we will create our own monoid with Scalaz. Let’s start by creating new data types. We’ll create two types of atoms: oxygen and hydrogen.

trait Atom
case object Oxygen extends Atom
case object Hydrogen extends Atom

And finally, the molecule type. This type will have a certain number of atoms (which may be of different types), and a molecular stability.

case class Molecule(atoms: Map[Atom, Int], stability: Double)

jesse-pinkman-yeah-bitch-science

We want to work with our molecule type as if it were a monoid. For that purpose, and by using the Scalaz type classes, we’ll define an implicit object that defines the monadic behaviour of the molecule:

implicit object MoleculeIsMonoid extends Monoid[Molecule] {

  def zero: Molecule = Molecule(Map(), 1)
  def append(f1: Molecule, f2: => Molecule): Molecule = f1.fusion(f2)

}

We have decided that the neutral molecule is the one that has no atoms, and whose stability is 1, the maximum stability possible.

In addition, we have decided that the addition of molecules is delegated to a function called fusion. Let’s see how it’s defined:

case class Molecule(atoms: Map[Atom, Int], stability: Double) {

def fusion(other: Molecule): Molecule =
  Molecule(
    atoms = atoms |+| other.atoms,
    stability = stability * other.stability
  )
}

As we can see, the fusion of two molecules is the union of the atoms that compose them as if they were monoids. It turns out that Scalaz provides us with the functionality to address the combination of maps as monoids. In addition, we will combine the stabilities as if they were two probabilities, that is, multiplying them both.

The append method can also be represented by the symbol | + |, just as we had initially defined it.

And that’s all! We can now merge molecules using monoids and the operations that Scalaz provides us with for such abstractions:

val m1 = Molecule(Map(Oxygen -> 1, Hydrogen -> 2), 0.2)
val m2 = Molecule(Map(Oxygen -> 1), 0.3)

m1 |+| m2
//Molecule(Map(Oxygen -> 2, Hydrogen -> 2), 0.06)

List(m1, m2, m2, m1).foldLeft(Molecule(Map(), 1))(_ |+| _)
//Molecule(Map(Oxygen -> 4, Hydrogen -> 4), 0.0036)

Some(m1) |+| Some(m2)
//Some(Molecule(Map(Oxygen -> 2, Hydrogen -> 2), 0.06))

46196561

Conclusion

By the time you get to this point, I hope you’ll have lost the fear of bizarre words. As we have seen, algebraic abstractions are just a way of naming items that comply with some properties. Then, we can benefit from this abstraction to treat different operations in the same way. Today, we’ve seen monoids. Later on, other concepts you might have heard about will be discussed, such as the famous monads. Now you know, show off your knowledge about monoids to your friends and family 🙂

Anuncios

One thought on “Abstract alge..what?: Monoids

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s