Ad-Hoc Polymorphism and Typeclasses in Scala, part 3

In part 2, we developed an Equal subclass. Now we'll show how you can use Equal to build up additional typeclasses. We'll start by making a simple function that determines if a list has a value in it. (Part 1 is here.)

def has[A:Equal](as: List[A], a: A): Boolean = {
  as.foldLeft(false)((b, e) => b || e === a)
}

This is similar to the List.contains() method, but uses our Equal typeclass to do the comparison.

val ints: List[Int] = List(1, 2, 3, 4)
val hasIt = has(ints, 3)

However, we'd like to generalize our has function. We'll start by extracting out the concept of FoldLeft into a trait and implementing it for a List.

trait FoldLeft[F[_]] {
  def foldL[A, B](as: F[A], b: B)(f:(B, A) => B): B}

object FoldLeft {

  implicit val foldLeftList: FoldLeft[List] = new FoldLeft[List] {
    def foldL[A, B](as: List[A], b: B)(f: (B, A) => B): B = as.foldLeft(b)(f)
  }

}

The above trait and definition are very similar to what we did with Equal, with one big difference. FoldLeft's type parameter is not a simple value, it is a higher kind. I don't want to dig too deep into kinds now, but I'll give a brief explanation. If you want a better description, I recommend checking out Learn You A Haskell For Great Good.

In trait Equal[A], the A represents a on concrete type. You can create an instance of it directly, such as an Int or a String. In trait FoldLeft[F[_]], the F is a higher kind. It is a type that requires another type before it can be instantiated. For example, List or Option. You can't create a List, but you can create a List[Int].

