Pattern Matching for Dummies

The pattern matching syntax of F# will change the way you write code.  Of all the reasons to begin the move from VB to F#, the declarative style of pattern matching is reason number one.  The days of the “nested if” are numbered and blood pressures everywhere can only benefit.

 

There’s a great article from Microsoft Research explaining how pattern matching in F# works.  Let’s do our best to dumb it down for the sub Neanderthal intelligence of the VB Mort :)  Actually, the article is very accessible compared to most Microsoft research articles.

 

Matching Over Concrete Data Types

 

Discriminated unions in F# are a handy concrete data type for modeling a set of choices. Each choice isn the union is called a discriminator.  Each discriminator can be used like a constructor for building values.  The key feature of discriminated unions is the ability to build a view of our values separate from their underlying types.   Let’s have a look at the example from the paper above.

 

type Expr =

    | Add of expr * expr

    | Mul of expr * expr

    | Var of string

    | Const of float

 

let variable = Var(“x”)

let constant = Const(1.0)

let e = Add(variable, constant)

 

So we’ve used each of our discriminators to construct ourselves different types of expressions.  And although each expression was built from a different underlying type, we can now view each of them as related expressions.  This allows us to pattern match on each our expressions in order to deconstruct them.

 

let rec eval env e =

    match e with

    | Add (e1,e2) -> eval env e1 + eval env e2

    | Mul (e1,e2) -> eval env e1 * eval env e2,

    | Var x -> lookup x env

    | Const n -> n

 

The evaluator for our expression becomes an easy to read declarative function.  Each of our expressions can now be evaluated by our eval function despite their underlying types being different.

 

let resultv = eval env variable

let resultc = eval env constant

let result = eval env e

printfn “%A” resultv

printfn “%A” resultc

printfn “%A” result

 

If you can’t figure out what env is then I’m right there with you.  The env variable had me confused when reading the paper, so let’s make our “environment” more concrete.

 

let env = new Dictionary<string, float>()

env.Add(“x”, 25.0)

let lookup var (env : Dictionary<string, float>) =

    let mutable res = 0.0

    let foundIt = env.TryGetValue(var, &res)

    if foundIt then res

    else failwithf “Didn’t find %s” var

 

Basically, the environment is a dictionary for storing and looking up our variables.  Discriminated unions are great for creating higher level views of our underlying types.  Our low level types can be constructed as higher level views then deconstructed using pattern matching back into their low level types.  Discriminated unions are invaluable for domain specific languages and logic programming, but they really are so much more.  A higher level view of low level types is a powerful concept.

 

Discriminated Unions Exposed

 

We’re diverging from the paper slightly, but any curious .Net programmer wants to see how discriminated unions are implemented under the covers.  Our expression type gets turned into a mustinherit base class.  I purposefully don’t use the word abstract here since it confuses the idea of an abstract data type in the next section.

 

Public MustInherit Class Expr

    Public Shared Function Add(ByVal Add1 As Expr, ByVal Add2 As Expr) As Expr

    Public Shared Function [Const](ByVal Const1 As Double) As Expr

    Public Shared Function Mul(ByVal Mul1 As Expr, ByVal Mul2 As Expr) As Expr

    Public Shared Function Var(ByVal Var1 As String) As Expr

    Public Function IsAdd() As Boolean

    Public Function IsConst() As Boolean

    Public Function IsMul() As Boolean

    Public Function IsVar() As Boolean

 

I’ve removed the gunk and left just the essence of what the F# compiler is doing.  The Expr class has two types of functions.  The Add, Const, Mul, and Var functions construct our expressions from the underlying types. The IsAdd, IsConst, IsMul, and IsVar functions do the matching portion of the deconstruction work.  The rest is left to our discriminators, which store the underlying types.

 

Public Class _Add

    Inherits Expr

    Public Sub New(ByVal _Add1 As Expr, ByVal _Add2 As Expr)

    Public ReadOnly _Add1 As Expr

    Public ReadOnly _Add2 As Expr

End Class

 

Public Class _Const

    Inherits Expr

    Public Sub New(ByVal _Const1 As Double)

    Public ReadOnly _Const1 As Double

End Class

 

Public Class _Mul

    Inherits Expr

    Public Sub New(ByVal _Mul1 As Expr, ByVal _Mul2 As Expr)

    Public ReadOnly _Mul1 As Expr

    Public ReadOnly _Mul2 As Expr

End Class

 

Public Class _Var

    Inherits Expr

    Public Sub New(ByVal _Var1 As String)

    Public ReadOnly _Var1 As String

End Class

 

So our discriminated union uses subtypes to store the discriminator specific underlying types, and relates these types by inheriting from a common base class.  Pretty nifty trick!

 

Matching Over Abstract Data Types

 

After a brief detour, let’s get back to the paper at hand.  An abstract data type (ADT) has a different connotation in functional languages than abstract/mustinherit classes in C# and VB.  An abstract data type in functional programming is any type that hides its implementation from the user of the type.  An abstract data type could use any underlying concrete type (discriminated union, record, etc) for its implementation, but the user never knows which one.

 

This hiding allows the implementer to change the underlying implementation without breaking all the user code.  Let’s implement our Expr discriminated union as an abstract data type.

 

(* abstract type *)

type Expr =

    internal

    | Add of Expr * Expr

    | Mul of Expr * Expr

    | Var of string

    | Const of float

    static member MakeAdd(exp1,exp2) = Add(exp1,exp2)

    static member MakeMul(exp1,exp2) = Mul(exp1,exp2)

    static member MakeVar(x) = Var x

    static member MakeConst(f) = Const f

    static member TryAdd(exp) =

        match exp with

        | Add(exp1, exp2) -> Some (exp1,exp2)

        | _ -> None

    static member TryMul(exp) =

        match exp with

        | Add(exp1, exp2) -> Some (exp1,exp2)

        | _ -> None

    static member TryVar(exp) =

        match exp with

        | Var x -> Some x

        | _ -> None

    static member TryConst(exp) =

        match exp with

        | Const n -> Some n

        | _ -> None

 

The use of internal in front of the discriminated union hides these constructor types from the user.  This allows us to add new discriminators for internal use only, get rid of old ones, or stop using a discriminated union all together.

 

Of course for our expression to be useful we need to provide member functions for constructing and deconstructing our expressions.  However, now that we’re abstract data type instead of a discriminated union the user can no longer use pattern matching to deconstruct the expressions.  The easy to understand eval function becomes the following mess in the user code.

 

let variable = Expr.MakeVar(“x”)

let constant = Expr.MakeConst(1.0)

let e = Expr.MakeAdd(variable, constant)

 

let rec eval env e =

    match Expr.TryAdd e with

    | Some (e1,e2) -> eval env e1 + eval env e2

    | None ->

    match Expr.TryMul e with

    | Some (e1,e2) -> eval env e1 * eval env e2

    | None ->

    match Expr.TryVar e with

    | Some x -> lookup x env

    | None ->

    match Expr.TryConst e with

    | Some n -> n

    | None -> failwith “How did we get here?”

 

let resultv = eval env variable

let resultc = eval env constant

let result = eval env e

 

It works, but it sure ain’t pretty.  An interesting aspect of this match statement is how the None propagates the check on to the next match statement.  So how can we match on our abstract datatype in a more palatable manner?  We’ll find out next time.