Ad-hoc polymorphism with the typeclass pattern

from Wikipedia: "Ad hoc polymorphism is a dispatch mechanism: control moving through one named function is dispatched to various other functions without having to specify the exact function being called. Overloading allows multiple functions taking different types to be defined with the same name; the compiler or interpreter automatically ensures that the right function is called. This way, functions appending lists of integers, lists of strings, lists of real numbers, and so on could be written, and all be called append—and the right append function would be called based on the type of lists being appended. This differs from parametric polymorphism, in which the function would need to be written generically, to work with any kind of list. Using overloading, it is possible to have a function perform two completely different things based on the type of input passed to it; this is not possible with parametric polymorphism. "

The example problem: an optional value with a default

sealed trait Maybe[T]
case class Nothing[T]() extends Maybe[T]
case class Just[T](just: T) extends Maybe[T]

Consider the type Option or Maybe. This would be an example of parametric polymorphism in Scala code:

def fromMaybe[T](m: Maybe[T]): T = m match {
  case Nothing() => throw new Exception("Nothing")
  case Just(a) => a
}

notice that for any type T this function behaves the same way. Now suppose we want to not raise an Exception there, but to return a default value, obviously of the same type T. This is not something we can do generically for all types so we will need a dispatch mechanism that is control moving through one named function is dispatched to various other functions without having to specify the exact function being called. The default of Int could be 0, the default of String could be " "

This dispatch mechanism can be achieved with typeclasses in Haskell or implicit functions in Scala. I believe the first to be more idiomatic so I'll start with that one:

A Haskell example explained

The Scala code above would look like this in Haskell:

fromMaybe :: Maybe a -> a
fromMaybe Nothing = error Nothing
fromMaybe (Just t) = t

and we have to change it to look like this:

fromMaybe :: Default a => Maybe a -> a
fromMaybe Nothing = defaultValue
fromMaybe (Just t) = t

Where defaultValue is a function in the Default typeclass (which is somewhat like a trait in Scala) Default has been defined like this:

class Default a where
    defaultValue :: a

defaultValue will have a different implementation for different types a.

instance Default Int where defaultValue = 0
instance Default Char where defaultValue = ' '
instance Default [a] where defaultValue = []

Notice this line fromMaybe :: Default a => Maybe a -> a which tells the compiler that fromMaybe is polymorphic in type a, but that type a has a constraint: it has to have an instance for the class Default. The result:

map fromMaybe ([Just 5, Nothing, Just 10] :: [Maybe Int]) 
[5, 0, 10]
concatMap fromMaybe  [Just "Hello", Nothing, Just "World"]
"HelloWorld"

The Scala example explained

Let's start with the dispatcher/typeclass/trait.

trait Default[T] {
  def default(): T
}

object Default  {
  implicit val intDefault: Default[Int] = new Default[Int] {def default() = 0}
  implicit val stringDefault: Default[String] = new Default[String] {def default() = " "}
}

An alternative way to write this def default[T : Default](): T = implicitly[Default[T]].default is def default[T]()(implicit evidence: Default[T]) = evidence.default.

I picked the first one as it makes the function declaration easier to understand, more information about this [T : Default] can be found in the Scala documentation here, it is called a context bound and it describes an implicit value. It is used to declare that for some type T, there is an implicit value of type Default[T] available.

Another point about this pattern is that you can consider it as extending existing types with new behaviour without changine the initial type (Int, String, ...). Consider that it's not feasible to do class Int extends Default, because it is defined in the standard library.

object Maybe {
  def get[T : Default](m: Maybe[T]): T = m match {
    case Nothing() => implicitly[Default[T]].default()
    case Just(a) => a
  }
}

The result:

Seq(Just(5), Nothing[Int](), Just(10)).map(Maybe.get(_)) 
List(5, 0, 10)
Seq(Just("Hello"), Nothing[String](), Just("World")).map(Maybe.get(_)).reduce(_ ++ _) 
"Hello World"

Further reading

https://en.wikipedia.org/wiki/Ad_hoc_polymorphism

https://dzone.com/articles/scala-ad-hoc-polymorphism-explained

https://blog.scalac.io/2017/04/19/typeclasses-in-scala.html