Pattern Matching

Luke Sandell

Nashville F#

10/23/14

What is Pattern Matching?

• Concise syntax for extracting values from data structures (destructuring).
• Mechanism for controlling program flow based on values rather than boolean conditions.
• Allows you to program more declaratively.

Part 1

Match Expressions

Factorial: Defintion

f(0) = 1

f(1) = 1 * 1 = 1

f(2) = 2 * 1 * 1 = 2

f(3) = 3 * 2 * 1 * 1 = 6

f(4) = 4 * 3 * 2 * 1 * 1 = 24

f(5) = 5 * 4 * 3 * 2 * 1 * 1 = 120

...

Factorial: Rercursive Definition

f(0) = 1

f(1) = 1 * f(0) = 1

f(2) = 2 * f(1) = 2

f(3) = 3 * f(2) = 6

f(4) = 4 * f(3) = 24

f(5) = 5 * f(4) = 120

...

f(n) = n * f(n - 1)

Factorial: Without Pattern Matching

1: 
2: 
3: 

let rec fac n =
    if n = 0 then 1
    else n * fac (n - 1)

Factorial: With Pattern Matching

1: 
2: 
3: 
4: 

let rec fac n =
    match n with
    | 0 -> 1
    | _ -> n * fac (n - 1)

Factorial: Improved Validation

1: 
2: 
3: 
4: 
5: 

let rec fac n =
    match n with
    | 0 -> 1
    | _ when n > 0 -> n * fac (n - 1) 
    | _ -> failwith "n must be >= 0"

Glorified Switch Statement?

• Many more types of matching. C# limited to primitive values.
• Pattern matching is used throughout the language, not just match expressions.
• Compiler can check cases for completeness.
• Patterns are composable (nesting).
• When guards allow mixing pattern matching and boolean logic.
• Extensible matching rules via active patterns.

A Tale of Two Type Systems

To understand pattern matching, you must understand the F# type system!

CLR Types

• Basic Types: Primitives, Arrays
• OO Types: Classes, Structs

F# Types

• FP Types: Tuples, Records, Lists, Discriminated Unions
• Immutable by default

FP Types: Tuples and Lists

Tuples

1: 
2: 

1, 2
1, "test", "red"

• Disparate types
• Number and type of elements known at compile time
• Type written as int int, int string * string, etc

Lists

1: 
2: 
3: 

[1; 2; 3]

1::[2; 3]

• Variable number of elements
• All elements must be of the same type
• Linked list rather than array list

FP Types: Records

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 

type Person { 
    LastName: string 
    FirstName: string 
}

let person = {
    FirstName = "Joe"
    LastName = "Smith"
}

{ person with FirstName = "John" }

• Optional mutability

FP Types: Discriminated Unions

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 

type Shape =
    | Circle of int
    | Square of int
    | Rectangle of int * int

type option<'t> =
    | Some of 't
    | None

Basic Pattern Rules

pattern type

examples

constant

1.0, "test", Color.Red, ()

variable

x, number

tuple

(1, 2), (x, y)

array

[¦1; 2¦], [¦x; y¦]

list

[1; 2], [x; y]

cons

h::t, x::y::t

union

Some x, Circle(center, radius), Circle(radius = r)

exception

Failure msg

record

{ FirstName = "John", SSN = ssn }

wildcard

_, (x, _)

More Pattern Rules

pattern type

examples

or

(1, x) ¦ (2, x)

and

(x, y) & z

as

(x, y) as z

type test

:? Dog as d

List Traversal with Cons Pattern

1: 
2: 
3: 
4: 

let rec sum list =
    match list with
    | [] -> 0
    | item::items -> item + sum items

Alternate Lambda Syntax

1: 
2: 
3: 

let rec sum = function
    | [] -> 0
    | item::items -> item + sum items

Argument Parsing: Reverse Utility

Usage: reverse [options]
-i {file}, --input {file}   Specify an input file (stdin by default)
-o {file}, --output {file}  Specify an output file (stdout by default)
-l, --reverse-line-order    Reverse order of lines in file
-c, --reverse-line-content  Reverse content of each line

Argument Parsing: Entry Point

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 

type Settings = {
    InputFile: string option
    OutputFile: string option
    ReverseLineContent: bool
    ReverseLineOrder: bool
}

let defaultSettings = {
    InputFile = None
    OutputFile = None
    ReverseLineOrder = false
    ReverseLineContent = false
}

[<EntryPoint>]
let main args =
    let settings = parseArgs defaltSettings (List.ofArray args)
    reverseFile settings
    0

Argument Parsing: Pattern Matching

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 

let rec parseArgs settings args =
    match args with
    | [] -> 
        settings
    | "--input"::file::rest -> 
        parseArgs { settings with InputFile = Some file } rest
    | "--output"::file::rest -> 
        parseArgs { settings with OutputFile = Some file } rest
    | "--reverse-line-order"::rest -> 
        parseArgs { settings with ReverseLineOrder = true } rest 
    | "--reverse-line-content"::rest -> 
        parseArgs { settings with ReverseLineContent = true } rest
    | _ ->
        printUsage()
        exit 1

Argument Parsing: Or Patterns

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 

let rec parseArgs settings args =
    match args with
    | [] -> 
        settings
    | ("-i"|"--input")::file::rest -> 
        parseArgs { settings with InputFile = Some file } rest
    | ("-o"|"--output")::file::rest -> 
        parseArgs { settings with OutputFile = Some file } rest
    | ("-l"|"--reverse-line-order")::rest -> 
        parseArgs { settings with ReverseLineOrder = true } rest 
    | ("-c"|"--reverse-line-content")::rest -> 
        parseArgs { settings with ReverseLineContent = true } rest
    | _ ->
        printUsage()
        exit 1

Argument Parsing: Simplified

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 

let rec parseArgs settings args =
    if args = [] then settings else
    match args with
    | ("-i"|"--input")::file::rest -> 
        { settings with InputFile = Some file }, rest
    | ("-o"|"--output")::file::rest -> 
        { settings with OutputFile = Some file }, rest
    | ("-l"|"--reverse-line-order")::rest -> 
        { settings with ReverseLineOrder = true }, rest 
    | ("-c"|"--reverse-line-content")::rest -> 
        { settings with ReverseLineContent = true }, rest
    | _ ->
        printUsage()
        exit 1
    ||> parseArgs

Argument Parsing: Consumption

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 

let reverseFile settings =
    use reader = 
        match settings.InputFile with
        | Some file -> new StreamReader(file) :> TextReader
        | None -> stdin

    use writer =
        match settings.OutputFile with
        | Some file -> new StreamWriter(file) :> TextWriter
        | None -> stdout

    let revString line = String(line |> Array.ofSeq |> Array.rev)

    let lines =
        [| while reader.Peek() <> -1 do
            yield reader.ReadLine() |]
        |> Array.map (if settings.ReverseLineContent then revString else id)

    let lines = if settings.ReverseLineOrder then Array.rev lines else lines

    for line in lines do 
        writer.WriteLine line

Mathematical Expressions

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 
9: 

type Expr =
    | Con of int
    | Var of string
    | Add of Expr * Expr
    | Sub of Expr * Expr
    | Mult of Expr * Expr
    | Div of Expr * Expr
    | Power of Expr * Expr
    | Neg of Expr

Mathematical Expressions: Pretty Print

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 

let rec print expr =
    match expr with
    | Add(x, y) -> sprintf "(%s + %s)" (print x) (print y)
    | Sub(x, y) -> sprintf "(%s - %s)" (print x) (print y)
    | Mult(x, y) -> sprintf "(%s * %s)" (print x) (print y)
    | Div(x, y) -> sprintf "(%s / %s)" (print x) (print y)
    | Power(x, y) -> sprintf "(%s ** %s)" (print x) (print y)
    | Neg x -> sprintf "-(%s)" (print x)
    | Var x -> x
    | Con x -> string x

Mathematic Expressions: Deriviative

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 

let rec deriv var expr =
    let d = deriv var
    match expr with
    | Var var -> Con 1                           // Identity Rule
    | Con x -> Con 0                             // Constant Rule
    | Mult(Con x, y) | Mult(y, Con x) -> Con x   // Constant Factor Rule
    | Add(x, y) -> d x + d y                     // Sum Rule
    | Sub(x, y) -> d x - d y                     // Difference Rule
    | Mult(x, y) -> d x * y + x * d y            // Product Rule
    | Div(x, y) -> (d x * y - x * d y) / y ** 2  // Quotient Rule
    | Power(var, Con x) -> x * var ** (x - 1)    // Elementary Power Rule
    | _ -> failwith "Sorry, don't know how to differentiate that!"

Part 2

Active Patterns

Active Patterns: Single Case

1: 
2: 
3: 
4: 

let showNum input = 
    match Int32.TryParse input with
    | true, value -> string value
    | false, _ -> "NaN"

Active Patterns: Single Case

Good for creating reusable match rules or conversions.

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 
9: 

let (|Number|_|) input =
    match Int32.TryParse input with
    | true, value -> Some value
    | false, _ -> None

let showNum input =
    match input with
    | Number n -> string n
    | _ -> "NaN"

Active Patterns: Multi Case

Good for classifying data into one or more categories.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 

let (|Negative|Positive|Zero|) num = 
    match num with
    | 0 -> Zero
    | _ when num > 0 -> Positive num
    | _ when num < 0 -> Negative -num

let showNum input =
    match input with
    | Zero -> "Zero!"
    | Positive n -> sprintf "Positive %d" n
    | Negative n -> sprintf "Negative %d" n

Active Patterns: Argument Parsing

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 

let rec parseArgs settings args =
    if args = [] then settings else
    match args with
    | ("-i"|"--input")::file::rest when not (file.StartsWith "-") -> 
        { settings with InputFile = Some file }, rest
    | ("-o"|"--output")::file::rest when not (file.StartsWith "-") -> 
        { settings with OutputFile = Some file }, rest
    | ("-l"|"--reverse-line-order")::rest -> 
        { settings with ReverseLineOrder = true }, rest 
    | ("-c"|"--reverse-line-content")::rest -> 
        { settings with ReverseLineContent = true }, rest
    | _ ->
        printUsage()
        exit 1
    ||> parseArgs

Active Patterns: Argument Parsing

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 

let (|File|_|) input =
    if input.StartsWith "-" then None
    else Some input

let rec parseArgs settings args =
    if args = [] then settings else
    match args with
    | ("-i"|"--input")::File file::rest -> 
        { settings with InputFile = Some file }, rest
    | ("-o"|"--output")::File file::rest -> 
        { settings with OutputFile = Some file }, rest
    | ("-l"|"--reverse-line-order")::rest -> 
        { settings with ReverseLineOrder = true }, rest 
    | ("-c"|"--reverse-line-content")::rest -> 
        { settings with ReverseLineContent = true }, rest
    | _ ->
        printUsage()
        exit 1
    ||> parseArgs

Active Patterns: Argument Parsing

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 

let (|File|) input =
    if input.StartsWith "-" then 
        failwith "'%s' is not a valid filename." input
    else input

let rec parseArgs settings args =
    if args = [] then settings else
    match args with
    | ("-i"|"--input")::File file::rest -> 
        { settings with InputFile = Some file }, rest
    | ("-o"|"--output")::File file::rest -> 
        { settings with OutputFile = Some file }, rest
    | ("-l"|"--reverse-line-order")::rest -> 
        { settings with ReverseLineOrder = true }, rest 
    | ("-c"|"--reverse-line-content")::rest -> 
        { settings with ReverseLineContent = true }, rest
    | _ ->
        printUsage()
        exit 1
    ||> parseArgs

Part 3

Patterns Everywhere

Patterns: Not Just for Match Expressions

Many other places in F# are "secretly" pattern matches.

• let bindings
• function & lambda parameters
• for .. in
• try .. with

Patterns in let bindings

The expression

1: 
2: 

let x = 2
...

is really like

1: 

match 2 with x -> ...

So you can do

1: 
2: 

let x, y = 1, 2
let Number n = "5"

Note however

1: 
2: 

let [x; y] = list
let Some x = option

will cause incomplete match warnings since the is only one case.

Patterns in For Loops

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 

let nameAges = [
    "John", 22
    "Jane", 43
    "George", 68
]

for name, age in nameAges do
    printfn "The age of %s is %d" name age

Patterns in Function Parameters

Pattern matching in lambda parameters

1: 
2: 
3: 

nameAges 
|> Seq.iter (fun (name, age) -> 
    printfn "The age of %s is %d" name age)

Calculating an endpoint to a line

1: 
2: 
3: 
4: 
5: 
6: 
7: 

let endpoint (startX, startY) length angle =
    x + length * cos angle, y + length * sin angle

let start = (5., 5.)
let length = 10.
let angle = 0.5 * Math.PI
let endX, endY = endpoint start length angle

Normal function parameters are actually "variable" patterns.

Patterns in Try ... With

Exception handling in F# is just pattern matching.

1: 
2: 
3: 
4: 
5: 

try
    File.ReadAllLines "data.txt"
 with 
    | :? IOException as e -> 
        printfn "An IO exception occurred: %s" e.Message

Exercise: Fizzbuzz

Solve Fizzbuzz using pattern matching.

Rules for FizzBuzz:

• If number is divisible by 3 and 5, print "FizzBuzz".
• If number is divisible by 3 only, print "Fizz".
• If number is divisible by 5 only, print "Buzz".
• Otherwise, print the number itself.

Example Output (1-15): 1,2,Fizz,4,Buzz,Fizz,7,8,Fizz,Buzz,11,Fizz,13,14,FizzBuzz

• First solve without active patterns.
• Then solve with with active patterns.
• Single-case or multi-case patterns may be useful.

The End

Thanks to:

• Paul Blasucci (@pblasucci) for the idea
• Karlkim Suwanmonkol (@kimsk) for FsReveal
• Firefly Logic (@FireflyLogic) for hosting