Functional Scala: Algebraic Datatypes – Sum and Product Types

Welcome back to another episode of Functional Scala!

This one is the continuation of the last episode, where we introduced algebraic datatypes. Within this installment we’ll broaden the scope and find a more general definition for algebraic datatypes. Of course we don’t stop with definitions. Since we wanna write code (that’s Scala for, isn’t it?), we’ll see how to implement those extended new forms of algebraic datatypes (we’re going to meet today) within Scala!

Well, for a short recapitulation – and even better, serving as a smooth transition base to our current point of interest –  let’s define a final enumerated data type, tagging again some of the main characteristics of an algebraic datatype. This time, imagine we need to define a new type Color. As with all algebraic datatypes we also need to define the values (the domain, if you like) of that type by defining a bunch of so called value constructors. Nothing easier than that, so let’s do it:

sealed abstract class Color
case object Red extends Color
case object Green extends Color
case object Blue extends Color

Aaahhh, our new type Color consists of three values Red, Green and Blue. Those are mapped to singleton objects (serving as the underlying value constructors), since every value is a unique instance of the type. And just for the records, we can therefore see that Color is a so called sum type, since all values of that type are clearly expressed by the sum of all value constructors.

Well, ok. Is there perhaps some annoyance that might bother you about Color? If not, than your world must really look kind of funny, since there are apparently only three colors within. Of course there are some more colors in the world, but enumerating them all might be a bit to cumbersome! But if you pick the right fortune cookie, you might get hit to another color model, which is called additive color model or just RGB color modell (which is the most prominent representative of an additive color model). I won’t go into the details of that color model, since i guess that you’ve already heard of’em.

Now, how do we go and represent that model as an algebraic datatype, say type RGBColor? Again, enumerating all possible combinations of intensity for all components (that are the primary colors red, green and blue) of a certain color would take us some little amount of time! In that case, we simply extend the idea of an algebraic datatype by allowing to combine existing data types: every value constructor of a certain datatype (like our new type RGBColor we’re going to define now) might carry (or nest) some values of some other datatypes. In our case, there might be three nested values of type Int, each one representing the intensity for one of the primary colors:

sealed abstract class RGBColor
case class RGB( red :Int, green :Int, blue :Int ) extends RGBColor

For this to work, a value constructor need to be defined in a more generic way. We can’t no longer define some singleton objects, since they only would represent one single value of a type each. Instead we defined our value constructor RGB as a case class, allowing to produce an arbitrary amount of color values by giving some concrete values for the nested intensity fields:

val black = RGB( 0, 0, 0 )
val white = RGB( 255, 255, 255 )
val red = RGB( 255, 0, 0 )
val hotPink = RGB( 255, 105, 180 )
val purple = RGB( 160, 32, 240 )
...

Aaahh, oohh, that looks pretty much the same like normal object instantiation in an object oriented way. And in fact it is, since Scala provides a blendet world which tries to fuse both paradigms (now go and count how many times i’ve already said that and win a … magic number). And since we’re working with ordinary classes and require only one class for the one and only value constructor RGB, we could cheat in our OO-functional world and use exactly that class as a type and produce some instances of that type, too. In this case, we could get rid of the abstract base class:

sealed case class RGBColor( red :Int, green :Int, blue :Int )

Ok, that was nice and simple! Pretty much like working with normal classes in an OO world! Yep, that’s true. But there’s one big difference here! While normal (OO) classes typically also hold some behaviour (which may execute on the given fields), an algebraic datatype is – guess what – a pure data type. An algebraic datatype only wraps some values from other datatypes in some or all of its value constructors, but the value constructor doesn’t execute on that values (it simply holds that values, if you will). And as we said before, those wrapped values can be unwrapped and operated on by using a very powerful mechanism called pattern matching, which enables us to deconstruct a value constructor (the next big thing, we’re looking at).

Now that we’ve seen RGBColor, we also encountered what’s called a product type. In that case, we can’t sum up every single value of the given type, simply by enumerating value constructors (while each value constructor’s representing a single value). This time, all values of that type are expressed as the ‘product’  of all different combinations for those three intensity fields within the parameter list of our value constructor! So the constructors parameters can be seen as the single factors of that product.

Summary

Up to now, we’ve only seen some examples for sum types (Bool, Season, Color) and a product type (RGBColor) in it’s purest form each. While a sum type will provide an individual value constructor for each and every value of that type (in its purest form), a product type will offer a value constructor which will stand for a potential set of different values. The potential set of values, which can be constructed is only limited by the combination of possible values for all fields (or constructor parameters) of that value constructor (you can see it as a kind of cartesian product).

We saw that a pure sum type was rather inappropriate for type Color, therefore we transformed it into a pure product type RGBColor. Within that transformation, we switched from case objects (which represents a separate value constructor for a single value of a given type) to case classes (which represents a whole bulk of potential values), offering some constructor parameters for those individual intensity values  for the underlying primary colors (based on the underlying additive color model).

Of course there are also some hybrid types possible. There, we speak of algebraic datatypes which feature more than one value constructor (sum), while some (or all) of those available value constructors may offer some fields (constructor parameters) for some other datatypes to wrap (product). In fact, the vast majority of algebraic datatypes are expressed as hybrid types and that’s why algebraic datatypes are often described as ‘sum of products types’ (hence algebraic). Those hybrid types will be the main topic for the next episode! So stay tuned …