Ad-Hoc Polymorphism and Typeclasses in Scala, part 1

I recently offered to give a talk on this subject to the PDXScala meetup group in Portland, OR. I was just going to share my slides with participants, but they probably wouldn't have been too useful without my commentary - especially since I'm going to develop most of the code "live" in an editor and sbt. So, I decided to start a blog. It's a big subject for one blog post, so I'll do it in installments.

Roadmap

I'll start out by talking about the OO version of polymorphism most people are familiar with and discuss some of the limitations of it. Then we'll go on to how a language like Haskell, which is not object oriented, manages to have polymorphism anyway. This version of polymorphism is built into the Haskell language, but we'll figure out how we can implement it with Scala.

OO and Subtype Polymorphism

When object oriented programming came along, polymorphism was one of it's key features. By creating a class hierarchy, methods could specify an argument of a base type, but also accept any subtype as the argument. This is the familiar polymorphism that looks like this:

trait Animal {
 def speak: String
}

class Dog extends Animal {
 val speak = "Woof"
}

val dog = new Dog

In Scala you can also create an instance more directly:

val fox = new Animal {val speak = "???"}

And a function that takes an Animal:

def whatDoesItSay(animal: Animal): String = "It says " + animal.speak

val dogSays = whatDoesItSay(dog) 
val foxSays = whatDoesItSay(fox)

We could also write whatDoesItSay with a type constraint:

def whatDoesItSay[A <: Animal](a: A): String = "It says " + a.speak

This provides a great way to achieve flexibility in modelling many real world problems. However, it does have some limitations.

1. All the objects need to be part of a class hierarchy. You need to build the polymorphism into the classes from the start. This also means that you're stuck if you need use classes you can't modify, such as those from a class library.
2. You may need to add functionality to your class which really isn't behavior that belongs in your class. This is a violation of separation of concerns.

True, there are ways around this, such the adapter pattern in which you wrap your class in another class that implements the interface that you require, but this is not an ideal situation. I'm not going to go into this, but Debasish Ghosh talks about this in his blog post Scala Implicits: Type Classes Here I Come.

Note: There is also another form of polymorphism, parametric polymorphism, in which behavior does NOT vary with type. This can be seen in "generic" collections such as List[A]. You can make a List of ANY type - it is type agnostic. Essentially, it does not really interact with it's elements.

Ad-Hoc Polymorphism in Haskell

Since Haskell doesn't have classes, at least not classes in the same manner as Object Oriented languages do, how does it create polymorphism? The answer is typeclasses. I'm going to throw a little Haskell in here. Don't worry if you have trouble following it completely, I know Haskell syntax can be a bit hard to follow. You'll still be able to understand the rest of the post when we get to it. Mostly I want you to see how easy and elegant it is to do this in Haskell.

So, here's how you declare a typeclass:

class Show a where show :: a -> String

Show is actually one of the typeclasses that come with the standard Haskell libraries, but we'll pretend we just made it up. It's very much like this Scala trait:

trait Show[A] {
 def show(a: A): String
}

The Show typeclass declares one function, which converts an object of type A into a string. But how do you make a type part of this typeclass? You just say:

instance Show Bool where
  show True = "True"
  show False = "False"

This makes the Bool type an instance of the Show typeclass. Now you can use boolean values with the show function:

let x = True
let y = show x

Or create a function called showMe that requires an instance of a Show as an argument:

showMe :: (Show a) => a -> String
showMe a = "Is is " + show a

Now we can call showMe with x:

showMe x

Note that you just use the Bool value directly. You don't have to wrap it in an Adapter or anything. The compiler sees that an instance of Show is required and that Bool is an instance of Show and (sort of) takes care of the wrapping for you. It's like having the Adapter pattern baked into the language.

Hmmm. The compiler does the wrapping for us. Does that sound familiar?

Yep. Implicits in Scala. In part 2, we'll cover how to implement this in Scala using implicits.

Acknowledgements

I don't bill myself as a Scala expert, nor is anything I explain in these posts new. I have leaned heavily on a number of websites in preparing my talk and these blog posts, mashing them up a bit. In particular:

Scala Implicits : Type Classes Here I Come by Debasish Ghosh, which talks about typeclasses, the Adapter pattern, and more.

Learning Scalaz which explains scalaz by essentially going through the same steps as Learn You a Haskell.

This Scalaz Talk by Nick Partridge, which is not only excellent, but I attempted to use a similar style in my talk.

Of course if you want to learn about things functional, it doesn't hurt to know a little Haskell. Learn You a Haskell for Great Good is an excellent book.

Last, but not least, check out the source code for scalaz. The project really pushes the limits of what the Scala type system can do.