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.