text: .
  Our motivation for the inaugural post of the series will be
  summing a
  List of something. Lets start out with
  Int,
  which is simple enough.
  def sum(l: List[Int]): Int = l.reduce(_ + _)
  And this works (kind of, it fails on empty
  Lists but we’ll get to that).
  But what if we want to sum a
  List[Double]?
  def sumDoubles(l: List[Double]): Double = l.reduce(_ + _)
  The code is the same, modulo the type parameter. In fact, the
  code would be the same whether it is
  Int,
  Double, or
  BigInt.
  Being the good programmers that we are, let’s make this generic
  in that respect with the help of
  scala.math.Numeric.
  def sumNumeric[A](l: List[A])(implicit A: Numeric[A]): A = l.reduce(A.plus)
  Awesome. We can now sum
  List[Int],
  List[Double],
  List[BigInt],
  and many more.
  But let’s give this a bit more thought - what if we wanted to
  “sum” a
  List[String] - that is, we concatenate all the
  Strings
  together to create one large
  String ?
  def sumStrings(l: List[String]): String = l.reduce(_ + _)
  This looks exactly like summing
  Int and
  Doubles! This however
  does not work with our
  sumNumeric - there is no (sane) way to define
  a
  Numeric[String].
  Another way to look at this is that we only use the
  plus method
  on
  Numeric, never any of the other methods that also make sense
  for numeric types. So while our function works for summing a List
  of numeric types, it does not work for anything else that is not
  numeric but can still be “added” (
  String and string concatenation,
  List[A] and
  List#++).
  So what do we want? We want a type class that only requires instances
  to be able to “add” two
  As to get another
  A.
  trait Addable[A] { def plus(x: A, y: A): A }
  And let’s define an instance of
  Addable for all
  Numeric types and
  String.
  object Addable { implicit def numericIsAddable[A](implicit A: Numeric[A]): Addable[A] = new Addable[A] { def plus(x: A, y: A): A = A.plus(x, y) } implicit val stringIsAddable: Addable[String] = new Addable[String] { def plus(x: String, y: String): String = x + y } }
  And here’s our shiny new generic summer function!
  def sumGeneric[A](l: List[A])(implicit A: Addable[A]): A = l.reduce(A.plus)
  And now this works for
  Int,
  Double,
  String, and many more.
  A good exercise at this point is to define an
  Addable instance for
  List[A].
  What happens when we pass in an empty
  List to our summer function though?
  We get an exception! How do we prevent this? A common answer I get is
  “Oh I know it won’t happen” – this is not ideal, we want to guarantee safety
  as much as possible without having to rely on human judgement.
  How then do we write a safer summer function? Lets turn to an alternative
  way of implementing sum on
  List[Int].
  // Old, bad version def sum(l: List[Int]): Int = l.reduce(_ + _) // Shiny, new version def sum(l: List[Int]): Int = l.foldLeft(0)(_ + _)
  What happens now when we pass an empty
  List into the sum function? We get 0,
  not an exception! Note that before all we gave the program was a binary
  operation (what
  Addable defines), where now we give a binary option and a
  “zero” or starting value (the 0). As it stands, we cannot write this with
  Addable since it has no “zero”.
  It may be tempting to just add a
  zero method to
  Addable, but then we may run
  into the same issues we had with
  Numeric later on – we don’t always need
  a “zero”, sometimes a binary operation is good enough. So instead, let’s create
  an
  AddableWithZero type class.
  trait AddableWithZero[A] extends Addable[A] { def zero: A }
  Note that while you dont see the
  plus method in here, the fact
  it
  extends Addable without implementing the
  plus method propagates the need to
  implement that method, so programmers who want to create an
  AddableWithZero[A] instance
  need to implement both.
  Programmers can now write functions that depend only on
  Addable, or perhaps if they
  need a bit more power use
  AddableWithZero. Types that have
  AddableWithZero instances
  also have
  Addable instances automatically due to subtyping.
  Lets move our
  Addable instances to the
  AddableWithZero object.
  object AddableWithZero { implicit def numericIsAddableZero[A](implicit A: Numeric[A]): AddableWithZero[A] = new AddableWithZero[A] { def plus(x: A, y: A): A = A.plus(x, y) def zero: A = A.zero } implicit val stringIsAddableZero: AddableWithZero[String] = new AddableWithZero[String] { def plus(x: String, y: String): String = x + y def zero: String = "" } }
  And finally, our shiny new generic sum function!
  def sumGeneric[A](l: List[A])(implicit A: AddableWithZero[A]): A = l.foldLeft(A.zero)(A.plus)
  Hurrah!
  It turns out that our
  Addable and
  AddableWithZero type classes is not just us being
  sly and clever, but an actual thing! They are called
  Semigroup and
  Monoid (respectively), taken from the wonderful field of abstract algebra. Abstract
  algebra is a field dedicated to studying algebraic structures as opposed
  to just numbers as we may be used to. The field looks into what properties
  and operations various structures have in common, such as integers and
  matrices. For instance, we can add two integers, as well as two matrices of the same size.
  This is analogous to how we noticed the
  plus worked on not only
  Numeric
  but
  String and
  List[A] as well! This is the kind of generecity we’re looking for.
  Here’s what
  sumGeneric looks like in Scalaz land.
  import scalaz.Monoid def sumGeneric[A](l: List[A])(implicit A: Monoid[A]): A = l.foldLeft(A.zero)((x, y) => A.append(x, y))
  Thankfully we dont have to create our own versions of
  Semigroup and
  Monoid –
  Scalaz has one for us! In fact, the developers of Scalaz have been kind enough to define
  several
  Monoid instances for common types such as
  Numeric,
  String,
  List[A], etc.
  There are also instances for tuples – if we have a tuple, say of type
  (A, B, C),
  and all three types have
  Monoid instances themselves, then the whole tuple has an
  instance where the
  zero is the tuple
  (A.zero, B.zero, C.zero) and the
  plus is
  appending corresponding pairs between the two tuples. Look for instances that may already
  be defined before defining your own on existing types.
  To close this post off, I confess one thing: defining a
  Monoid (and
  Semigroup) instance
  should not be done without some thought. It is not enough that you simply have a zero and
  a binary operation – to truly have a
  Monoid or
  Semigroup certain laws must be obeyed.
  These laws are as follows:
  Call the
  plus operation $+$ and the
  zero value $0$. Arbitrary values of type
  A will be
  referred to as $a$, $b$, etc.
  The
  Semigroup law requires $+$ to be associative. That is:
  In addition to the
  Semigroup law for the binary operation, the
  Monoid law relates
  $+$ and $0$:
  To check these laws, Scalaz provides ScalaCheck bindings to help you, but that is a topic for another day.
  Note that a particular type can have several
  Semigroup or
  Monoids that make sense.
  For instance,
  Int has a
  Monoid on $(+, 0)$ as well as on $(*, 1)$. Convince yourself
  (using the above laws) that this makes sense.
  This raises the question of how we get both $+$ and $*$
  Monoids for
  Int without
  making
  scalac freak out about ambiguous implicit values. The answer is “tagged types”,
  again a topic for another day.
  If you have any questions/comments/concerns, feel free to hop onto the IRC channel on
  Freenode at
  #scalaz.
  Unless otherwise noted, all content is licensed under a Creative Commons Attribution 3.0 Unported License.Back to blog