ADTs in Scala for Object Oriented Programmers

  • Date : January 1, 0001
  • Categories :
  • Tags :

One of the many aspects that you need to learn when starting with functional programming is ADTs. But what are they and why do we care so much for them in FP?

ADT stands for Algebraic Data Types. They allow the definition of complex data types. If you come from object-oriented programming, the closest equivalent are classes, and in Scala they look almost the same.

Defining ADTs

Let’s start with the basics: the definition. We define an ADT by declaring its name and its variants. Variants might be parametrized . Let us consider a basic ADT where the variants don’t have parameters.

enum MyBoolean: // declare name
	case True     // constant variant
	case False		// constant variant

You might think that I just tricked you, as this seems like a standard enumeration that you can find in Java or any other language. However, enum, in Scala 3, is just syntax sugar (which we will explore later). You can implement the same thing with a Java enumeration, but this is more complex.

Now, let’s explore a more sophisticated example. This time, one variant has a parameter:

enum Nat:
	case Zero
	case Suc(s: Nat) // parametrized variant

This ADT is the classic Peano encoding of natural numbers. Indeed, using this ADT, we can represent any natural number, for example:

import Nat.*
val zero: Nat = Zero
val one = Suc(Zero)
val five = Suc(Suc(Suc(Suc(Suc(Zero)))))

The ADT above shows another noteworthy feature of ADTs, you can make them recursive. ADTs can also have a type parameter. This enables to use ADT to model recursive structures such as lists, trees, etc. For example, to define a simple list, we can do:

enum MyList[+A]: // A is a type parameter
	case MyNil
	case MyCons(h: A, tail: MyList[A])

The A is preceded by a + operator. This is Scala’s way of declaring a covariant data type. This means that if we have B a subtype of A, then MyList[B] is a subtype of MyList[A]. Now, you can build elements of the list using the generators. For example:

import MyList.*
val emptyList = MyNil
val oneEltList = MyCons(5, MyNil)

The possibilities are indeed endless. The compiler infers the type parameter (in this case, Int), thus making the expression compact and uncluttered.

You can also use ADTs to encode standard business logic that you would normally encode in classes, for example:

enum Amount(amount: Double):
	case USD(amount: Double) extends Amount(amount)
	case EURO(amount: Double) extends Amount(amount)

enum Quantity(quantity: Int):
	case Boxes(quantity: Int) extends Quantity(quantity)
	case Units(quantity: Int) extends Quantity(quantity)

enum Product:
	case ConcreteProduct(code: String, description: String, price: Amount, q: Quantity) // there is a better way to do this, to be shown later

This example highlights another feature of ADTs: they can be parametrized. The extends is only necessary because we are setting a parameter of the ADT itself and not of the variant. Let us look at an example of how to use this code.

import Amount.*, Quantity.*, Product.*
val product: ConcreteProduct = ConcreteProduct("123", "My Product", USD(500.00), Units(1))

Until now, we have seen that ADTs can:

  • Encode different variants of the same object (more or less like subclassing)
  • Encode enumerations
  • Encode recursive data structures
  • Encode standard business records

What is the Difference with Classes

Coming from object-oriented programming, you might think that ADTs are more or less a combination of classes and enumerations.

The first and main difference between classes and ADTs is that ADTs are immutable. While objects are stateful, ADTs are stateless. One does not change the internal data of an ADT. If we want to change an ADT, we build it again with the field of data changed. Since this is a common operation, Scala comes with a way to perform this operation efficiently. For example, let’s say that we want to change the price of our product defined above, we would create a new product as with the new price:

val cheaperProduct = product.copy(price = USD(450))

The second difference is that one can extend classes via inheritance. Although the different ADTs that we have seen look like inheritance, and even use the keyword extends, the compiler does not allow them to be extended in the same way that a class might is extended by its clients. In Scala, you can only create new variants of an ADT in the same file that the original ADT was defined, or under the same enum. For normal classes, however, the user can add a new variant even in another program that does not know the source code of the original class. The idea behind this finality is that its definition completely defines an ADT. This allows the compiler to check that any ADT created is always valid and that any function that works with ADTs knows always all the scenarios that it might encounter.

The third difference is that in ADTs all fields are public. ADTs goal is to define a structure not to encapsulate a hidden state. This is important because functions that work on the ADT expect it to be fully known to them.

The fourth difference is methods. You might have noticed that we have defined the ADTs, but no methods. Normal functions define operations on ADTs. In Scala, you can define the functions directly under the ADT enum, or outside of it. This means that adding new operations to an ADT does not require knowing its source code, because all fields are public. You just create a new function in your preferred scope and you are ready to go.

The final difference is that ADTs support pattern matching. Pattern matching is a feature that allows to decompose a variant of an ADT in its constituents. This is done with the match construction in Scala. For example, if we want a function that returns true if a Nat is bigger or equal to two, we can define:

def greaterThanTwo(n: Nat) = n match {
  case Suc(Suc(_)) => true
  case _ => false
}

This function tries to match the structure of the ADT value to the pattern in the case, and if it matches, returns the code on the right side of the => symbol. Since the compiler has complete knowledge of each ADT, it can analyze match expressions and determine if all cases are covered.

How are ADTs Similar to Classes

Scala is a hybrid programming language. It supports classes and they work exactly as you would expect. Indeed, ADT support in Scala is a special type of class, the case class. We can encode our Nat enum using case classes:

sealed trait OtherNat
case object OtherZero extends OtherNat
case class OtherSuc(n: OtherNat) extends OtherNat

Using this syntax, we can define the ConcreteProduct from above in a more compact way:

case class ConcreteProduct(code: String, description: String, price: Amount, q: Quantity)

Indeed, the Scala compiler will translate the different enums above to a representation like the one in OtherNat. As a consequence, these special classes have the same limitations and features we mentioned above:

  • We cannot extend them outside of the definition file (that is what the sealed keyword is for)
  • the fields declared in the constructor immutable
  • they allow to use the copy method

If you explore Scala documentation, you see that we can add methods to our ADTs. This is very practical in certain situations. For example, if you want to create a function that returns the length of a list, you can implement it as a function:

def myLength[A](l: MyList[A]): Int = l match {
  case MyList.MyNil => 0
  case MyList.MyCons(_, tail) => 1 + myLength(tail)
}

Or you can implement it as a method:

enum MyOtherList[+A]:
	def length: Int = 
		this match 
			case MyOtherNil => 0
			case MyOtherCons(_, tail) => 1 + tail.length
	case MyOtherNil
	case MyOtherCons(h: A, tail: MyOtherList[A])

The method implementation can be called as a normal method (using . syntax) and thus is much more elegant:

import MyOtherList.*
val myOtherList = MyOtherCons(1, MyOtherNil)
myOtherList.length

You might have noticed that the myLength and length functions are defined recursively. As ADTs can be recursive data structures, recursive functions are a very common way to perform operations in them.

Which One Should I Use

If you are doing functional programming with Scala you should stick to ADTs and use methods to improve usability of your ADTs. Scala is a very flexible language that gives you the best of both worlds.

ADTs immutability, genericity and enhanced type safety are what make them useful for functional programming and even programming. Since immutability is necessary for functional programming (at least most of the time), ADTs are the go to method to define data in functional programs. Features such as type parameters and pattern matching make programming with ADT a very pleasant experience.

If you have read until here and liked this content please consider subscribing to my mailing list. I write regularly about Blockchain Technology and Scala.

comments powered by Disqus