So how can we match over abstract data types in a more palatable manner?
Active Patterns
Active patterns are the class of recognizers that allow us to pattern match over abstract data types. The key to understanding active patterns is the word active. An active pattern lets us run a computation as part of a pattern match. With only basic patterns we were stuck with this rather ugly piece of code every time we needed to match on our Expr type.
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?”
What we’d really like to do is run the Expr.TryAdd, Expr.TryMul, Expr.TryVar, and Expr.TryConst computations as part of the pattern match itself. So let’s write ourselves a total recognizer that can do precisely that.
let (|Add|Mul|Var|Const|) (e : Expr) =
match Expr.TryAdd e with
| Some (e1,e2) -> Add(e1,e2)
| None ->
match Expr.TryMul e with
| Some (e1,e2) -> Mul(e1,e2)
| None ->
match Expr.TryVar e with
| Some x -> Var(x)
| None ->
match Expr.TryConst e with
| Some n -> Const(n)
| None -> failwith “How did we get here?”
And now our palate is happy.
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
This code is identical to the basic pattern matching code we wrote over our discriminated union. The difference is what happens under the hood.
Active Patterns Exposed
The pattern match over the discriminated union generates the following eval function.
Public Function eval(ByVal env As Dictionary(Of String, Double), ByVal e As Expr) As Double
Dim expr As Expr = e
If TypeOf expr Is _Add Then
Dim e2 As Expr = DirectCast(expr, _Add)._Add2
Dim e1 As Expr = DirectCast(expr, _Add)._Add1
Return (Program.eval(env, e1) + Program.eval(env, e2))
End If
If TypeOf expr Is _Mul Then
Dim e2 As Expr = DirectCast(expr, _Mul)._Mul2
Dim e1 As Expr = DirectCast(expr, _Mul)._Mul1
Return (Program.eval(env, e1) * Program.eval(env, e2))
End If
If TypeOf expr Is _Var Then
Return Program.lookup(DirectCast(expr, _Var)._Var1, env)
End If
Return DirectCast(expr, _Const)._Const1
End Function
So we use guard clauses to match on the type of our expression and do the appropriate logic for that match. If none of our guard clauses match then we return the last option in our match. Now let’s look at the code generated by our “active” eval statement.
Public Shared Function eval(ByVal env As Dictionary(Of String, Double), ByVal e As Expr) As Double
Dim option1 As Option(Of Tuple(Of Expr, Expr)) = Expr.TryAdd(e)
If option1 IsNot Nothing Then
Dim e2 As Expr = option1._Some1.get_Item2
Dim e1 As Expr = option1._Some1.get_Item1
Return (Program2.eval(env, e1) + Program2.eval(env, e2))
End If
Dim option2 As Option(Of Tuple(Of Expr, Expr)) = Expr.TryMul(e)
If option2 IsNot Nothing Then
Dim e2 As Expr = option2._Some1.get_Item2
Dim e1 As Expr = option2._Some1.get_Item1
Return (Program2.eval(env, e1) * Program2.eval(env, e2))
End If
Dim option3 As Option(Of String) = Expr.TryVar(e)
If option3 IsNot Nothing Then
Return Program2.lookup(option3._Some1, env)
End If
Dim option4 As Option(Of Double) = Expr.TryConst(e)
If option4 IsNot Nothing Then
Return option4._Some1
End If
Return Operators.failwith(Of Double)(“How did we get here?”)
End Function
Our “active” eval statement has the TryAdd, TryMul, TryVar, and TryConst computations embedded in it. Our computations really do get run as part of the pattern matching process.
Total Recognizers
Active Patterns that always match on a value, like our example above, are called total recognizers. We’ll take a look a slightly different total recognizer next time to find out what happens when we don’t return an option type from our recognizer.