Kerflyn's Blog

Well… It's a blog!

Playing with Scala’s pattern matching

with 20 comments

How many times have you been stuck in your frustration because you were unable to use strings as entries in switch-case statements. Such an ability would be really useful for example to analyze the arguments of your application or to parse a file, or any content of a string. Meanwhile, you have to write a series of if-else-if statements (and this is annoying). Another solution is to use a hash map, where the keys are those strings and values are the associated reified processes, for example a Runnable or a Callable in Java (but this is not really natural, long to develop, and boring too).

If a switch-case statement that accepts strings as entries would be a revolution for you, the Scala’s pattern matching says that this is not enough! Indeed, there are other cases where a series of if-else-if statements would be generously transformed into a look-alike switch-case statement. For example, it would be really nice to simplify a series of instanceof and cast included in if-else-if to execute the good process according to the type of a parameter.

In this post, we see the power of the Scala’s pattern matching in different use cases.

Notice that the pattern matching is not something new. It is something that appears already in some other languages like OCaml, Haskell. A kind of pattern matching also exits in Prolog, but it uses a far different mechanism (unification in this case).

Traditional approach

There is an approach to the Scala’s pattern matching that looks similar to the switch-case structure in C and Java: each case entry use an integer or any scalar type. Here is an example:

def toYesOrNo(choice: Int): String = choice match {
    case 1 => "yes"
    case 0 => "no"
    case _ => "error"
  }

So if  you enter toYesOrNo(1), Scala says “yes”. And if you enter toYesOrNo(2), Scala says “error”. Notice that the symbol _ is used to formulate the default case.You also have to remark that there is no need to use the break statement.

But if you want that Scala says “yes” when you enter toYesOrNo(1), toYesOrNo(2), or toYesOrNo(3), you will write the function like this:

def toYesOrNo(choice: Int): String = choice match {
    case 1 | 2 | 3 => "yes"
    case 0 => "no"
    case _ => "error"
  }

Now, you can use a string for each case entry. Using strings is interesting when you want to parse options of your applications:

def parseArgument(arg: String) = arg match {
    case "-h" | "--help" => displayHelp
    case "-v" | "--version" => displayVerion
    case whatever => unknownArgument(whatever)
  }

So if you enter parseArgument(“-h”) or parseArgument(“–help”), Scala calls the displayHelp function. And if you enter parseArgument(“huh?”), Scala calls unknownArgument(“huh?”).

Notice that I have not used _ for the default case. Instead, I have put an identifier as its value is used in the associated instruction.

Typed pattern

Sometimes in Java, you have to deal with an instance of something that appears like an Object or any high level classes or interfaces. After checking for nullity, you have to use series of if-else statements and instanceof-cast to check the class or the interface that the instance extends or implements, before using it and processing the instance correctly. This the case when you have to override the equals() method in Java. Here is the way Scala sees the thing:

def f(x: Any): String = x match {
    case i:Int => "integer: " + i
    case _:Double => "a double"
    case s:String => "I want to say " + s
  }
  • f(1) → “integer: 1″
  • f(1.0) → “a double”
  • f(“hello”) → “I want to say hello”

Is not it better than a succession of if+instanceof+cast?

This kind of pattern matching is useful to walk through a structure using the composite design pattern. For example, you can use it to explore the DOM of an XML document or the object model of a JSON message.

Functional approach to pattern matching

A side effect of such a matching is that it provides an alternative way to design functions. For example, consider the factorial function. If you choose the recursive version, usually, you would define it like this:

def fact(n: Int): Int =
    if (n == 0) 1
    else n * fact(n - 1)

But you can use Scala’s pattern matching in this case:

def fact(n: Int): Int = n match {
    case 0 => 1
    case n => n * fact(n - 1)
  }

Notice the use of the variable n in this case. It is matched with any value that does not appears in the preceding cases. You have to understand that the n in the last case is not the same as the one used in the function signature. If you wanted to use the parameter n and not a new variable with the same name, you have to delimit the variable name with back-quote in the case definition, like this: `n`

Here is a simple way to build you factorial function in Scala:

def fact(n) = (1 to n).foldLeft(1) { _ * _ }

Pattern matching and collection: the look-alike approach

Pattern matching may be applied to the collections. Below is a function that computes the length of a list without pattern matching:

def length[A](list : List[A]) : Int = {
    if (list.isEmpty) 0
    else 1 + length(list.tail)
  }

Here is the same function with pattern matching:

