Pattern Matching vs Subtype Polymorphism

On May 30, 2013, in Scala, by OleTraveler

This post is an overview of the talk Living in a Post-Functional World by Daniel Spiewak. In ithe talks about The Expression Probmel which is defined as:

  • Define a datatype by case.
  • Add new Cases to the datatype.
  • Add new functions over the datatype
  • Don’t recompile (don’t change any existing code)

There are no clear solution to this problem, but there are different strategies.  In Scala, the options are pattern matching and subtype polymorphism.  Pattern matching allow adding a new function without altering existing codc, but alter existing code when adding new cases.   Whereas subtype polymorphism allows adding new cases without recompiling existing code, however existing code would need to be altered when adding function.

 

For example, here is Daniel’s example using Patter Matching:

 

  
object Pattern {

  sealed trait Expr
  case class Add(e1: Expr, e2: Expr) extends Expr
  case class Sub(e1: Expr, e2: Expr) extends Expr
  case class Num(n: Int) extends Expr

  def value(e: Expr): Int = e match {
    case Add(e1, e2) => value(e1) + value(e2)
    case Sub(e1, e2) => value(e1) - value(e2)
    case Num(n) => n
  }
  val expr = Add(Num(5), Sub(Num(50), Num(13)))

  val result = value(expr) //41
}

Using the above as a codebase, adding a function for pretty printing the expression would not require any of the existing code to be touched. However adding the new algrebaic type Mult would require the value function be modified to match on the Mult type. (Note that the Visitor’s pattern is a poor-mans pattern matching in Object Oriented languages).

Here is Daniel’s example of Subtype Polymorphism.

  
object Subtype {
  sealed trait Expr {
    def value: Int
  }

  case class Add(e1: Expr, e2: Expr) extends Expr {
    def value = e1.value + e2.value
  }

  case class Sub(e1: Expr, e2: Expr) extends Expr {
    def value = e1.value - e2.value
  }

  case class Num(n: Int) extends Expr {
    def value = n
  }
  val expr = Add(Num(5), Sub(Num(50), Num(12)))

  val result = expr.value
}

In order to add a pretty print method, all the case classes would have to be modified. However if we were to add the Multi class, none of the existing case classes would have to be touched.

So, when designing a system that is expected to expand with more cases, use subtype polymorphism, whereas if the system is expected to expand more with functions, use pattern matching.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>