Tuesday, 18 August 2009

Advantages of Pattern Matching

Following the May 2009 CTP release of F#, this new programming language is finally starting to gain some serious traction. However, many people trying to learn about the advantages and disadvantages of F# are being misled by much of the oversimplified journalistic material being made available. We shall endeavour to address this by releasing short articles in the form of blog posts that augment the common information with valuable insights.

Perhaps the most common misconception is that functional programming is the primary advantage of the F# programming language over alternatives like C#. This is misleading for two main reasons. Firstly, the latest C# 3.0 version provides extensive support for funtional programming including lambda functions and the .NET 3.5 framework is already taking advantage of this with the System.Func and System.Action generic delegates. Secondly, the F# programming language provides a wealth of other valuable features that are as advantageous as functional programming but which are not found in any other mainstream programming languages. Pattern matching over variant types is one such feature.

Grouping code by function rather than class lets you use pattern matching, which is far more powerful and efficient than alternatives such as method dispatch in object-oriented programming:

  • Pattern matches can act upon ints, floats, strings and other types as well as objects. Method dispatch requires an object.
  • Pattern matches can act upon several different values simultaneously: parallel pattern matching. Method dispatch is limited to the single this case in mainstream languages.
  • Patterns can be nested, allowing dispatch over trees of arbitrary depth. Method dispatch is limited to the non-nested case.
  • Or-patterns allow subpatterns to be shared. Method dispatch only allows sharing when methods are from classes that happen to share a base class. Otherwise you must manually factor out the commonality into a separate member (giving it a name) and then manually insert calls from all appropriate places to this superfluous function.
  • Pattern matching provides exhaustiveness and redundancy checking which catches many errors and is particularly useful when types evolve during development. Object orientation provides exhaustiveness checking (interface implementations must implement all members) but not redundancy checking.
  • Non-trivial parallel pattern matches are optimized for you by the F# compiler. Method dispatch does not convey enough information to the compiler's optimizer so comparable performance can only be achieved in other mainstream languages by painstakingly optimizing the decision tree by hand, resulting in unmaintainable code.
  • Active patterns allow you to inject custom dispatch semantics.

Interestingly, although F# is one of the world's first production-quality functional programming language implementations, it still provides features like or-patterns and active patterns that are not available in other academic functional languages such as Haskell.

You can learn all about pattern matching in F# from the F#.NET Journal article "How to Leverage Pattern Matching" (16th April 2007).


Ben said...

Funny looking at that trend - in the cities list, Redmond is way above all the others. Looks like Microsofties are the ones doing most of the searching (with Google as well!)

Anonymous said...

Are you insinuating that pattern matching is not a functional concept? I'm not seeing how FP isn't a huge advantage in F#

Jon Harrop said...

@Ben: Yes, that is interesting. Note that the US does not even appear in the top regions though.

@Anonymous: Pattern matching is not a functional concept. Functional programming is a huge advantage in F# but it is not the only advantage. Type inference is another huge advantage, for example.