The Principles Behind Scalaz

Last updated: March 18, 2024

Reviewed by: Grzegorz Piwowarek

1. Introduction

In this tutorial, we’ll explore the basic principles behind Scalaz, one of the common libraries in the Scala ecosystem. It brings the best of functional programming to the world of Scala with pure functions and immutable data structures.

It also extends existing Scala features to increase expressiveness and brevity. Finally, it adds a suite of utility methods to do almost anything in Scala in a purely functional way.

If new to Scala, feel free to start with our gentle Introduction to Scala. To make the best of this article, we also need to understand ad-hoc polymorphism.

2. Implicits

Scalaz relies heavily on ad-hoc polymorphism. But to understand how Scala supports ad-hoc polymorphism, it’s critical to be versed with the concept of implicits. We should note that it’s one of the more confusing and frustrating concepts for anyone moving into the world of Scala.

2.1. Implicit Parameters

In very simple terms, just like each Scala method has function parameters like a, b in def max(a: Int, b: Int) as well as type parameters as we saw under parametric polymorphism, it can also have implicit parameters marked by the implicit keyword at the start of the parameter list.

Let’s take a look at how the sorted method used in Scala collections is declared:

def sorted[B >: A](implicit ord: Ordering[B]): Repr

Notice that it takes a generic type B so that it can be reused for nearly any type. However, it expects another parameter called ord of type Ordering, which defines a sorting strategy for that type. The native types in Scala that can be sorted all define an Ordering. So, for any custom type that we want to be sortable, we need to define an Ordering, too.

The keyword implicit tells the compiler that if the developer doesn’t provide an argument for ord, as we did before, then it should look for an appropriate variable that is accessible to the method in question and use that instead.

In other words, the compiler should attempt to resolve the dependency implicitly instead of expecting the developer to provide it explicitly.

If the compiler searches in all the available scopes and doesn’t find something that fits the type of the required implicit parameter, it throws an error.

2.2. No Implicit Arguments Exception

We can sort Int, String, and other built-in types without adding a new implementation of Ordering:

it should "sort ints and strings" in {
    val integers = List(3, 2, 6, 5, 4, 1)
    val strings = List("c", "b", "f", "e", "d", "a")

    assertResult(expected = List(1, 2, 3, 4, 5, 6))(integers.sorted)
    assertResult(expected = List("a", "b", "c", "d", "e", "f"))(strings.sorted)
}

Assume we introduce a new type that only wraps an integer:

case class IntWrapper(id: Int)

Then, if we try to call sorted on a List of our new type:

it should "sort custom types" in {
    val wrappedInts = List(IntWrapper(3), IntWrapper(2), IntWrapper(1))

    assertResult(expected = List(IntWrapper(1), IntWrapper(2), IntWrapper(3)))(wrappedInts.sorted)
}

The code won’t compile, and we’ll see the error that causes the compile failure:

No implicit arguments of type: Ordering[IntWrapper]

This error tells us that we need to define and provide a sorting strategy for our new type as Scala doesn’t know how to sort it.

2.3. Implicit Values

Implicit parameters can be fulfilled by providing an argument explicitly at the method invocation point.

However, that negates their essence. With the power of implicits, we can make our argument an implicit value by defining it with the implicit keyword, so that we don’t have to pass it to sorted explicitly:

implicit val ord: Ordering[IntWrapper] = (x, y) => x.id.compareTo(y.id)

With the above value provided within scope, the error we saw previously suddenly disappears. This means that the compiler can now see a way to sort IntWrapper types. When we run the test, it should pass.

The implicit value doesn’t even need to be within the same method — the implicit scope extends to the whole class as well as imported classes.

Using this same pattern, we can empower List.sorted to work with any arbitrary type we think of, simply by implicitly providing a separate implementation for each type that the compiler can switch to, depending on the type of the list’s elements.

3. Higher-Kinded Types

In functional programming, every variable or value declared in code is built using a certain type hierarchy. This is an advanced topic in Scala and functional programming cycles.

Therefore, we’ll begin from the basics of types and build through the type hierarchy.

3.1. Proper Values

Let’s take a look at some variable declarations:

val name = "Greg" 
val age = 34

In the above snippet, “Greg” is just raw data that makes complete sense without any further manipulation, and the same goes for the number 34.

In plain English, if we hear someone mention “Greg”, we’ll have very few unanswered questions about what they mean. We’ll call this a proper value because it’s in a final state.

3.2. Proper Types

From the previous subsection, the Scala compiler is able to infer the type of “Greg” to String and the type of 34 to Int.

Therefore, we can conclude that String and Int are proper types. In the type system, they’re in a final state because all they need is data to contain. We could’ve been more explicit with the types:

val name: String = "Greg"

3.3. Abstract Types

Let’s take another example:

val fruits = List("Oranges", "Apples", "Mangoes")

In this snippet, what we’re assigning to the variable fruits is also a proper value. The Scala compiler can again infer the type as List[String]. However, let’s think about if we can declare fruits with an explicit type:

val fruits: List = List("Oranges", "Apples", "Mangoes")

This won’t work, and compilation will fail with the error: Type List takes type parameters. Unlike String, List is not in a final state in the type hierarchy. It leaves an unanswered question: List of what type, or simply, List of what? Because the compiler expects a List to have values of a given type.

