Typeclasses in Scala and Haskell

Posted by Jan Machacek

Find me on:

04-Oct-2012 19:00:00

I know I've already covered this topic, but let me repeat and tidy up what I've written before on typeclasses. And this time, I'll throw in some Haskell code for comparison.
In short, typeclass defines behaviour for a particular type; and a typeclass instance is the particular implementation of the behaviour for the given type. This allows us to move behaviour from our types into other components and let the compiler select the correct typeclass instance.

Let's say you want to be able to get some textual representation of values and imagine for a moment that your favourite language does not have a toString method on everything. (Or that it does not do a good job--think toString() in java.util.Date.)

def format(value: Any): String = ???

We are finding it difficult to define our function format, becasuse all we have is the value to be shown. And, to make matters worse, we don't even know its type. Making it polymorphic does not make much difference.

def format[A](value: A): String = ???

Even though we now know the type A, we're lacking any way of formatting the value of type A. We would like to automatically be given an instance of a component that can format values of type A.

trait Formatter[A] {
  def format(value: A): String
}

def format[A](value: A)(implicit formatter: Formatter[A]) =
  formatter.format(value)

Our format function is now far better. It takes the value of type A and the compiler supplies an instance of Formatter for the type A. The code above compiles, but if you actually tried applying the format function to---for example---42, the compiler would complain that there is no implicit view to Formatter[Int]. That's because we haven't given any instances of the Formatter typeclass. Let's do that now, and while we're at it, let's try different way of requiring typeclass instances.

trait Formatter[A] {
  def format(value: A): String
}

implicit object IntFormatter extends Formatter[Int] {
  def format(value: Int): String = "Number " + value
}

implicit object StringFormatter extends Formatter[String] {
  def format(value: String): String = value
}

def format[A : Formatter](value: A): String =
  (implicitly[Formatter[A]]).format(value)

Now we have instances of the Formatter typeclass for type Int and String. We also have the big-boy way of requiring typeclass instance in Scala: def format[A : Formatter](value: A): String; in the body of the function format, we need to pull the typeclass instance from the nether-world, using the implicitly function.

Checkpoint

So, we have the instances of the Formatter typeclass for some types. That lets the types drive the way in which they are formatted. We show numbers in one way, strings in another way, but the formatting behaviour is not part of the values being formatted!.
Typeclasses define behaviour for a particular type and typeclass instances implement that behaviour. In this sense, typeclasses are interfaces and typeclass instances are implementations of those interfaces. You do not instantiate the implementations, the compiler does, and it does so by matching the types.

Back to the fray

You now know that it is up to us to give the typeclass implementations (instances), but the compiler selects them. And so, typeclasses can work even in non-OO languages, like Haskell. Let's translate the same show code from above.

class Formatter a where
    format :: a -> String

Here, we have defined a typeclass Formatter for some type a. The typeclass contains the method format that take a value of type a and computes a String. Let's now throw in a few instances of the Formatter typeclass.

class Formatter a where
    format :: a -> String

instance Formatter Integer where
	format i = "Number " ++ (show i)

instance Formatter Bool where
	format = show

We can now apply the format function to the value of type Integer and Bool.

Typeclass inheritance

Let's now make other typeclass instances by applying them to containers of other things. How about being able to format lists of things? We will require typeclass instance for elements of the list and then apply the format to every element.

instance (Formatter a) => Formatter [a] where
	format as = show (map (\a -> format a) as)

See what I've done? To format a list of as, we need a Formatter instance for a. That's the instance (Formatter a) => bit. Putting it together, we have instance (Formatter a) => Formatter [a] where. The format method inside simply maps every element in the list to its formatted form and then calls the show function to display the resulting list of Strings.

Before I show you how to get the same thing done in Scala, let's indulge in a little bit of algebra. First, we can eliminate the lambda in (map (\a -> format a) as), because the first parameter of the function map is a function a -> b, which is what format is!

instance (Formatter a) => Formatter [a] where
	format as = show (map format as)

Let's continue by composing the show and map functions, because we want to eliminate as from both sides of the equation.

instance (Formatter a) => Formatter [a] where
	format = show . map format

We're missing Haskell's ad-hoc inheritance in Scala, but we can still subclass typeclasses. To create the Formatter typeclass instance for Seq[A], we write

implicit def seqFormatter[A : Formatter] = new Formatter[Seq[A]] {
  val formatter = implicitly[Formatter[A]]

  def format(value: Seq[A]) = (value map formatter.format).toString
}

I take similar shortcut to the Haskell code; I call toString on the sequence of formatted As.

Summary

I know I have rehashed a lot of topics I've already covered on my blog, but hope you will find the more detailed discussion of typeclasses and the reason for their existence interesting; and that the comparison with Haskell will also shed light on the language, and give you the answer to "how can one have inheritance in a non-OO language?"

Topics: Scala, Haskell

Subscribe to Email Updates