Functional Scala: Algebraic Datatypes – ‘Sum of Products’ Types

Welcome to another episode of Functional Scala!

We’re not finished yet exploring algebraic datatypes! We’ve already seen some simple sum types and a pure product type in the last two episodes. However, the vast majority of algebraic datatypes constitute a combination of a sum and product type, that’s why they’re happily called ‘sum of products type’. If you’re now wondering what a funny thing such a ‘sum of products type’ might be, or even better – how they could be defined in Scala – don’t worry: in this episode we’re going to see and implement some of these hybrid types, so you’ll getting a good feelin’ for that.

So without any further ado, let’s get our hands dirty and jump right away into a somewhat reasonable example: let’s say we wanna model and represent some different kind of Shapes within our application. And don’t worry, i’m not going to demonstrate some of the oldest known object oriented inheritance pitfalls using shapes, since we’re focusing on algebraic datatypes, which doesn’t feature subtype polymorphism, but only combination (you may wanna think composition) of datatypes.

Let’s start with a single, concrete instance of a shape (lights off, spot on) … a Circle. Ok, a circle! But there isn’t only one circle, right? There exist many circles, all different by their radius. Ahhh, so circle needs to be a product type, just holding a value of another datatype which represents the length of a circle’s radius. Let’s code it:

sealed abstract class Shape
case class Circle( radius : Double ) extends Shape

Unfortunately (or better luckily) there are not only circles, otherwise the world of shapes would be pretty dreary! What about Rectangles? Ahh, sure – we need rectangles! This time, the variety of rectangles might be described by the width and height of a rectangle. Does that mean, that the value constructor for rectangles need some completely other fields than circles? Yep, why not! C’mon, give it a try. Its for free and completely legal:

sealed abstract class Shape
case class Circle( radius : Double ) extends Shape
case class Rectangle( width : Double, height : Double ) extends Shape

And there you have it: a nice, clean example of a ‘sum of products’ type! Um, what? Where? Ok, the range of possible different (read disjointed) sort of shapes is given by the sum of all existing value constructors, that is Circle plus Rectangle. But there isn’t only one unique rectangle (or circle). There’s a whole (infinite) set of rectangles, given by the product for all combinations of width times height. Aaaahhhhh … aye!

Type cosmetics

There might be one little annoyance when looking at the constructor parameters for Rectangle. Both fields are of the same type Double, which might lead to irritation when it comes to value instantiation. If the formal parameter names width and height weren’t chosen carefully (say we named them simply a and b), the intention for those fields might get lost. Even leveraging named parameters wouldn’t help any new reader (read maintainer) of our code, since those names don’t care any semantics:

...
case class Rectangle( a : Double, b : Double ) extends Shape
...
val rectangle = Rectangle( a = 20.0F, b = 1.5F )

Now, is rectangle a flat one or rather a slender one? Your new team mate won’t tell, neither by looking at the instantiation side of rectangle, nor by staring at the type definition for Rectangle. Well, then. We could introduce some naming conventions and point to the importance of picking meaningful names! Right, that’s a good idea even in the functional world! But from there comes also another practice, called type synonyms: You can introduce a synonym for an existing type at any time, in order to give a type a more descriptive name. And hurray to Scala, there’s a way to do those type cosmetics, too! Observe:

type Width = Double
type Height = Double
...
case class Rectangle( w :Width, h :Height ) extends Shape

Yep, the intention of every single parameter should be much clearer now, just by looking at its new type. We leveraged Scalas keyword type for their introduction. Well, of course Width and Height aren’t full blown types, just some synonyms for existing types, as we said before. And how i’m going to produce some values for those type synonyms? Easy as that, just by refering to the underlying type, since they are only synonyms. You’ve surely perceived that i’ve constantly emphasized the fact of being synonyms? Right so, that’s because the compiler will always work with the underlying type. In consequence, we still can simply pass values of type Double to our value constructor!

case class Rectangle( w :Width, h :Height ) extends Shape
...
val rectangle = Rectangle( 20.0F, 1.5F )

But beware! The same fact of being only type synonyms gives rise to some subtle, misleading deductions to our fellow team mate when it comes to scruffy value instantiations. Watch out:

val width :Width = 20.0F
val height :Height = 1.5F
...
val rectangle = Rectangle( height, width )
...
val anotherRectangle = Rectangle( 10.0F :Height, 5.5F :Width )

Ugh, we just interchanged both values during value instantiation, putting them to the wrong parameter position, where exactly the other type sysnonym is expected.  And the best – the compiler won’t complain, since it only checks the underlying type Double, which is ok for both constructor parameters (no matter the type synonyms they exhibit).

Nested type composition

It seems, a more reliable way for ensuring clearness at type level is to introduce another type instead of a type synonym. For that, erase all datatypes you’ve seen in this post so far (mentally) and imagine we’ve needed shapes which also feature a position for displaying them on a 2-dimensional area. Conversant in modeling algebraic datatypes, let’s introduce two more fields (one for the x and the other for the y-position) for each of our value constructors:

sealed abstract class Shape
case class Circle( x :Int, y :Int, radius : Double ) extends Shape
case class Rectangle( x :Int, y :Int, width :Width, height :Height ) extends Shape

Taking another closer look at our value constructors, you may ask if those two new fields may suffer from the same symptoms of carrying too few semantics. Well, if you haven’t wondered yourself, then let me ask that question. Does those two fields relate to each other? If yes, in which way are they associated? Of course are they related! I know, you know, but think again about your poor team mate. C’mon, clearly they state a point in a 2-D area! Well, then why not give a point the right to live as an own algebraic datatype … and your team mate a chance to recognize the concept of a Point:

case class Point( x :Int, y :Int )

We should have no pain to identify Point as a pure product type. It features the same characteristics as type RGBColor from our last installment. Ok, now that we’ve related those two values and giving them a clear semantic conture by introducing an own datatype, we can simply compose those datatypes.

...
case class Circle( center : Point, radius : Double ) extends Shape
case class Rectangle( leftTopAngle : Point, width :Width, height :Height ) extends Shape

See how Point nicely fits into our value constructors? We’re able to assign a single meaningful name to the affected constructor parameter  and in addition to that, you can’t lose but only put a value of the right type in there, when it comes to value instantiation. And in fact, it needn’t stop here. You could nest as many datatypes as you want! The question is now, how to operate on those datatypes, unveiling their nested values …

Summary

Wow, another journey behind us! With Shape we discovered a truly so called ‘sum of products’ type and grasped why they’re named this way: the possible range for all values of such type is given by the  sum of all existing value constructors (remember ‘Circle plus Rectangle’) while each single value constructor might stand for a (possibly infinite) set of representations for that concrete sort, given by the product for all combinations of their constructor parameters (remember Rectangles ‘width times height’).

In addition to that, we somewhat paid attention on how to create more readable code on a type level, just by introducing type synonyms. We saw that they come with some chances by masking types with a more descriptive name. But we also saw some obstacles while the compiler only checks for the underlying, masked type.

Finally, we saw that there’s no restriction in composing given datatypes, that is using existing datatypes as components for other datatypes. In this sense, we’re free to nest as many datatypes as we want as deeply as we want them to have (of course it’s another questions if that’s a really good idea). That way, it’s also possible to compose types in a recursive way (as we’ll see soon).

By now, the most urgent question is how to operate on those datatypes. We need a way to deal with them, esp. if they are nested. Not only talking about readability, having a bunch of nested if-else if-else expressions might not be the best way to handle them. That said, our next focus will be on pattern matching, a directly linked mechanism for writing tidy, regular functions which act on algebraic datytpes (before we return a last time to algebraic datatypes and do a last investigation due to their options on parametric polymorphism). We’ll see pattern matching as a powerfull way to deconstruct any given value of an algebraic datatype and working over their component values in an easy, well-regulated way. So hope to see you next time again …