Monoids
Monoids are algebraic structures that have an identity element and an associative binary operation. So what is a monoid? It’s a …
trait Monoid[A] {
def mempty: A
def mappend(a0: A, a1: A): A
}
defined trait Monoid
… and the associativity and identity rules which cannot be enforced by Scala 😞
Okay, but what can we do with it? Well the simplest thing to do is if we have a collection (monad) of monoids, we can apply the monoid’s binary operation recursively over the elements of the collection. That means we can fold over the elements, starting from the monoid’s identity and applying the binary operation recursively.
import Predef.{implicitly => as} // `implicitly` is just too long :)
// Haskell calls it mconcat, but it's also known as reduce
def mconcat[A: Monoid](xs: A*): A = xs.fold(as[Monoid[A]].mempty)(as[Monoid[A]].mappend)
import Predef.{implicitly => as}
defined function mconcat
Now, create some instances, so we can try it out!
// Addition on numbers is a monoid
def add[A: Numeric] = new Monoid[A] {
def mempty = as[Numeric[A]].zero
def mappend(a0: A, a1: A) = as[Numeric[A]].plus(a0, a1)
}
// as well as multiplication
def multiply[A: Numeric] = new Monoid[A] {
def mempty = as[Numeric[A]].one
def mappend(a0: A, a1: A) = as[Numeric[A]].times(a0, a1)
}
defined function madd
defined function multiply
Note on syntax: our context bound acts the same way as it were an implicit evidence. So
def mconcat[A: Monoid](xs: A*): A
and
def mconcat[A](xs: A*)(implicit ev: Monoid[A]): A
are the same, the former being syntactic sugar. Which means…
// ... you specify your instance this way.
val sumResult = mconcat(1,2,4)(add)
assert(mconcat(1,2,4)(add) == 7)
// okay but call this thing sum:
def sum[A: Numeric](xs: A*) = mconcat[A](xs:_*)(add)
assert(sum(1,2,4) == 7)
assert(mconcat(1,2,4)(multiply) == 8)
//name the product fold as well
def product[A: Numeric](xs: A*) = mconcat[A](xs:_*)(multiply)
assert(product(1,2,4) == 8)
// Gr8! Let's try out if the associativity rule really holds for a
// specific case
def mconcatRight[A: Monoid](xs: A*): A =
xs.foldRight(as[Monoid[A]].mempty)(as[Monoid[A]].mappend)
// ((1 + 2) + 4) = (1 + (2 + 4))
assert(mconcat(1,2,4)(add) == mconcatRight(1,2,4)(add))
sumResult: Int = 7
defined function sum
defined function product
defined function mconcatRight
Now, let’s concatenate lists! More generally, let’s do it for all things that are iterable!
Sure, simple as a cake!
def multiply[A: Iterable] = new Monoid[A] {
def mempty = as[Iterable[A]].empty
def mappend(a0: A, a1: A) = as[Iterable[A]].concat(a0, a1)
}
Well, well, not so fast. There isn’t a typeclass for standard Scala collection iterables. Instead we must use
CanBuildFrom for these.
import scala.language.higherKinds
// this is a bit nasty. we don't have a typeclass for iterable structures in scala, we have to use
// CanBuildFrom instead
import scala.collection.Iterable, scala.collection.generic.CanBuildFrom
def concat[A, I <% Iterable[A]](implicit bf: CanBuildFrom[I, A, I]) = new Monoid[I] {
def mempty = bf().result()
def mappend(a0: I, a1: I) = bf.apply().++=(a0).++=(a1).result()
}
import scala.language.higherKinds
import scala.collection.Iterable, scala.collection.generic.CanBuildFrom
defined function concat
Basically, we restrict our monoid to be a implicitly convertible to an Iterable. Then we use an implicit builder for this collection. Another method would be to use a lower type bound instead of a lower view bound like this:
def concat[A, I <: Iterable[A]](implicit bf: CanBuildFrom[I, A, I]): Monoid[i]
The view bound has the advantage over a type bound to be able to work with String, which doesn’t subclass nor Iterable, nor anything like it (it’s just the plain java.lang.String), but Scala has an implicit conversion from it to Seq.
// works for all sequences as long both all arguments are exactly T[U]
val resultSeq = mconcat(Seq(1,2,3), Seq(4,5,6))(concat)
val resultList = mconcat(List(1,2,3), List(4,5,6))(concat)
import scala.collection._
val mutableSeq = mconcat(mutable.Seq(1,2,3), mutable.Seq(4,5,6))(concat)
// even sets!
val resultSet = mconcat(Set(1,1,3), Set(4,4,6))(concat)
assert(mconcat(Set(1,1,3), Set(4,4,6))(concat) == mconcatRight(Set(1,1,3), Set(4,4,6))(concat))
resultSeq: Seq[Int] = List(1, 2, 3, 4, 5, 6)
resultList: List[Int] = List(1, 2, 3, 4, 5, 6)
import scala.collection._
mutableSeq: collection.mutable.Seq[Int] = ArrayBuffer(1, 2, 3, 4, 5, 6)
resultSet: collection.Set[Int] = Set(1, 3, 4, 6)
That’s great! Does it work for strings? With view bounds? Yes.
assert(mconcat("abc", "def")(concat) == "abcdef")
def join(xs: String*) = mconcat(xs:_*)(concat)
assert(join("abc", "def") == "abcdef")
defined function join
And that’s all I wanted to say. Next it’ll be something on applicative functors I guess.
(++) <$> ["Boom", "Bang"] <*> ["?", "!"]
println("Bye!")
Bye!