Now we can modify our has function to use our new trait. (We're skipping a few of the steps we went through in part 2.)

def has[M[_], A](as: M[A], a: A)(implicit eq: Equal[A], fl: FoldLeft[M]): Boolean = {
  fl.foldL(as, false)((b, e) => b || e === a)
}

We can also simplify the function we pass by using the underscore syntax.

def has[M[_], A](as: M[A], a: A)(implicit eq: Equal[A], fl: FoldLeft[M]): Boolean = {
  fl.foldL(as, false)(_ || _ === a)
}

At this point, we still call has the same way. But, we'd like to be able to call it as a method on a list. We can't just use the Identity trait, because it doesn't provide enough type information. So, we'll create a new one. We'll also move the has function into the trait, and provide an implicit conversion method.

trait MA[M[_], A] {
  val value: M[A]

  def has(a: A)(implicit eq: Equal[A], fl: FoldLeft[M]): Boolean = {
    fl.foldL(value, false)(_ || eq.equal(_, a))
  }
}

implicit def toMA[M[_], A](ma: M[A]): MA[M, A] = new MA[M, A] {val value = ma}

Now we can use has like this:

val hasIt = ints has 7

We can go one step further. If our operator ends with a colon, it becomes right associative. In other words, the method will be called on the value to the right of the operator, with the value on the left passed as a parameter.

trait MA[M[_], A] {
  val value: M[A]

  def has(a: A)(implicit eq: Equal[A], fl: FoldLeft[M]): Boolean = {
    fl.foldL(value, false)(_ || eq.equal(_, a))
  }

  def >>:(a: A)(implicit eq: Equal[A], fl: FoldLeft[M]): Boolean = has(a)
}

So, we can use it like this:

val hasIt = 3 >>: ints

We can even make the operator unicode and use the element of unicode symbol.

def ∈:(a: A)(implicit eq: Equal[A], fl: FoldLeft[M]): Boolean = has(a)

val hasIt = 3 ∈: ints

If you do decide to create any unicode operators, I highly recommend providing a "plain text" alternative as well. In fact, you should think hard about creating operators: they should make sense and clarify the code, not make it more obscure.

That's as far as I'm going to go, but it gets much deeper. Check out scalaz or the resources in my acknowledgment section in part 1.

Ad-Hoc Polymorphism and Typeclasses in Scala, part 2

In part 1, we covered the types of polymorphism and how ad-hoc polymorphism works in Haskell. Now, we'll look at implementing it in Scala. We'll start with a basic example and build up to a better solution.

We'll implement an Equal typeclass (Eq in Haskell) that is used for comparing 2 values of the same type. To do this, we'll create a trait and an implementation of it for Ints.

trait Equal[A] {
  def equal(a1: A, a2: A): Boolean
}

class EqualInt extends Equal[Int] {
  def equal(a1: Int, a2: Int): Boolean = a1 == a2
}

We'll also make a function that uses it:

def areTheyEqual[A](a1: A, a2: A, eq: Equal[A]): String = {
  if (eq(a1, a2)) "Yes"
  else "No"
}

OK. It's a lame function, but it should serve our purposes for now. We can call the function like:

val areThey = areTheyEqual(1, 3, new EqualInt)

The function can now compare different types, as long as we pass an implementation for Equal for that type to it. But, it's a far cry from elegant. The next step is to make the Equal parameter implicit. This requires making another parameter group:

def areTheyEqual[A](a1: A, a2: A)(implicit eq: Equal): String ...

We can also define areTheyEqual() using context bound syntax like:

def areTheyEqual[A: Equal](a1: A, a2: A) = {
  if (implicitly[Equal[A]]equal(a1, a2) "Yes"
  else "No"
}

Either way, we can call it like:

val areThey = areTheyEqual(1, 3)(new EqualInt)

But, we can also pass the parameter implicitly if an appropriate value is in scope:

implicit val eq = new EqualInt
val areThey = areTheyEqual(1, 3)

The Scala compiler sees that the implicit parameter is missing, and goes looking for one for us. However, at this point we still need to create the missing implicit value. To make this easier, we'll put some default implicit values in the companion object for the Equal trait. If the compiler doesn't find an implicit value in the local scope or that is explicitly imported it will check in the companion object. This provides a convenient place to put the default implicit values.

object Equal {
  implicit object EqualInt extends Equal[Int] {
    def equal(a1: Int, a2: Int): Boolean = a == b
}

While the above works in almost all cases, it is better to explicitly give the type of implicit value to avoid some subtle type errors that can occur. You can do that like this (as well as adding an instance for Strings):

object Equal {
  implicit val equalInt: Equal[Int] = new Equal[Int] {
    def equal(a1: Int, a2: Int): Boolean = a == b
  }
  implicit val equalString: Equal[String] = new Equal[String] {
    def equal(a1: String, a2: String): Boolean = a == b
  }
}

The definitions for Int and String are identical here, but that is not the case in general. Now we don't have to create our own implicit val eq = new EqualInt, and we can also use areTheyEqual() for Strings:

val areThey1 = areTheyEqual(1, 3)
val areThey2 = areTheyEqual("xyz", "xyz")

Calling areTheyEqual() for different types is now simple and clean. As a library developer for Equal, you would want to provide a number of default implementations for different types. Users could then make their types "instances" of the Equal "typeclass" in the same way, without needing to alter their type at all.

But, what if you have a need to compare Strings by a different criteria - maybe case insensitive, or you only care about the length of the strings. You can create your own implicit instance, either in the local scope or in a package you explicitly import, and it will take precedence over the one defined in the Equal package:

implicit val equalStrLen: Equal[String] = new Equal[String] {
  def equal(a1: String, a2: String): Boolean = a1.length = a2.length
}

val areThey = areTheyEqual("abc", "xyz") // now is true

Of course, you can also still pass an instance of Equal explicitly:

val areThey = areTheyEqual("abc", "xyz")(equalStrLen)

Ok. That's great. But, one thing is still bothering me. I have to do my comparison like so:

  eq.equal(1, 3)

It would be much nicer to be able to call equal on one of the parameters, like 1.equal(3), or even use something that looks more like an operator: 1 === 3.

So far, we've used the implicit mechanism for passing an implicit parameter. But, there is another way it can be used - for implicitly converting one type to another. This is how Scala allows methods to be called on values like Int, which are not present in the Java implementation of them, while still being compatible with Java. When the Scala compiler sees a method being called on an object, but doesn't find that method defined on the object, it looks around for another class that DOES have that method, and for an implicit method that will convert the original type to that type. In the case of Int, if you type 5 min 7, the compiler sees Int does not have a min method, but it finds an implicit method that converts an Int to a RichInt, which does have that method, so it performs the conversion.

That is essentially what we want to do here, but we want to do it in a more general fashion. So, we'll start by creating a trait that can wrap any kind of value, and an implicit function for doing the conversion:

trait Identity[A] {
 val value: A
}

implicit def toIdentity[A](a: A): Identity[A] = new Identity[A] {val value = a}

So, now we can implicitly convert any type A to an Identity[A], but it doesn't do anything. To remedy this, we can add method definitions to the trait:

trait Identity[A] {
  val value: A

  def ===(a2: A)(implicit eq: Equal[A]) = eq.equal(value, a2)
  def =/=(a2: A)implicit eq: Equal[A]) = !eq.equal(value, a2)
}

The compiler will now allow us to call the === method on any type that can be converted to Identity (which is every type) AND for which there is an implicit Equal[A] available. Now we can use our trait in a much more natural fashion:

1 === 2
"abc" =/= "xyz"

I know what you're thinking: "Great! He just went to a lot of trouble to implement ==, and !=". But, there is one big difference. Equal is type safe. In the Scala REPL, if you use == on 2 different types, you'll see something like this:

scala> 1 == "one"

<console>:11: warning: comparing values of types Int and String using `==' will always yield false

       1 == "one"

         ^

res4: Boolean = false

It emits a warning, but does the comparison anyway. Let's try it with ===.

scala> 1 === "one"

<console>:15: error: type mismatch;

 found   : String("one")

 required: Int

       1 === "one"

             ^

You now get a compiler error if you try to compare dissimilar types.

We can also use the Equal typeclass in other typeclasses. In part 3, we will extend our example.

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.