Functional Scala: Pattern Matching on product types

Welcome to another episode of Functional Scala!

This time, we’ll finally discover how to pattern match on product types. Within the last episodes we saw how to use pattern matching on some rather simple sum types. The one question left is how to use pattern matching and therein refer to the single components of a given value constructor for a product type.

So let’s start right away with a little warm-up and revisit our well known product type Shape. To make things a bit more interesting, let’s add Triangle (considered right-angled for simplicity sake) as another value constructor. Here it comes:

slealed abstract class Shape
case class Circle( radius : Double ) extends Shape
case class Rectangle( width : Double, height : Double ) extends Shape
case class Triangle( base : Double, height : Double ) extends Shape

Ok, ok, nothing new so far. Now, let’s define a new function which returns the area for any given value of a Shape. Ring, Ring – is there a way of applying pattern matching? Of course! We could give a separate case expression for every individual Shape. So let’s match against the different value constructors, like we did before with sum types! Uhm, err, but what about the fields? No matter – as we said, let’s simply match against the value constructors. As soon as they offer some fields, we only need to mimic those within our pattern: if we wanna refer to them afterwards, we can simply bind them by providing a free variable name on the right position within our value constructor pattern. Observe:

import sala.Math.{Pi,pow}

val area : Shape => Double
    =  _ match {
    case Circle( radius ) => Pi * ( pow( radius, 2.0 ) )
    case Rectangle( width, height ) => width * height
    case Triangle( base, height ) => height * base / 2
}

Ah, ok now things gettin’ clearer, right? We simply applied some variable names for every single field within our individual value constructors, se we refer to them afterwards on the right side of each case expression for calculating the right area. See that variable radius within the first case expression for matching against circles. This one is a free variable name and only accidentally named after the same name used within the original value constructor. You could use whatever (free) variable name you want, as long as they start with a lower case (that’s the sign for Scala to bind the fields value from the actual Shape instance to that variable).

Of course you’re not forced to always bind your fields to a variable. Say we wanna add some optimization and directly return the height of a Rectangle, if the width is 1 (and vice verca). There, we could simply add another case expression just before our common case for Rectangles (otherwise we would always match against the common case):

