F Sharp Programming/Active Patterns

Previous: Caching Index Next: Advanced Data Structures
F# : Active Patterns

Active Patterns allow programmers to wrap arbitrary values in a union-like data structure for easy pattern matching. For example, its possible wrap objects with an active pattern, so that you can use objects in pattern matching as easily as any other union type.

Defining Active Patterns

edit

Active patterns look like functions with a funny name:

let (|name1|name2|...|) = ...

This function defines an ad hoc union data structure, where each union case namen is separated from the next by a | and the entire list is enclosed between (| and |) (humbly called "banana brackets"). In other words, the function does not have a simple name at all, it instead defines a series of union constructors.

A typical active pattern might look like this:

let (|Even|Odd|) n =
    if n % 2 = 0 then
        Even
    else
        Odd

Even and Odd are union constructors, so our active pattern either returns an instance of Even or an instance of Odd. The code above is roughly equivalent to the following:

type numKind =
    | Even
    | Odd

let get_choice n =
    if n % 2 = 0 then
        Even
    else
        Odd

Active patterns can also define union constructors which take a set of parameters. For example, consider we can wrap a seq<'a> with an active pattern as follows:

let (|SeqNode|SeqEmpty|) s =
    if Seq.isEmpty s then SeqEmpty
    else SeqNode ((Seq.head s), Seq.skip 1 s)

This code is, of course, equivalent to the following:

type seqWrapper<'a> =
    | SeqEmpty
    | SeqNode of 'a * seq<'a>
    
let get_choice s =
    if Seq.isEmpty s then SeqEmpty
    else SeqNode ((Seq.head s), Seq.skip 1 s)

You've probably noticed the immediate difference between active patterns and explicitly defined unions:

  • Active patterns define an anonymous union, where the explicit union has a name (numKind, seqWrapper, etc.).
  • Active patterns determine their constructor parameters using a kind of type-inference, whereas we need to explicitly define the constructor parameters for each case of our explicit union.

Using Active Patterns

edit

The syntax for using active patterns looks a little odd, but once you know what's going on, it's very easy to understand. Active patterns are used in pattern matching expressions, for example:

> let (|Even|Odd|) n =
    if n % 2 = 0 then Even
    else Odd
    
let testNum n =
    match n with
    | Even -> printfn "%i is even" n
    | Odd -> printfn "%i is odd" n;;

val ( |Even|Odd| ) : int -> Choice<unit,unit>
val testNum : int -> unit

> testNum 12;;
12 is even
val it : unit = ()

> testNum 17;;
17 is odd

What's going on here? When the pattern matching function encounters Even, it calls (|Even|Odd|) with parameter in the match clause, it's as if you've written:

type numKind =
    | Even
    | Odd

let get_choice n =
    if n % 2 = 0 then
        Even
    else
        Odd
        
let testNum n =
    match get_choice n with
    | Even -> printfn "%i is even" n
    | Odd -> printfn "%i is odd" n

The parameter in the match clause is always passed as the last argument to the active pattern expression. Using our seq example from earlier, we can write the following:

> let (|SeqNode|SeqEmpty|) s =
    if Seq.isEmpty s then SeqEmpty
    else SeqNode ((Seq.head s), Seq.skip 1 s)
    
let perfectSquares = seq { for a in 1 .. 10 -> a * a }

let rec printSeq = function
    | SeqEmpty -> printfn "Done."
    | SeqNode(hd, tl) ->
        printf "%A " hd
        printSeq tl;;

val ( |SeqNode|SeqEmpty| ) : seq<'a> -> Choice<('a * seq<'a>),unit>
val perfectSquares : seq<int>
val printSeq : seq<'a> -> unit

> printSeq perfectSquares;;
1 4 9 16 25 36 49 64 81 100 Done.

Traditionally, seq's are resistant to pattern matching, but now we can operate on them just as easily as lists.

Parameterizing Active Patterns

edit

Its possible to pass arguments to active patterns, for example:

> let (|Contains|) needle (haystack : string) =
    haystack.Contains(needle)

let testString = function
    | Contains "kitty" true -> printfn "Text contains 'kitty'"
    | Contains "doggy" true -> printfn "Text contains 'doggy'"
    | _ -> printfn "Text neither contains 'kitty' nor 'doggy'";;

val ( |Contains| ) : string -> string -> bool
val testString : string -> unit

> testString "I have a pet kitty and she's super adorable!";;
Text contains 'kitty'
val it : unit = ()

> testString "She's fat and purrs a lot :)";;
Text neither contains 'kitty' nor 'doggy'

The single-case active pattern (|Contains|) wraps the String.Contains function. When we call Contains "kitty" true, F# passes "kitty" and the argument we're matching against to the (|Contains|) active pattern and tests the return value against the value true. The code above is equivalent to:

type choice =
    | Contains of bool
    
let get_choice needle (haystack : string) = Contains(haystack.Contains(needle))

let testString n =
    match get_choice "kitty" n with
    | Contains(true) -> printfn "Text contains 'kitty'"
    | _ ->
        match get_choice "doggy" n with
        | Contains(true) -> printfn "Text contains 'doggy'"
        | printfn "Text neither contains 'kitty' nor 'doggy'"

As you can see, the code using the active patterns is much cleaner and easier to read than the equivalent code using the explicitly defined union.

Note: Single-case active patterns might not look terribly useful at first, but they can really help to clean up messy code. For example, the active pattern above wraps up the String.Contains method and allows us to invoke it in a pattern matching expression. Without the active pattern, pattern matching quickly becomes messy:

let testString = function
    | (n : string) when n.Contains("kitty") -> printfn "Text contains 'kitty'"
    | n when n.Contains("doggy") -> printfn "Text contains 'doggy'"
    | _ -> printfn "Text neither contains 'kitty' nor 'doggy'"

Partial Active Patterns

edit

A partial active pattern is a special class of single-case active patterns: it either returns Some or None. For example, a very handy active pattern for working with regex can be defined as follows:

> let (|RegexContains|_|) pattern input = 
    let matches = System.Text.RegularExpressions.Regex.Matches(input, pattern)
    if matches.Count > 0 then Some [ for m in matches -> m.Value ]
    else None

let testString = function
    | RegexContains "http://\S+" urls -> printfn "Got urls: %A" urls
    | RegexContains "[^@]@[^.]+\.\W+" emails -> printfn "Got email address: %A" emails
    | RegexContains "\d+" numbers -> printfn "Got numbers: %A" numbers
    | _ -> printfn "Didn't find anything.";;

val ( |RegexContains|_| ) : string -> string -> string list option
val testString : string -> unit

> testString "867-5309, Jenny are you there?";;
Got numbers: ["867"; "5309"]

This is equivalent to writing:

type choice =
    | RegexContains of string list
    
let get_choice pattern input =
    let matches = System.Text.RegularExpressions.Regex.Matches(input, pattern)
    if matches.Count > 0 then Some (RegexContains [ for m in matches -> m.Value ])
    else None

let testString n =
    match get_choice "http://\S+" n with
    | Some(RegexContains(urls)) -> printfn "Got urls: %A" urls
    | None ->
        match get_choice "[^@]@[^.]+\.\W+" n with
        | Some(RegexContains emails) -> printfn "Got email address: %A" emails
        | None ->
            match get_choice "\d+" n with
            | Some(RegexContains numbers) -> printfn "Got numbers: %A" numbers
            | _ -> printfn "Didn't find anything."

Using partial active patterns, we can test an input against any number of active patterns:

let (|StartsWith|_|) needle (haystack : string) = if haystack.StartsWith(needle) then Some() else None
let (|EndsWith|_|) needle (haystack : string) = if haystack.EndsWith(needle) then Some() else None
let (|Equals|_|) x y = if x = y then Some() else None
let (|EqualsMonkey|_|) = function (* "Higher-order" active pattern *)
    | Equals "monkey" () -> Some()
    | _ -> None
let (|RegexContains|_|) pattern input = 
    let matches = System.Text.RegularExpressions.Regex.Matches(input, pattern)
    if matches.Count > 0 then Some [ for m in matches -> m.Value ]
    else None

let testString n =
    match n with
    | StartsWith "kitty" () -> printfn "starts with 'kitty'"
    | StartsWith "bunny" () -> printfn "starts with 'bunny'"
    | EndsWith "doggy" () -> printfn "ends with 'doggy'"
    | Equals "monkey" () -> printfn "equals 'monkey'"
    | EqualsMonkey -> printfn "EqualsMonkey!" (* Note: EqualsMonkey and EqualsMonkey() are equivalent *)
    | RegexContains "http://\S+" urls -> printfn "Got urls: %A" urls
    | RegexContains "[^@]@[^.]+\.\W+" emails -> printfn "Got email address: %A" emails
    | RegexContains "\d+" numbers -> printfn "Got numbers: %A" numbers
    | _ -> printfn "Didn't find anything."

Partial active patterns don't constrain us to a finite set of cases like traditional unions do, we can use as many partial active patterns in match statement as we need.

Additional Resources

edit
Previous: Caching Index Next: Advanced Data Structures