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 …

Advertisements
Posted in Scala. 7 Comments »

7 Responses to “Functional Scala: Algebraic Datatypes – ‘Sum of Products’ Types”

  1. Functional Scala: Algebraic Datatypes - 'Sum of Products' Types Says:

    […] a pure product type in the last two episodes. However, the vast majority of algebraic datatypes… [full post] Mario Gleichmann brain driven development scala 0 0 0 0 […]

  2. Tweets that mention Functional Scala: Algebraic Datatypes – ‘Sum of Products’ Types « brain driven development -- Topsy.com Says:

    […] This post was mentioned on Twitter by Planet Scala, Mario Gleichmann. Mario Gleichmann said: Blogged 3rd part on algebraic datatypes: 'sum of products' – some 'hybrid' datatypes in Action #Functional #Scala http://tinyurl.com/6dtev74 […]

  3. Renato Cavalcanti Says:

    Hi Mario,

    What you are describing here does not differ from what many call value objects. Objects with only data and no behavior.

    I prefer to have my model objects defined as pure value objects or as datatypes and have other classes with behavior (but stateless) that act on the value objects. Does it sounds like datatypes + functions?

    IMO, this way of working have been popularized in the java world mainly because of de facto standards like Spring and Hibernate. It’s much easier to have a Hibernate DAO that saves a value object (or datatype) than to have a save() method in the model itself like proposed by the ActiveRecord pattern. It’s also much cleaner to have a service to which I can pass my model that to inject such a service in my model. For instance, that PrinterService.print(rectangle) instead of Rectangle.print().

    Some will argue that this is not really object oriented and that we should not separate data from behavior and bla, bla, bla. I can’t disagree more. I don’t see the point in having a Rectangle depending on a hibernate session or a printer driver.

    I know that Functional Programming is much more than that and I still have a lot to learn about it. But my feeling is that the java developers do not follow, have never followed, OOP strictly. Fortunately. And that it’s very common to see data and behavior separated.

    Looking forward to read your next post.

    • Mario Gleichmann Says:

      Renato,

      thank you very much for your detailed feedback!

      First of all, i see a distinction between data transfer objects (DTOs) and value objects. While a Data transfer object is really nothing more than a data container, a value object (in the sense of value types, as Eric Evans would call them) may also feature some useful behaviour, based on its nature (for example, a Rectangle could provide a method for asking about his area, while refering to its height and width). This is separated on algebraic datatypes, as they can’t provide any ‘behaviour’ for themselves.

      I’m not really sure wether you refer to DTOs or value objects. In either case, one essential characteristic of an algebraic datatype is it’s immutability. So, in order to compare them with DTOs, an DTO shouldn’t be mutable then (that is no setters on board).
      Further on, with algebraic datatypes you can’t rely on subtype polymorphism, as you *could* with DTOs or value objects: In an OO world, you could define an abstract method getArea() on a base class Shape and have them implemented within the subclasses accordingly. With algebraic datatypes, you abandon that option. Hence, there must be an alternative way to operate on them – which is pattern matching …

      Grettings

      Mario

      • Renato Cavalcanti Says:

        Mario,

        I think I was not very precise when talking about Value Objects. I was certainly not referring to DTO. Maybe it would be better to refer to it as Model instead of VO. Anyway, the similarity I was pointing out is the fact they are data only objects without behavior. But indeed, I was not taking into account that a datatype is immutable. So we may consider them similar, but not equal as I affirmed.

        Regarding subclassing and polymorphism, I believe you are referring to the theory about datatypes or how it works in languages that support it natively.
        In Scala we can do both. Although subclassing a case class gives a deprecation warning. Maybe it’ll become a compilation error in the future, but for the time being it’s still possible.

        Cheers,

        Renato

  4. Mccrosky@gmail.com Says:

    We have been currently fixing an even greater immune of strategy. Might be curious to listen for applying for grants the type of reviews you’d do while using the nestin ally.

  5. Functional Scala: Pattern Matching – the basics « brain driven development Says:

    […] the last episodes, we discovered how to define so called algebraic datatypes. So far, we’ve only implemented […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: