Get 10 days free access to Safari Books Online + 30% off first 6 months. START TRIAL NOW
|

Monoids for Programmers: A Scala Example

The term monoid frustrates a lot of programmers who otherwise are pretty versatile with higher-order generics, mutexes and even XSLT. This blog post will show how using monoids can be very simple and practical. Monoids are the basis of more complicated algebraic structures in mathematics, and are the underlying entities in many operations that we do while coding. There is a code sample in this post for Scala, which is becoming a lingua franca these days, and subsequent posts will focus on Scala.

When you deal with various types in a programming language you will notice common patterns of behavior for binary operations. Here are some examples:

  1. Integers with addition. We know that (a+b)+c == a+(b+c) and 0+n == n+0 == n; same with multiplication: (a*b)*c == a*(b*c) and 1*n == n*1 == n
  2. Strings with concatenation. a+(b+c)==(a+b)+c; ""+s==s and s+"" == s, etc.
  3. Lists with concatenation, like List(1,2)+List(3,4) == List(1,2,3,4).
  4. Sets with their union, like Set(1,2,3)+Set(2,4) == Set(1,2,3,4).

See a common pattern with a data type, a binary operation, and a special instance of the type, and certain rules? This common pattern is called monoid. Read Chapter 12: Monoids for more details about monoids.

Formally

Now, I’ll give a strict formal definition of monoid. Given a type T, a binary operation Op:(T,T) => T, and an instance Zero: T, with the properties that will be specified below, the triple (T, Op, Zero) is called a monoid. Here are the properties:

  1. Neutral element: Zero `Op` a == a `Op` Zero == a
  2. Associativity: (a `Op` b) `Op` c == a `Op` (b `Op` c)

Now, not every binary operation in the world is associative. For example, this average: avg(10, avg(30, 50)) != avg(avg(10, 30), 50); and for tuples, (a,(b,c)) != ((a,b),c).

So, you may be wondering what’s good about associativity? With an associative operation, you can reorganize a calculation in any order. Say, for instance, that we have the following expression:

(a1 `Op` (a2 `Op` (a3 `Op` (a4...))))

In Scala we have, (Zero /: a) (x `Op` y). This calculation can be regrouped and run in parallel, enabling map/reduce as follows:

(a0 `Op` a1 … `Op` a99) -------> p0 ---\
(a100 `Op` a101 … `Op` a199) ----> p1 ---->  p0 `Op` … `Op` p9	
. . .                                                                      /   
(a900 `Op` a901 … `Op` a999) ----> p9 --/

The definition above is all that you need to check whether you have a monoid. But it is important to see relationships between monoids. If you have just types, without any additional structure, any function, such as f:A=>B, is good for mapping instances of one type to instances of another. But if we have monoids, mappings between monoids should preserve operations.

Mappings Between Monoids

For two monoids, (A, OpA, ZeroA) and (B, OpB, ZeroB), we define a mapping from one monoid to another, such as with a function f: A => B, that f(ZeroA) = ZeroB and f(x OpA y) = f(x) OpB f(y).

Here are some good examples of monoid mappings:

Free Monoids

For any type T we can build a monoid on it. Such a monoid will have an interesting universal property, as discussed next.

Suppose we have a type A, a monoid (B, OpB, ZeroB), and a function f:A=>B. This function just maps instances of A to instances of B. Now we can extend this function to a monoid mapping from List[A] to (B, OpB, ZeroB).

Obviously, if we have f:A=>B, we can apply f to elements of any list of elements of type A, and then fold as follows:

  
f'(Nil) = ZeroB and f'(list1 + list2) = f'(list1) OpB f'(list2)

This monoid mapping is uniquely determined by f, and it defines f if applied to singletons.

List[A] is a free monoid because it’s built out of A with no constraints, in a universal way.

Let’s look at a simple example. Suppose we have the following:

						
object WeekDay extends Enumeration {
  val Mon, Tue, Wed, Thu, Fri, Sat, Sun = Value
}

And the following function:

						
WeekDay=>Int = (Mon->1, Tue->1, Wed->1, Thu->1, Fri->1,
Sat->0, Sun->0)

Having a monoid (Int, +, 0), we can automatically extend this mapping to List[WeekDay]->Int, which counts the number of working days.

More Properties?

Not all monoids are created equal. We can find classes of monoids that have additional properties, reflecting the nature of their operations. In this section we will discuss some of those properties.

Commutative Monoids

To start with, here is the commutativity law: for all a and b, a `Op` b == b `Op` a.

Some monoids are commutative, and some are not:

					
2+3==3+2

But that isn’t true with strings:

"hello" + "world" != "world" + "hello"

You might wonder if we can build a free commutative monoid? Say we have a list of characters: “abracadabra“. Forget about the concatenation order; we can just count the number of each entry – or sort the list, obtaining “aaaaabbcdrr“. Only the number of occurrences of each element matters – meaning, we have what is known as a Multiset or a Bag:

{
  "partridges in a pear tree": 1,
  "turtle doves": 2,
  "french hens": 3,
  "calling birds": 4
}

To count, say, all of the birds, we don’t need to know on which day they were appended to the multiset.

How About Sets?

Sets have an interesting property: a set A joined with itself is still set A. Instances with properties like this are called idempotent:

x `Op` x == x

If we take Bags and add the property for each instance that is idempotent, we have Sets.
Here’s the hierarchy, from Alexander Bunkenburg, “The Boom Hierarchy”.

In Scala

To define a monoid in Scala, we declare the following:

trait Monoid[T] {
 def Zero: T
 def op: (T,T) => T
}

Then, if we define a new class, it can also extend Monoid[T]. This is impossible if the class already exists, like, Int or String. We may need to specify which operation we mean to be the monoidal operation. This is where type class should be used. In Haskell, a type class is defined as just an interface. In Scala; however, it is more complicated. It can depend upon the scope, and involves a so-called witness object. All this will be explained in more detail in my next blog post, so stay tuned.

Safari Books Online has the content you need

Check out these monoid and Scala books available from Safari Books Online:

Learn You a Haskell for Great Good! begins with an overview of Node.js and then quickly dives into the code, core concepts, and APIs. In-depth coverage pares down the essentials to cover debugging, unit testing, and flow control so that you can start building and testing your own modules right away.
Real World Haskell takes you through the basics of functional programming at a brisk pace, and then helps you increase your understanding of Haskell in real-world issues like I/O, performance, dealing with data, concurrency, and more. Be sure to look at The Data Structures chapter to learn more about monoids.
Scala in Depth is a unique new book designed to help you integrate Scala effectively into your development process. By presenting the emerging best practices and designs from the Scala community, it guides you though dozens of powerful techniques example by example.

About the author

Vlad Patryshev was born in Russia, and has an education in Math (including now popular category theory). Since 1998 in the US, he worked at Borland (JBuilder team), then at Google in various teams, and had a 20% project, an onscreen keyboard, now available on various Google pages. He then changed several Bay Area startups, and now is working at HealthExpense.com. A functional programmer and a Scala fan since 2008, he is now an organizer of Scala BASE and Bay Area Categories and Types meetups. As a hobby, he rides his road bike, builds decks, and drives around the US (Key West to the Polar Circle in Alaska). He can be reached at @vpatryshev.

 

About Safari Books Online

Safari Books Online is an online learning library that provides access to thousands of technical, engineering, business, and digital media books and training videos. Get the latest information on topics like Windows 8, Android Development, iOS Development, Cloud Computing, HTML5, and so much more – sometimes even before the book is published or on bookshelves. Learn something new today with a free subscription to Safari Books Online.
|

Comments are closed.

Facebook Twitter RSS feed