def length[A](list : List[A]) : Int = list match {
    case _ :: tail => 1 + length(tail)
    case Nil => 0
  }

In this function, there are two cases. The last one checks if the list is empty with the Nil value. The first one checks if there is at least one element is the list. The notation _ :: tail should be understood “a list with whatever head followed by a tail”. Here the tail can be Nil (ie. empty list) or a non-empty list.

To go further, we will use this approach with tuples in order to improve our method parserArgument() above:

  def parseArgument(arg : String, value: Any) = (arg, value) match {
    case ("-l", lang) => setLanguageTo(lang)
    case ("-o" | "--optim", n : Int) if ((0 < n) && (n <= 5)) => setOptimizationLevelTo(n)
    case ("-o" | "--optim", badLevel) => badOptimizationLevel(badLevel)
    case ("-h" | "--help", null) => displayHelp()
    case bad => badArgument(bad)
  }

Notice first the use of the operator | that allows to match alternative forms of arg inside the tuple. Notice also the use of two patterns for options -o and --optim. These patterns are distinguished by the use of a guard condition. The guard conditions help you to get fine tuned pattern matching when pattern matching alone is not enough.

Advanced pattern matching: case class

Case classes are classes with part of their behavior predefined in order to make easier their construction and their use in a pattern. Case classes enables you to manipulate parameterized symbols for example, parsed by a compiler or used by your internal Domain Specific Language (DSL).

The example below shows how to use case classes and pattern matching in order to build simple mathematical expressions, evaluate them, and compute their derivative. First, lets define the symbol to represent expressions: the variable X, constants, addition, multiplication, and the negative operator (for the fun!). Here sealed means that there is no other children of the class Expression outside of the namespace.

  sealed abstract class Expression
  case class X() extends Expression
  case class Const(value : Int) extends Expression
  case class Add(left : Expression, right : Expression) extends Expression
  case class Mult(left : Expression, right : Expression) extends Expression
  case class Neg(expr : Expression) extends Expression

Now, lets define a function to evaluate expressions with a given value for the variable by using pattern matching.

  def eval(expression : Expression, xValue : Int) : Int = expression match {
    case X() => xValue
    case Const(cst) => cst
    case Add(left, right) => eval(left, xValue) + eval(right, xValue)
    case Mult(left, right) => eval(left, xValue) * eval(right, xValue)
    case Neg(expr) => - eval(expr, xValue)
  }

Lets try the eval() function:

val expr = Add(Const(1), Mult(Const(2), Mult(X(), X())))  // 1 + 2 * X*X
assert(eval(expr, 3) == 19)

Now, we define a function that compute the (unreduced) derivative of an expression:

  def deriv(expression : Expression) : Expression = expression match {
    case X() => Const(1)
    case Const(_) => Const(0)
    case Add(left, right) => Add(deriv(left), deriv(right))
    case Mult(left, right) => Add(Mult(deriv(left), right), Mult(left, deriv(right)))
    case Neg(expr) => Neg(deriv(expr))
  }

Lets try the deriv() function:

val df = deriv(expr)

Here is what you get in df:

Add(Const(0),Add(Mult(Const(0),Mult(X(),X())),Mult(Const(2),Add(Mult(Const(1),X()),Mult(X(),Const(1))))))
// = 0 + (0 * X*X + 2 * (1*X + X*1)) = 4 * X
assert(eval(df, 3), 12)

Other advanced pattern matching features

There are some special notations used in the Scala’s pattern matching. Scala allows to put aliases on patterns or on parts of a pattern. The alias is put before the part of the pattern, separated by @. For example, in the expression address @ Address(_, _, "Paris", "France"), we want any addresses in Paris/France, but we do not care about its content after the match is done. So after, we just use the alias address.

There is also a specific notation to match sequences with _*. It matches zero, one or more elements in a sequence to its end.

In Scala, pattern matching does not appears only after a the function match. You can put pattern matching in any closure and also in a catch block.

You can provide your own behavior for pattern matching. This is called extractor. To do so, you have to provide your own implementation of the unapply() method (and/or unapplySeq() for a sequence).

Conclusion

In this post, we have seen different ways to use the pattern matching with Scala. The main advantage of such a feature is to provide an easy way to build alternative structures based the matching of scalar values, strings, collections, but also types and parameterized symbols. For me, pattern matching is one of the sexiest alternatives to if statements! A good use of pattern matching can make your program really readable and helps you to build an internal DSL.

About these ads

Written by fsarradin

2011/02/14 at 18:52

Posted in Programming

Tagged with , ,

20 Responses

Subscribe to comments with RSS.

  1. [...] Playing with Scala’s pattern matching [...]

  2. Great post ! Thanks for sharing !

    Mike

    2011/02/24 at 04:17

  3. Thank you for your post, for reminding me of cool features of scala.

    Hans

    2011/10/10 at 14:29

  4. [...] case classes is to provide a way to practice symbolic computation — in my post named Playing with Scala’s pattern matching, read the section Advanced pattern matching: case [...]

  5. [...] article est une traduction libre, faite avec l’autorisation de l’auteur, de « Playing with Scala’s pattern matching » publié par François Sarradin le 14/02/2011 sur [...]

  6. Sad. Doesn’t seem possible to do something like

    case class A (s : String)
    def f (A(s) : A) = s

    whereas you can do the following in OCaml:

    type t = A of string
    let f (A s) = s

    Simply syntactic sugar and AST manipulation. Wondering why that kind of pattern-matching is left out of Scala.

    Guillaume Yziquel

    2012/03/21 at 14:14

  7. [...] designed by a single person have a much better design philosophy which ultimately gets reflected in its minute [...]

  8. [...] Scala (here is an post in this blog showing the different usages of the pattern matching in Scala: Playing with Scala’s pattern matching). In Java, what is almost closed to pattern matching is named switch-case. But, you’re [...]

  9. [...] match,这里有几个基本的用法,下面是一个高级一些的例子,这得到了一个 compile-time [...]

  10. I am just trying out your tutorial:
    In regards to the first snippet of code:

    def toYesOrNo(choice: Int): String = choice match {
    case 1 => “yes”
    case 0 => “no”
    case _ => “error”
    }

    —-
    Did you actually mean:
    def toYesOrNo(choice: Int): String = choice match {
    case 1 => “yes”
    println(“yes”)
    case 0 => “no”
    println(“no”)
    case _ => “error”
    println(“error”)
    }

    Thanks

    ilango

    2012/10/16 at 22:47

  11. A clarification. You mentioned: “So if you enter toYesOrNo(1), Scala says ”yes”
    Being new to Scala I assumed that the case statement also takes care of printing what the user wants to see, in this case being “yes”.. But on trying out your statement, I found that Scala does not print “yes” and had to add a println.
    I also simply changed the code to read:
    def toYesOrNo(choice: Int): String = choice match {
    case 1 => println(“yes”)
    case 0 => println(“no”)
    case _ => println(“error”)
    }

    and Scala returned what I wanted to see.

    ilango

    2012/10/16 at 23:05

    • 1/ your implementation produces a compilation error (what is “return” by println is not compatible with String)
      2/ you can use println on what is returned by toYesOrNo
      3/ if you try toYesOrNo in the Scala REPL, it will display the answer

      fsarradin

      2012/10/16 at 23:27

      • Thanks for your reply. I was running it as an application in Eclipse. I ran your code in the REPL after you asked me to and yes, it ran with no problems.

        ilango

        2012/10/16 at 23:36

  12. I have been learning pattern-matching based on your blog. After that, I wrote my own code
    So, how would you interpret the following case statement that I wrote myself. This works. It is used inside a higher-order function, but I still can’t interpret it very well.

    def occurrences(chrList: List[Char], pairs: List[(Char, Int)]): List[(Char, Int)] = chrList match {
    case (ch :: charList) => occurrences(chList.filter(_ != ch), pairs :+ (ch, 1 + chList.count(_ == ch)))


    }
    My problem is, I can’t seem to understand how ch is getting its values in the expression on the right. Thanks for your time.

    ilango

    2012/10/19 at 17:48

    • chrList looks like List(c1, c2, …, cn). This is the same as c1 :: (c2 :: (… :: (cn :: Nil)…)). Where :: is an operator that takes an element on the right side and a List on the left side. Scala tries to match it with ch :: charList. In such a pattern, ch is matched with the first element of chrList and charList is matched with the rest of chrList.

      If you want more precise answers on this subject, I suggest that you the book “Programming in Scala” by M. Odersky et al. (http://www.artima.com/shop/programming_in_scala_2ed), or ask your questions on a Scala mailing list, or even that you get to http://stackoverflow.com/.

      fsarradin

      2012/10/24 at 21:36

  13. [...] One of the features I miss in Ruby after coding in scala is Pattern Matching. [...]

  14. […] Playing with Scala's Pattern Matching […]


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

Follow

Get every new post delivered to your Inbox.

Join 507 other followers

%d bloggers like this: