Typeclases in Scala & Haskell

Typeclass is a concept in Scala and Haskell (and in some other strongly-typed languages). The best way to think about a typeclass is that it is an interface, which defines functions. Great. Typically, everyone really understands this. The trouble comes when we have to apply the concept to practical code, especially if we’ve grown up with Scala and we now want to try out Haskel.


As I said above, typeclass is essentially an interface that defines some behaviour. Consider a Monoid typeclass for some type a. In Haskell, one writes:

class Monoid a where
  mempty :: a
  mappend :: a -> a -> a

This is the equivalent of a trait in Scala parametrized with type variable:

trait Monoid[A] {
  def mempty: A
  def mappend(a1: A, a2: A): A
}

If you look at these typeclass definitions, you should see that these are just the interfaces. They contain no behaviour. Let’s now find out how to define instances of typeclasses; a typeclass instance is an implementation of the interface (say, the Monoid above) for a specific type. Consider:

instance Monoid Int where
  mempty = 0
  mappend a b = a + b

Of course, being Haskell, we can eliminate the values in mappend and write just mappend = (+). Now, in Scala, we can have:

class IntMonoid extends Monoid[Int] {
  def mempty = 0
  def mappend(a: Int, b: Int) = a + b
}

If we now define a polymorphic function (with respect to its parameters), we can require that there be an instance of typeclass for the type.

sigma :: (Monoid a) => Int -> Int -> (Int -> Int) -> (Int -> a) -> a
sigma a b inc comp =
  if a > b then mempty else mappend (comp a) (sigma (inc a) b inc comp)

Before I dig into the details, let me show equivalent code in Scala:

def sigma[A](a: Int, b: Int, inc: Int => Int, comp: Int => a)
            (implicit m: Monoid[A]): A =
  if (a > b) m.mempty else m.append(comp(a), sigma(inc(a), b, inc, comp))

So, in Scala, we have to be a bit more explicit; we need to tell the compiler which monoid instance (instance here is the OO instance, a value that implements Monoid[A]). However, the compiler can search the implicit scope and find an instance of Monoid[Int]; of course reporting errors if it cannot find exactly one instance.

Now, class IntMonoid extends Monoid[Int] is not an instance. It is a class definition, and therefore the compiler will complain that there is no implicit instance of Monoid[Int]. In Scala, we have to provide an implicit value. We can do so by writing:

implicit val intMonoid = new IntMonoid

Or, in this particular case, we can actually make the Monoid[Int] a singleton!

implicit object IntMonoid extends Monoid[Int] {
  def mempty = 0
  def mappend(a: Int, b: Int) = a + b
}

If this object IntMonoid is in the current scope, the Scala compiler will be able to supply it as the value of the implicit m: Monoid[A] parameter; and our function compiles & runs as expected.

Haskell for great good

Compare the code in Haskell:

sigma :: (Monoid a) => Int -> Int -> (Int -> Int) -> (Int -> a) -> a
sigma a b inc comp = 
  if a > b then mempty else mappend ...

And the Scala code

// option 1: explicit implicits
def sigma[A](a: Int, b: Int, inc: Int => Int, comp: Int => A)
            (implicit m: Monoid[A]): A =
  if (a > b) m.mempty else m.append(...)
// option 2.1: type bounds
def sigma[A : Monoid](a: Int, b: Int, inc: Int => Int, comp: Int => A): A =
  if (a > b) implicitly[Monoid[A]].mempty else implicitly[Monoid[A]].append(...)
// option 2.2: type bounds and then consume implicit
def sigma[A : Monoid](a: Int, b: Int, inc: Int => Int, comp: Int => A): A = {
  val m = implicitly[Monoid[A]]
  if (a > b) m.mempty else m.mappend(...)
}

Because Scala is OO, there are more ways in which you provide the typeclass instances; even though ultimately, you have to have an implicit value available in the implicit scope. You can, however write

// implicit singleton value
implicit object IntMonoid extends Monoid[Int] { ... }

// implicit anonymous implementation
implicit val intMonoid = new Monoid[Int] { ... }

// implicit function that returns a new Monoid[Int] every time
implicit def intMonoid = new Monoid[Int] { ... }

// implicit named implementation
class IntMonoid extends Monoid[Int] { ... }
implicit val intMonoid = new IntMonoid

One might now think that in Haskell, the typeclass instances are equivalent of implicit object construct in Scala. Well, there are some terms & conditions!

Typeclass “inheritance”

We can have a kind of inheritance in our typeclasses. Let’s add typeclass for Group.

class Group a where
  mempty :: a
  mappend :: a -> a -> a
  inverse :: a -> a

This feels like too much typing. We would really like to “inherit” all functions from Monoid a and only provide the inverse. Our “inheritance” concept say that if I have an instance of Group for a, then I also have an instance of Monoid for the same a. It is not the traditional OO subclassing situation.

class (Monoid a) => Group a where
  inverse :: a -> a

Here, we have class Group for some type a, that “inherits” functions from Monoid for the same type a. To create instance of Group Int, we can now only provide the one remaining function.

instance Group Int where
  inverse = ((-1) *)

And we can now happily require these instances:

example :: (Group a) => a -> a
example a = inverse (mappend a a)

We can do the same thing in Scala, of course; though the syntax is a little more hairy, and sometimes, we have to deal with unpleasant side-effects. Let’s define Group[A], which extends Monoid[A].

trait Group[A] extends Monoid[A] {
  def inverse(a: A): A
}

Now, how do we go about creating instances of Group[A] if we already have Monoid[A]? We could, of course write the whole thing:

implicit object IntGroup extends Group[Int] {
  def mempty = 0
  def mappend(a: Int, b: Int) = a + b
  def inverse(a: Int) = -a
}

Or (inefficiently!) we can write code that’s similar to the Haskell code:

implicit def intGroup(implicit m: Monoid[Int]): Group[Int] = new Group[Int] {
  def mempty = m.mempty
  def mappend = m.mappend
  def invserse(a: Int) = -a
}

Here you can see that the compiler will create an instance of Group[Int], as long as it already has an instance of Monoid[Int]. This is where Haskell’s typeclasses really shine; Scala’s approach is not as efficient or elegant.

The epiphany

On a recent training ride, a friend told me, “I get typeclasses in Scala, but how can I call functions on the typeclass instances in Haskell?” Let me go back to the sigma function. In Scala, we write

def sigma[A](a: Int, b: Int, inc: Int => Int, comp: Int => a)
            (implicit m: Monoid[A]): A =
  if (a > b) m.mempty else m.append(comp(a), sigma(inc(a), b, inc, comp))

In Haskell, we write:

sigma :: (Monoid a) => Int -> Int -> (Int -> Int) -> (Int -> a) -> a
sigma a b inc comp =
  if a > b then mempty else mappend (comp a) (sigma (inc a) b inc comp)

The difference is that in Haskell, the compiler makes all functions from the typeclass available in the body of the sigma function; and it knows which one to call based on the types.

This entry was posted in Jan's Blog and tagged , , . Bookmark the permalink.

6 Responses to Typeclases in Scala & Haskell

  1. Pingback: This week in #Scala (16/12/2013) | Cake Solutions Team Blog

  2. Martin Odersky says:

    Nice post! I have a different solution to offer for typeclass inheritance. What you tried was first, duplication and then delegation. But you can use plain inheritance. The universally applicable rule is: if something can be refined further, make it a class. So:

    class IntMonoid {
    def mempty = 0
    def mappend(a: Int, b: Int) = a + b
    }
    class IntGroup extends IntMonoid {
    def inverse(a: Int) = -a
    }
    implicit object intGroup extends IntGroup

    – Martin

  3. Pingback: Typeclases in Scala & Haskell | Functional ...

  4. Good intro.

    That the implicit “dictionary” is passed explicitly (ha) in Scala has advantages, of course: being able to use different dictionaries simultaneously of the same type (where in Haskell you’d have to play a newtype trick). There are other advantages also, such as less confusion in the face of type inference. From the very inception of type classes in Haskell there was criticism of them on these grounds from the ML community, which promoted the explicit use of functors. And of course with GHC extensions it is feasible to adopt the explicit dictionary approach to type classes already, as promoted at http://www.haskellforall.com/2012/05/scrap-your-type-classes.html

    Interesting design tradeoffs, in any case.

    (BTW, there’s a typo “Monid” in two places in the post.)

  5. Nice post, although Monoid might be a little scary example for beginners :)

  6. Pingback: Typeclases in Scala & Haskell | Cake Soluti...

Leave a Reply