So, if one says List of strings, it makes sense just like List of names or ages. We can reasonably infer the inner type when the value category is mentioned. Now, let’s take the above declaration to its final state:

val fruits: List[String] = List("Oranges", "Apples", "Mangoes")

Therefore, String is a proper type, but List is an abstract type because it sits higher in the type hierarchy than String, Int, and other proper types. List needs to contain a proper type to make it proper. In the above example, List[String] is then a proper type.

3.4. Type Constructors

Following from the previous sub-section, something important to note is that List[_] is a type constructor. When given a concrete type, it constructs an instance of a List of that type. This is similar to a value constructor like StudentId(_). When given an integer student ID, it constructs an instance of StudentId.

The type List sits at the same level in the type hierarchy like other container types Option, Either, and Future. These container types are abstract until they are made specific by giving them a type.

That way, a container type reaches its final state. In other words, container types enable us to abstract overvalues or over proper types.

The fact that container types sit higher in the type hierarchy than proper types is the reason we can create abstractions like:

def sort[A](xs: List[A]): List[A]

This is parametric polymorphism, as we saw earlier. We can call sort on a List of any type by substituting type parameter A with a type argument, such as String or Int. Thus, value types are called proper types, and container types are called type constructors.

3.5. Abstracting Over Type Constructors

What if we could also abstract over type constructors? We can abstract over a proper type such as List[A] as seen in the snippet above, so why not over a type constructor like F[Int]?

In this case, we convert List into a parameter such that by providing a type constructor argument, we can replace it with any other type-constructor-like Option.

Let’s try it out. Imagine we have arbitrary integers in containers:

val nums = List(1, 2, 3)
val numOpt = Some(5)

And we want to double every contained element:

nums.map(_ * 2) // List(2,4,6)
numOpt.map(_ * 2) // Some(5)

This is easily done! Assume, hypothetically, that we want to create a single abstract function that can do the same operation whether we pass to it a List or an Option. Just like the sort function earlier, which can sort a List of any type, we want a doubleIt function that can take not only a list of integers, but any container of integers, and double the contained elements:

def doubleIt[F[Int]](xs: F[Int]): F[Int]

This is like parametric polymorphism, but over type constructors rather than over types. Think about how we would implement the body of this method such that we can pass to it any integer container without changing its implementation.

3.6. Higher Kinds

We can use a type-class as before. Remember, doubleIt needs help to know how to deal with any F[Int] it encounters, whether F turns out to be a List, Option, or any other type constructor we provide at method invocation time.

This help comes in the form of an implicit parameter:

def doubleIt[F[Int]](xs: F[Int])(implicit doubler: Doubler[F]): F[Int] = {
    doubler.makeDouble(xs)
}

We now need to define our type class:

trait Doubler[F[Int]] {
    def makeDouble(xs: F[Int]): F[Int]
}

object Doubler {
    implicit object listDoubler extends Doubler[List] {
        def makeDouble(xs: List[Int]): List[Int] = xs.map(_ * 2)
    }
    implicit object optionDoubler extends Doubler[Option] {
        def makeDouble(xs: Option[Int]): Option[Int] = xs.map(_ * 2)
    }
}

With this type-class in scope, doubleIt now knows how to double integers wrapped in a List or an Option:

"Doubler" should "work on any supported container type" in {
    val list: List[Int] = List(1,2,3)
    val opt: Option[Int] = Some(5)

    assertResult(expected = List(2,4,6))(actual = doubleIt(list))
    assertResult(expected = Some(10))(actual = doubleIt(opt))
}

This is where the term higher-kinded polymorphism comes from – abstraction over type constructors. In most cases, we’ll find a notation like F[_] instead of F with a proper type like F[Int] in our case. Of course, what we have is a contrived example.

Currently, our contained parameter is a proper type. What if we also want to abstract over it, such that the following test would pass:

"Doubler" should "work on any supported container type" in {
    ...
    val strList: List[String] = List("a", "b", "c")

    ...
    assertResult(expected = List("aa", "bb", "cc"))(actual = doubleIt(strList))
}

We’d have to change the signature of doubleIt to support this abstraction. Otherwise, the above test will fail to compile with the error: No implicits found for parameter doubler: Doubler[List, String].

Let’s upgrade the method signature:

def doubleIt[F[_], A](xs: F[A])(implicit doubler: Doubler[F,A]): F[A]

Likewise, we should update the type-class:

trait Doubler[F[_], A] {
    def makeDouble(xs: F[A]): F[A]
}

object Doubler {
    ...
    implicit object stringListDoubler extends Doubler[List, String] {
        def makeDouble(xs: List[String]): List[String] = xs.map(s => s concat s)
    }
    ...
}

4. Conclusion

In this tutorial, we’ve covered some of the foundational concepts that form the backbone of Scalaz. To explore more concepts that are used in Scalaz, check out our articles on type-classes and the pimp my library pattern.

When we encounter any Scalaz feature, we’ll be able to map what is happening to one or more of the concepts in this article and those referenced.

As usual, the complete source code is available over on GitHub.

Comments are open for 30 days after publishing a post. For any issues past this date, use the Contact form on the site.