...
case Rectangle( 1, height ) => height
case Rectangle( width, 1 ) => width
case Rectangle( width, height => width * height
...

See that we’re also allowed to match single fields of a certain value constructor against a constant value. And what about our friend, the underscore? It’s of course valid syntax to place them at the position of arbitrary fields. Now guess its meaning – again, we apply the underscore if we simply don’t care about the fields value. If we wanna give an own case expression for the more or less unlikely case of a Triangle with a base of zero, we wouldn’t be interested about the value of its height at all. Check it out:

...
case Triangle( 0, _ ) | Triangle( _, 0 ) => 0
case Triangle( base, height ) => height * base * 2
...

Nothing to be scared! We just said that if the first or second field is of value 0, then we dont care about the companion field (by placing an underscore at its position)  because the whole case expression evaluates to zero anyway.

A little brick world

Let’s just concentrate on rectangles for the rest of this episode and create some more functions to play with them. Say we wanna use them to build a little brick world where you can topple or stack them. For a first glance, let’s write a function which takes a rectangle and returns another rectangle where width and height is just switched. Experts that we are now, easy as it can be:

val switch : Rectangle => Rectangle
    =  _ match {
    case Rectangle( w, h ) => Rectangle( h, w )
}

A tiny little Function. It does nothing more then using pattern matching to kind of unwrap the components of that product types value constructor. Now you see why pattern matching is sometimes named as deconstruction: a value constructor (like Rectangle) constructs a new value from some given values for its individual components (that is the fields for width and height) while pattern matching deconstructs that value again and kind of unveils the individual components.

Now imagine we wanna stack two rectangles. The result might be another, new Shape called Stack (i know, it’s no real Shape, but think it’s for the sake of easy continuation for this episode). So let’s just add it:

...
case class Stack( top :Rectangle, bottom :Rectangle ) extends Shape
...
val myStack = Stack( Rectangle( 5, 10 ), Rectangle( 7, 12 ) )

Ok, so with this new Shape on board, we could build some new stacks simply by taking two rectangles and use our new value constructor. Let’s say we want to make our stacks a little more robust by trying to pile them in a more controlled way: whenever two sides of a rectangle are of the same length, we use those sides to stack them. Means that we may switch a given rectangle if the length of its height corresponds with the length of the companions width and vice verca!

A Guard for stacking

So far so good! But how can we pattern match under regard of some conditions? Of course we could do some kind of case analysis on the right side of an case expression which may lead to nested pattern matching. You may try it and judge for yourself if such functions remain well structured and readable. Fortunately pattern matching offers something called Guards, which is nothing more (but also nothing less) as a kind of Predicate which also need to be fulfilled in order to have a valid match. In Scala, a guard is simply a boolean expression, preceded by keyword if. Just watch:

val stack : ( Rectangle, Rectangle ) => Stack
    =
    ( r1 : Rectangle, r2 : Rectangle ) => ( r1, r2 ) match {
        case( Rectangle( w1,_ ), Rectangle( w2,_ ) ) if w1 == w2 => Stack( r1, r2 )
        case( Rectangle( w1,_ ), Rectangle( _,h2 ) ) if w1 == h2 => stack( r1, switch( r2 ) )
        case( Rectangle( _,h1 ), Rectangle( w2,_ ) ) if h1 == w2 => stack( switch( r1 ), r2 )
	case _ => Stack( r1, r2 )
}

As you can see, we just added a guard to our pattern. As soon as the basic pattern matches, the guard is evaluated. If the guard results to true, we have a final  match, If the guard results to false, we haven’t a match and pattern matching will continue with the next case expression.

Summary

This time, we just saw that pattern matching on product types is not more complicated than we already saw with sum types. The only additional feature is to provide some meaningful expressions for a product types components (that are the fields of a given value constructor.)

As we saw, we could simply put a new variable at the position of a field, which binds the fields current value to that variable (so we can use it at the right side of the case expression). This way we can deconstruct a value of a given product type back into its individual parts. If we’re not interested in some of those parts we simply use the almighty underscore (again) at those positions.

Another way of pattern match was to just apply constant values for some or all components of a product type. This way we could match against some individual cases were we’re just fixing some components. We used that in order to fish for some special cases which needed some special treatment (e.g. for the sake of performance).

Finally, we saw a first simple use case for guards. As we’ll see, this is a very powerful mechanism to incorporate some conditions into our patterns. With guards we can not only match against a static pattern, but also put some additional dynamic relations to a pattern, which can’t be directly expressed by only looking at a types fields. We will make some more use of guards in the next episode, where we’ll discover some recursive defined datatypes and tryin’ to pattern match against. In addition to that, we’ll see some yet undiscovered techniques offered by Scalas pattern matching mechanism, which will even inrease its range of application. Stay tuned …

Advertisements

15 Responses to “Functional Scala: Pattern Matching on product types”

  1. Functional Scala: Pattern Matching on product types Says:

    […] saw how to use pattern matching on some rather simple sum types. The one question left is how to… [full post] Mario Gleichmann brain driven development generalscala 0 0 0 […]

  2. Steve Says:

    Polymorphism is a much more flexible and more powerful solution than this switch based approach.

    It’s a lesson we learned in the 90’s…

    • Mario Gleichmann Says:

      Steve,

      there are different types of polymorphism.

      While you are referring to inclusion polymorphism (also called subtype polymorphism), there isn’t such a thing in a pure functional environment, since there aren’t any ‘objects’ featuring state and behaviour (so there isn’t any possibility to ‘replace conditionals with polymorphism’) …

      It seems that i have to kind of apologize, since it looks like i have failed to explain the relation between algebraic datatypes for value construction and pattern matching for value deconstruction (when i first encountered pattern matching, i also saw it as a switch on steroids).

      For there are far more skilled people out there explaining the essentials of pattern matching, i strongly recommend to read chapter 4 ‘Structured types and the semantics of pattern matching’ from the book ‘The Implementation of Functional Programming Languages’ by Simon Peyton Jones (together with the great Philip Wadler).

      You can find diverse formats for download the book and studying the ideas behind under
      http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/index.htm

      Thanks and greetings

      Mario

      • Steve Says:

        Mario,

        I mentioned polymorphism because you’re using Scala, which supports it, and your example shows classes and subclasses.

        Pattern matching still suffers from the same flaws as switch, namely: when you decide you want to add classes to your hierarchy, maintenance becomes a problem.

        And as I already said, polymorphism makes this problem completely disappear.

    • Mario Gleichmann Says:

      Steve,

      thanks again for your critical ruminations!

      Yes, Scala is a hybrid language, supporting both areas. But as the name of this series points out (Functional Scala) and as mentioned in the very first episode, we’re trying to push Scala to its functional limits.

      Again, as said in the very first episode about algebraic datatypes, using case classes is the best way to kind of apply the idea of algebraic datatypes in Scala (you may take a look on chapter 6 from the Scala Tutorial at http://www.scala-lang.org/docu/files/ScalaTutorial.pdf).

      As also said, algebraic datatypes need to be fixed. As soon as you add some more value constructors, pattern matching isn’t exhaustive anymore and you may get into maintenance problems. That may be one of the obstacles when working in a purely functional environment where you have no choice of using subtype polymorphism, right!

      On the other hand, you only picked one side of the medal. If your type hierarchy stays very robust (read fixed) but you frequently need to add some more functionality, maintenance becomes a problem (to speak with your words), since you need to add that new functionality potentially to all of your individual sub types. There’s a design pattern you typically apply in this scenario, which is the visitor pattern. But if you think a little deeper, you’ll see, that the visitor pattern is nothing more than pattern matching!

      Greetings

      Mario

  3. Greg Says:

    I get the pattern matching, but how would I use this, i.e. how would I incorporate ‘area’ into a simple example? Is ‘area’ a property of class Shape or is it to be used external to Shape? (sorry…newbie)

    • Mario Gleichmann Says:

      Greg,

      ‘area’ is a function, which is a first class citizen in the world of functional programming. In fact, in a pure functional world there aren’t such thinks as ‘objects’, carrying data and behaviour (aka methods).

      So as you already said it right, ‘area’ is to be used ‘external’ to shape. But this ‘externality’ (or being a first class citizen as i mentioned above) gives rise to some new (or other) forms of abstractions (you may wanna take a look at the post about higher order functions), composeability and easy (algebraic) reasoning about your programs (as long as your functions stay pure and produce no side effects ‘under the radar’). I tried to clarify these ideas in the first posts about Functional Scala, where i ruminated about the more general, core features and ideas of functional programming. Please feel free to read them and just ask questions if they come along …

      Greetings

      Mario

      • Steve Says:

        Mario,

        You still haven’t answered Greg’s question.

        If you want to illustrate of how powerful functional programming is, I suggest you don’t use an OO based example…

  4. Germán Says:

    I don’t see this as an “OO based example” as Steve points out. This is Algebraic Data Types, a concept that is natural to FP, and not just any OO class hierarchy; and this is how ADTs are expressed in Scala.

  5. Hood Says:

    I dont know what to say. This web site is amazing. Thats not truly a actually substantial statement, but its all I could come up with soon after reading this. You know a great deal about this subject. Much making sure that you produced me wish to understand additional about it. Your web site is my stepping stone, my buddy. Many thanks for that heads up on this theme.

  6. Virtuagirl Says:

    I will add this blog to my favorites, it is great.

  7. Sams Says:

    I am glad to be one of many visitors on this great web site (:, thankyou for putting up.

  8. Functional Scala: List sugarization « brain driven development Says:

    […] but what about deconstructing lists by pattern matching? As you surely remember from some older episodes, pattern matching is one of the main tools for operating on algebraic datatypes. And since […]

  9. Functional Scala – Mario Gleichmann « Another Word For It Says:

    […] Functional Scala: Pattern Matching on product types […]

  10. Functional Scala: Curried Functions and spicy Methods « brain driven development Says:

    […] or radius. Hugh? But how we’re supposed to get those fields then? Well, we could leverage Pattern Matching in order to retrieve a circles components. […]


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: