Types implementing `Semigroup` can now be passed to `sum`

case class Point(x: Int, y: Int) extends Semigroup[Point]{
  def combine(p: Point): Point = Point(x + p.x, y + p.y)
}

sum(Point(1,2) :: Point(2,5) :: Nil) // Point(3,7)

But it's impossible to retroactivly declare types we don't control (Like `scala.Int`) as `Semigroup`s. Scala offers two workarounds: the Adapter Pattern and Type Classes.

Lets first consider Adapters. Popularized by the Gang of Four and used in Java, we define generic wrappers for every type needed:

trait SemigroupLike[A]{
  def get: A
  def combine(a: SemigroupLike[A]): SemigroupLike[A]
}

case class Point(x: Int, y: Int)

case class SemigroupLikePoint(p: Point) extends SemigroupLike[Point]{
  def get: Point = p
  
  def combine(a: SemigroupLike[Point]): SemigroupLike[Point] =
    SemigroupLikePoint(Point(p.x + a.get.x, p.y + a.get.y))
}

case class SemigroupLikeInt(i: Int) extends SemigroupLike[Int]{
  def get: Int = i
  
  def combine(a: SemigroupLike[Int]): SemigroupLike[Int] =
    SemigroupLikeInt(i + a.get)
}

def sum[A](xs: Seq[SemigroupLike[A]]): A =
  xs.reduce((a,b) => a.combine(b)).get

But this requires users to laboriously create wrapper objects, which is both wordy and unperformant:

val a = SemigroupLikePoint(Point(1,2))
val b = SemigroupLikePoint(Point(2,3))

sum(a :: b :: Nil) // Point(3,5)

val x = SemigroupLikeInt(1)
val y = SemigroupLikeInt(2)

sum(x :: y :: Nil) // 3

Typeclasses circumvent the Adapter Pattern's issues, at the potential cost of greater complexity. Instead of extending type `T` with an interface to declare some behavior `B`, a typeclass implementation is an external object able to perform `B` on `T`. Beginning with the simplest of typeclasses, this post and its follow-ups should progress to the advanced definitions seen in the wild.

As implementations of the typeclass `Semigroup[A]` will be themselves combining elements of type `A`, a second parameter `b` is added to `Semigroup.combine`:

trait Semigroup[A]{
  def combine(a: A, b: A): A
}

case class Point(x: Int, y: Int)

`sum` can now be redefined as:

def sum[A](xs: Seq[A], semi: Semigroup[A]): A =
  xs.reduce(semi.combine)

And used after implementing `Semigroup` for `Point` and `Int`

val pointSemigroup = new Semigroup[Point] {
  def combine(a: Point, b: Point): Point =
    Point(a.x + b.x, a.y + b.y)
}

// As trait `Semigroup` has a single abstract method (SAM),
// Defining implementations with lambda syntax is supported in
// Scala 2.12.X
val intSemigroup: Semigroup[Int] = (a,b) => a + b

val a = Point(1,2)
val b = Point(2,3)
sum(Seq(a,b), pointSemigroup) // Point(3,5)

val x = 1
val y = 2
val z = 3
sum(Seq(x,y), intSemigroup) // 6

intSemigroup.combine(x,y) // 3

There are still many issues with our typeclass, namely:

• Semigroup instances must be manually passed around
• It would be preferable in many cases to use infix notation `1.combine(2)` vs `intSemigroup.combine(1,2)`

Implicit parameters solve the former. If a second `implicit` parameter list is added to `sum`, the compiler will attempt to find an implicitly declared instance, first using static scoping rules, and finally by checking the typeclass's static fields. Redeclaring `sum` and `intSemigroup`,

def sum[A](xs: Seq[A])(implicit semi: Semigroup[A]): A =
  xs.reduce(semi.combine)

Or alternatively using [Context Bound](http://docs.scala-lang.org/tutorials/FAQ/context-bounds) syntax,

def sum[A: Semigroup](xs: Seq[A]): A =
  xs.reduce(implicitly[Semigroup[A]].combine)

`sum` can now be called without passing `intSemigroup`

implicit val intSemigroup: Semigroup[Int] =
  (a,b) => a + b

sum(1 :: 2 :: 3 :: Nil) // 6

Implicits also permit a form of ad-hoc polymorphism when used with typeclasses; should a library designer declare common instances in the typeclass's companion object, users are free to pass or implicitly declare alternate definitions.

implicit val reversedStringSemi: Semigroup[String] =
  (a,b) => b + a

trait Semigroup[A]{
  def combine(a: A, b: A): A
}
object Semigroup {
  
  implicit val stringSemigroup: Semigroup[String] =
    (a,b) => a + b
}

// reversedStringSemi found first by compiler
sum("nick" :: "loves" :: "honey" :: Nil) // "honeylovesnick"

To scrap some boilerplate, we define static `Semigroup.apply[A]` to return the implicitly required `Semigroup[A]`.

object Semigroup { 
  def apply[A](implicit ev: Semigroup[A]): Semigroup[A] = ev
  
  ???
}

// or, using context-bound syntax

object Semigroup {
  def apply[A: Semigroup]: Semigroup[A] = implicitly
  
  ???
}

def sum[T: Semigroup](xs: Seq[T]): T =
  xs.reduce(Semigroup[T].combine)

Although I find the context-bound `Semigroup.apply` more appealing, the first version should be used because it can be inlined if desired.

Next up is infix syntax. Scala has [implicit classes](http://docs.scala-lang.org/overviews/core/implicit-classes.html) which allow just that:

object Semigroup {

  ???

  implicit class SemigroupOps[A: Semigroup](lhs: A){

    def combine(rhs: A): A = Semigroup[A].combine(lhs,rhs)

    /** alias for `combine` */
    def |+| (rhs: A): A = Semigroup[A].combine(lhs, rhs)
  }
}

import Semigroup._

Semigroup[String].combine("foo", "bar") // "foobar"
"foo" |+| "bar" // "foobar"

Regular implicit classes create a lot of wrapper objects, so `SemigroupOps` should be restructured as a [Value Class](http://docs.scala-lang.org/overviews/core/value-classes.html), which doesn't allocate any runtime objects when used correctly.

implicit class SemigroupOps[A](val lhs: A) extends AnyVal{

  def combine(rhs: A)(implicit semi: Semigroup[A]): A =
    semi.combine(lhs, rhs)

  /** alias for `combine` */
  def |+| (rhs: A)(implicit semi: Semigroup[A]): A =
    semi.combine(lhs, rhs)
}

Conclusions

Typeclasses are a powerful means of achieving retroactive polymorphism. In future posts, I hope to cover the different styles used by open source libraries like [spire](https://github.com/non/spire) and [cats](typelevel.org/cats/), with usability and performance considerations.