What are Monoids and Semigroups: explained with Type Classes[Scala].


Learn how to attain ad-hoc polymorphism with Type classes in a functional way.

Scala is one of the best programming languages❤.

you can choose to treat everything as function in Scala with referential transparency, modularity, maintainability and tons of syntactic sugars.

Functional approach is the best, to overcome shared and mutable state and to focus on results.

Type Classes do not have native support in Scala, so you can use built-in features like traits and implicit classes to achieve ad-hoc polymorphism.

What is ad-hoc polymorhism?

function with same name acts differently for different declared types.

lets understand the concept first and transition towards the how-to,
i believe that, if you are aware of the problem, then you can implement the solution better.

example-

"string concat" + "is a monoid"

we can add above 2 Strings, the same + can be used to add Int, List, tuples, Options. we can use it for many other operations which are mutable, but how? answer is ad-hoc polymorphism.


what are Monoids & semigroups,

Monoids- are important abstraction of Functional programming introduced in Haskell.
unaware of what they are, you use monoids everywhere, many mathematical operations are monoids.
concatenating a List, string, appending to List and operations on Scala Options are monoids(many more).

According to Wikipedia

Monoid-  is a Set equipped with an associative binary operation and an identity element.

wait what?
that’s difficult to understand. my personal experience, i didn’t get it the first time. lets break the definition to understand it better.

Monoid is generally a trait with a combine method and an empty method and should agree with associativity and identity algebric laws.

Associativity- is all about getting same results no matter how we shuffle the problem.

Code referred from cats library

think addition/multiplication –
with x, y and z as Int

x + (y + z) = (x + y) + z
(x * y) * z = x * (y * z)
results will always be same, this is associativity.

def associativeLaw[A](x: A, y: A, z: A)
(implicit m: Monoid[A]): Boolean = {
m.combine(x, m.combine(y, z)) ==
m.combine(m.combine(x, y), z)
  }

Identity- is an equation that is true for all chosen values.
Or
is an object with no side effects.

a/2 = a × 0.5 is true for all values of a: Int, this is identity.
a + 0 = a is true for all a: Int. (Update from Andrew’s Suggestion in comments)

def identityLaw[A](x: A)
(implicit m: Monoid[A]): Boolean = {
(m.combine(x, m.empty) == x) &&
(m.combine(m.empty, x) == x)
  }

if we write monoid definition in code it looks like this-

trait Monoid[A] {
  def combineOp(X: Int, Y: Int): Int
  def Zero: Int
}

Semigroup- is an algebraic structure consisting of a set together with an associative binary operation.

Code referred from cats library

a semigroup is structure with just combine method and no empty method, same algebric laws apply.

again why? is the question here, when we have monoid to do the empty methods job then why we need semigroup?

for some data types we cannot define empty/zero element.

trait semigroup{
  def combineOp(X: Int, Y: Int): Int
}

we can use semigroup to extend monoid and declare empty method, resulting in monoid.

trait monoid extends semigroup {
  def empty: Int
}

I know i confused you enough, let me show you how monoids and semigroups operate.

traits and Implicits as Type classes-

Type Classes- are programming patterns used to extend existing libraries with new functionality, without altering the original source code to attain ad-hoc polymorphism.

to know how associativity and identity laws work on monoid or semigroups, in-fact for many other uses, you should know Type classes, heavily used in Scala

lets break down the concept of Type class and see what pattern/structure does types classes agree with-

  • Type class Itself
  • Type class instance
  • Typed class interface methods

Type class- is like an API to implement functionality with a trait and at-least one Type variable, 

traits- are like code skeleton to declare what pre-conditions should the program agree with.

Classes and objects can extend traits, but traits cannot be instantiated and therefore have no parameters.

extended classes and objects should instantiated with the parameters declared in the trait skeleton/need to override the parameters without fail to meet the pre-conditions, if failed the compiler will show warning and throws error.

//  API to display users login info
  sealed trait loginAPI
  final case class Details(get: String) extends loginAPI 

//Type Class
 trait displayDetails[A] 
{ 
   def showemAll(d: A): loginAPI
}

above code represents the API which we want to use for different types and this approach can help you to use the same API for as many types you declare in the Type class instances.

Type class instances- 
declare instances that you want or are aware of which will be used in the implementation from standard Scala library of outside domain.

//  Type class instance
  object loginAPI {
    implicit val userDetails: displayDetails[String] =
      (d: String) => Details(d)
  }

Type Interface –
this is the functionality that we expose to the users to use the methods that are declared in more generic and functional way.

//  Type Interface
    object userInterface {
      def printDetails[A](details: A)(implicit value: displayDetails[A]): loginAPI =
        value.showemAll(details)
    }

Implicits- are the magic under the hood, taken care by Scala Compiler.

Implicit in Scala is about “automatically” passing values where needed / conversion from one type to another .

when you are declaring values or methods, if you add implicit keyword in-front of parameters and fail to pass them in the parameter list where required guess what will happen?

Scala compiler will work its magic for you by looking for the implicit value in scope and use it where required.

where does the compiler find the values to import?

  • lexical scope –  Scala compiler will look for implicit definitions and implicit parameters that can be accessed directly (without a prefix) at the point the method with the implicit parameter block is called.
  • imports – from the imports you make.
  • companion objects- compiler will looks for members marked implicit in all the companion objects associated with the implicit candidate type.


implicits are core language features of Scala that makes it possible to encode the type-class pattern.

println(userInterface.printDetails("DeadPool"))

if we use above snippet for out type class, the compiler will throw an error showing-

could not find implicit value for parameter value: tciExample.displayDetails[String]
  print(userInterface.printDetails("DeadPool"))

we need to bring the implict value into scope by importing companion object.

import loginAPI._

Implicits does the work for us to notify errors during compile time and import stuff automatically.

  • They cannot be defined as top-level objects.
    They must be defined inside of another trait/class/object.
//not supported
implicit object {
...
}

//supported
package object Implicits {

   implicit object example1....

   implicit object example2....
}
  • Implicits cannot take multiple non-implicit arguments in their constructor
//not supported
implicit def notSupportedWay(x: Int, y: Int) = {}

//supported
implicit def supportWay(x: Int)(implicit y: Int)={}
  • you cannot use implicit classes with case classes
object example{
  implicit case class example(x: Double) {}
//not supported
  • There cannot be any member or object in scope with the same name as the implicit class

Implicity- generic type provided by Scala standard library. We can use implicitly to summon any value from implicit scope.

best for debugging.

def implicitly[A](implicit value: A): A =value

Complete Code Snippet-

object tciExample extends App {

  //  API to display users login info

    sealed trait loginAPI
    final case class Details(get: String) extends loginAPI

  //Type class

    trait displayDetails[A] {
      def showemAll(d: A): loginAPI
    }

  //  Type class instance

    object loginAPI {
      implicit val userDetails: displayDetails[String] =
        (d: String) => Details(d)
    }

//  Type Interface

    object userInterface {
      def printDetails[A](details: A)(implicit value: displayDetails[A]): loginAPI =
        value.showemAll(details)
    }

  import loginAPI._
  print(userInterface.printDetails("DeadPool"))
  }

Conclusion-

Ad-hoc polymorphism is extensively used in Scala, helps to avoid repetitive implementations by declaring a generic Type class.
traits and implicits are Scala’s way to implement Type classes.
learning Monoids and Subgroups is a great start towards your FP journey.

Thanks for the support,
please leave a comment for any Typo or error and feedback.

2 Comments

  • Andrew

    There’s a slight problem here in your notion of Identity. You write “Identity- is an equation that is true for all chosen values.” While yes, that is one way that the word “identity” is used in mathematics (e.g. a trigonometric identity), in the context of algebraic structures the “identity” is a particular object (a.k.a. element) from the monoid/semigroup that “has no effect” under the binary operation. So a more illustrative example of an “identity element” would be something like
    a + 0 = a for all a: Int,
    rather than the example of a/2 = a * 0.5.
    Indeed, your code blocks actually illustrate this really well with the empty object; I just wanted topoint out a way you could improve the explanation mathematically 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *