Scalaz Types of Polymorphism

Polymorphism is a programming language feature that allows one interface to be used for a general class of actions.[1] Scalaz makes extensive use of ad-hoc polymorphism to provide its set of goodies. In this post I’ll cover ad-hoc polymorphism in detail and show you how you can implement ad-hoc polymorphism in Scala. I’ll also talk about parametric, and subtype polymorphism.

Parametric Polymorphism

In parametric polymorphism, the behavior of the function does not depend upon the type of the arguments passed to it. More formally[2],

Parametric polymorphism refers to when the type of a value contains one or more (unconstrained) type variables, so that the value may adopt any type that results from substituting those variables with concrete types.

1
2
3
4
5
6
7
8
scala> def head[A](xs: List[A]) = xs(0)
head: [A](xs: List[A])A

scala> head(List(1, 2, 3))
res0: Int = 1

scala> head(List("a", "b", "c"))
res1: String = a

Here, the argument xs has an unconstrained type A which can be anything and yet head would work. Then we call head with lists of concrete type Int, and String resulting in xs being of type List[Int] and List[String].

Subtype Polymorphism

Subtype polymorphism involves inheritance. More formally[3],

Subtype polymorphism is a form of type polymorphism in which a subtype is a data-type that is related to another data-type (the super-type) by some notion of substitutability.

As an example[4], consider a trait Plus which lets its subtype add itself with another of the same type.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
scala> trait Plus[A] {
| def plus(a2: A): A
| }
defined trait Plus

scala> def plus[A <: Plus[A]](a1: A, a2: A): A = a1.plus(a2)
plus: [A <: Plus[A]](a1: A, a2: A)A

scala> case class Currency(amount: Float, code: String) extends Plus[Currency] {
| override def plus(other: Currency) = Currency(this.amount + other.amount, this.code)
| }
defined class Currency

scala> case class Kilogram(amount: Float) extends Plus[Kilogram] {
| override def plus(other: Kilogram) = Kilogram(this.amount + other.amount)
| }
defined class Kilogram

scala> plus(Currency(1, "USD"), Currency(1, "USD"))
res4: Currency = Currency(2.0,USD)

scala> plus(Kilogram(1), Kilogram(1))
res5: Kilogram = Kilogram(2.0)

The function plus[A <: Plus[A]] will work only with those arguments that are subtype of Plus. This is restrictive because for this to work, the trait needs to be mixed in at the time of defining whatever concrete type A represents.

Ad-hoc Polymorphism

In ad-hoc polymorphism the behavior of the function depends on what the type of the argument is. More formally[5],

Ad-hoc polymorphism refers to when a value is able to adopt any one of several types because it, or a value it uses, has been given a separate definition for each of those types.

The simplest way to do ad-hoc polymorphism is by overloading functions. For example, having plus(Int, Int), plus(Currency, Currency), etc. The other ways are by using type classes, and coercion.

Type Classes

I’ll rewrite the Plus[A] example using type classes:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
scala> case class Currency(amount: Float, code: String)
defined class Currency

scala> case class Kilogram(amount: Float)
defined class Kilogram

scala> trait Plus[A] {
| def plus(a:A, b: A): A
| }
defined trait Plus

scala> object Plus {
| implicit object CurrencyPlus extends Plus[Currency]{
| override def plus(a: Currency, b: Currency): Currency = Currency(a.amount + b.amount, a.code)
| }
| implicit object KilogramPlus extends Plus[Kilogram] {
| override def plus(a: Kilogram, b: Kilogram): Kilogram = Kilogram(a.amount + b.amount)
| }
| }
defined object Plus

scala> import Plus._
import Plus._

scala> def plus[A](a: A, b: A)(implicit p: Plus[A]) = p.plus(a, b)
plus: [A](a: A, b: A)(implicit p: Plus[A])A

scala> plus(Currency(1, "USD"), Currency(1, "USD"))
res0: Currency = Currency(2.0,USD)

scala> plus(Kilogram(1), Kilogram(1))
res1: Kilogram = Kilogram(2.0)

Relating the above implementation to the formal definition, the implicit p was able to adopt one of CurrencyPlus or KilogramPlus depending on what arguments were passed. Thus the behavior of plus is polymorphic as its behavior comes from the definition of each of the types.

Coercion

The other way to implement ad-hoc polymorphism is coercion. Coercion refers to implicitly converting the argument into a type that the function expects. Here’s an example modeled around scala.runtime.RichInt:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
scala> class AwesomeInt(val self: Int) {
| def absolute: Int = math.abs(self)
| }
defined class AwesomeInt

scala> object AwesomeInt {
| import scala.language.implicitConversions
| implicit def asAwesomeInt(x: Int): AwesomeInt = new AwesomeInt(x)
| }
defined object AwesomeInt

scala> import AwesomeInt._
import AwesomeInt._

scala> -1.absolute
res0: Int = 1

The absolute method is defined in AwesomeInt but what we have is a plain old Int. This Int gets transformed into an AwesomeInt automagically because we have an implicit conversion within scope. The Int was coerced into an AwesomeInt.

So we see how ad-hoc polymorphism allows us to extend classes to whose code we don’t have access. We defined absolute to work with Int which comes from the Scala core library.

Higher-Kinded Types (HKT)

In the post where we generalized sum function, we generalized it to work with a List. What if we want to generalize it even further so that it can work with not just list but anything? Here’s what we want to achieve:

1
2
3
4
5
// we have this
def sum[A](xs: List[A])(implicit m: Monoid[A]): A = ???

// we want this
def sum[M[_], A](xs: M[A])(implicit m: Monoid[A], f: FoldLeft[M]): A = ???

The difference between the two is that the first version, although polymorphic over types for which we have monoids defined, is still heavily tied to List. The second version instead will work with type that is FoldLeft. We’ll expand upon the sum example[6]. We’ll need the monoids and we’ll need to add a FoldLeft to make sum more generic.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
scala> import scala.language.higherKinds
import scala.language.higherKinds

scala> trait Monoid[A] {
| def mempty: A
| def mappend(a: A, b: A): A
| }
defined trait Monoid

scala> trait FoldLeft[F[_]] {
| def foldLeft[A, B](xs: F[A], b: B, f: (B, A) => B): B
| }
defined trait FoldLeft

scala> object FoldLeft {
| implicit object FoldLeftList extends FoldLeft[List] {
| def foldLeft[A, B](xs: List[A], b: B, f: (B, A) => B): B = xs.foldLeft(b)(f)
| }
| }
defined object FoldLeft

scala> object Monoid {
| implicit object IntMonoid extends Monoid[Int] {
| def mempty: Int = 0
| def mappend(a: Int, b: Int) = a + b
| }
| }
defined object Monoid

scala> import Monoid._
import Monoid._

scala> import FoldLeft._
import FoldLeft._

scala> def sum[M[_], T](xs: M[T])(implicit m: Monoid[T], f: FoldLeft[M]): T = f.foldLeft(xs, m.mempty, m.mappend)
sum: [M[_], T](xs: M[T])(implicit m: Monoid[T], implicit f: FoldLeft[M])T

scala> sum(List(1, 2, 3))
res0: Int = 6

So, by using HKT, we can generalize across types.

Pimp My Library

You might wonder what the whole point of using so much polymorphism is. The answer is that it lets you inject new functionality into existing libraries without having access to their source code. To quote Martin Odersky[7]:

There’s a fundamental difference between your own code and libraries of other people: You can change or extend your own code, but if you want to use some other libraries you have to take them as they are … Scala has implicit parameters and conversions. They can make existing libraries much more pleasant to deal with.

So, by using all the polymorphism techniques, we can implement the “pimp my library” pattern.[8]

The Pimp my Library Pattern suggests an approach for extending a library that nearly does everything that you need but just needs a little more. It assumes that you do not have source code for the library of interest.

Conclusion

The polymorphism capabilities provided by Scala allow Scalaz to provide its set of features. By using HKT we can write code that truly generalizes across multiple types. It might seem like a long-winded way to do something so simple but as codebase gets larger and larger, the features that Scalaz provides out-of-the-box really help in eliminating boilerplate code. We haven’t seen how to use Scalaz, yet. These posts serve as a foundation to understand how Scalaz does what it does.

Scalaz Under the Hood

A lot of what Scalaz does is made possible by using ad-hoc polymorphism, traits, and implicits. I’ll explain how this works by borrowing from Nick Partridge’s talk on Scalaz.

Motivating Example

Let’s begin with a simple sum function that adds together all the elements in a List[Int].

1
2
scala> def sum(xs: List[Int]): Int = xs.foldLeft(0)( _ + _ )
defined function sum

The sum function above works only with List[Int]. If we want to sum together a List[Double], List[Float], or a List[String], we’d need a new implementation of sum. Our goal is to make sum function general so it would work with any of these.

Step 1 - Monoid

The first step towards generalizing sum is by using a monoid. A monoid is an algebraic structure with a single associative binary operation and an identity element.[1]. Since we are working with a List[Int], let’s create an IntMonoid.

1
2
3
4
5
6
7
8
scala> object IntMonoid {
def mempty: Int = 0
def mappend(a: Int, b: Int): Int = a + b
}
defined object IntMonoid

scala> def sum(xs: List[Int]) = xs.foldLeft(IntMonoid.mempty)(IntMonoid.mappend)
defined function sum

mempty is the identity or the zero value, and mappend is the binary operation which produces another Int i.e. another value in the set. These names come from Haskell[2].

Step 2 - Generalizing the Monoid

Next, we’ll generalize the monoid by creating a Monoid[A] so that IntMonoid is just a monoid on Int.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
scala> trait Monoid[A] {
def mempty: A
def mappend(a: A, b: A): A
}
defined trait Monoid

scala> object IntMonoid extends Monoid[Int] {
def mempty: Int = 0
def mappend(a: Int, b: Int) = a + b
}
defined object IntMonoid

scala> def sum[A](xs: List[A], m: Monoid[A]): A = xs.foldLeft(m.mempty)(m.mappend)
defined function sum

scala> sum(List(1, 2, 3), IntMonoid)
res3: Int = 6

What we’ve done is create a general-purpose sum function whose working depends upon which monoid is passed to it. Now we can very easily sum a List[String] or a List[Double] by adding a corresponding monoid.

Step 3 - Make the Monoid Implicit

Next, we’ll make the monoid an implicit parameter to our sum function. We’ll also package our IntMonoid into a Monoid companion object and make it implicit. The reason for doing this is how Scala compiler resolves implicit values; it’ll look for implicit values in its scope. So, we bring IntMonoid within scope by importing from the Monoid companion object.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
scala> trait Monoid[A] {
def mempty: A
def mappend(a: A, b: A): A
}
defined trait Monoid

scala> object Monoid {
implicit object IntMonoid extends Monoid[Int] {
def mempty: Int = 0
def mappend(a: Int, b: Int) = a + b
}
}
defined object Monoid

scala> import Monoid._
import Monoid._

scala> def sum[A](xs: List[A])(implicit m: Monoid[A]): A = xs.foldLeft(m.mempty)(m.mappend)
defined function sum

scala> sum(List(1, 2, 3))
res4: Int = 6

So, what we’ve done is create a general-purpose sum function that works as long as there is a corresponding implicit monoid within scope. This is made possible by using ad-hoc polymorphism. I’ll cover ad-hoc polymorphism briefly in this post and defer providing a detailed explanation for a later post.

Ad-hoc Polymorphism

Ad-hoc polymorphism is a type of polymorphism in which polymorphic functions are invoked depending on the different argument types. One way to implement ad-hoc polymorphism that we already know about is function overloading where a different “version” of the function is invoked depending on the type of arguments. This is what we’ve done in the post where there is only a single function but an implementation is provided for different types. In other words, sum only knows how to be invoked but the behavior is provided by monoids. Another way to implement ad-hoc polymorphism is coercion where the argument is converted into a type which the function expects.

So, by using ad-hoc polymorphism, Scalaz is able to provide general-purpose functions over existing types. Ad-hoc polymorphism is flexible in the sense that it lets you extend even those classes for which you do not have access to the source code i.e. classes from other libraries, etc.

Scalaz Introduction

Motivation

I’ve been using Scalaz for a while now and I remember not having any guides that provide a gentle introduction. It was a lot of scouring around, reading source code, and watching tech talks that gave me the understanding that I have now. This series of posts is intended at filling that gap by providing simple, step-by-step tutorials that will help you get productive quickly without compromising on the functional programming concepts.

What is Scalaz?

The documentation for Scalaz (pronounced Scala-zee or Scala-zed) states:

Scalaz is a Scala library for functional programming.
It provides purely functional data structures to complement those from the Scala standard library. It defines a set of foundational type classes (e.g. Functor, Monad) and corresponding instances for a large number of data structures.

In a nutshell, Scalaz aims to do three things:

  • Provide new datatypes that are not present in the core Scala library
  • Provide new operations on existing types a.k.a. pimp the library
  • Provide general-purpose functions so that you don't have to re-write them
  • I’ll provide a quick example of each of these without going into any details.

    New Datatypes

    1
    2
    3
    4
    5
    6
    7
    8
    scala> import scalaz._
    import scalaz._

    scala> import Scalaz._
    import Scalaz._

    scala> NonEmptyList.nels(1, 2, 3)
    res0: scalaz.NonEmptyList[Int] = NonEmpty[1,2,3]

    Here we are creating a NonEmptyList which is a list that is guaranteed to have atleast one element i.e. it’s never empty.

    New Operations on Existing Types

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    scala> import scalaz._
    import scalaz._

    scala> import Scalaz._
    import Scalaz._

    scala> val o = Option(3)
    o: Option[Int] = Some(3)

    // Scalaz way
    scala> o some { _ + 1 } none { 0 }
    res0: Int = 4

    // Scala way
    scala> o.fold(0)( _ + 1 )
    res1: Int = 4

    The first way of extracting value from an Option comes from Scalaz and is much more expressive compared to using fold from Scala standard library.

    General-Purpose Functions

    1
    2
    3
    4
    5
    6
    7
    8
    scala> import scalaz._
    import scalaz._

    scala> import Scalaz._
    import Scalaz._

    scala> List(1, 2, 3) |+| List(4, 5, 6)
    res0: List[Int] = List(1, 2, 3, 4, 5, 6)

    The |+| operator from Scalaz conveniently concatenated the two Lists together.