Navigate / search

Active Patterns: Single Partial (|A|_|)

This entry is part 5 of 8 in the series Active Patterns

I’ve referred to all of the Active Patterns we have seen so far in this series as ‘Single Total’. It’s time to look at the distinction between ‘Total’ and ‘Partial’ Active Patterns.

To understand Partial Active Patterns you need to have some understanding of Option Types’. If they are new to you, I’d encourage you to read up on them before continuing. A great place for reading about this, and F# generally is FSharpForFunAndProfit.

When we write a function to count the upper case characters in a string, there is always an answer, even if that answer is 0. Not all functions are so clear cut. If we write a function to parse a string into a number, it is possible to provide strings that simply can’t be parsed.

ParseNumber(“21”) // OK
ParseNumber(“Tango Foxtrot”) // What can we do with this?

All of the examples we’ve seen so far have involved Active Patterns that are just transformation functions. The match expression uses guards, literal values, variables and wildcards to decide how it will match on the returned value.

Partial Active Patterns take back some of that control. A ParseNumber active pattern can decide that it won’t match a value regardless of how the match expression is constructed. It does this by returning an Option Type. When it returns ‘Some Value’ the match expression will deal with that value just as before, but if the Active Expression returns ‘None’ then there is no match and the value falls through and must be handled by a different pattern.

Since we’ve been talking about parsing numbers, let’s look at an example.

let (|Number|_|) (str: string) =
    match Int32.TryParse(str) with
    | (true, n) -> Some(n)
    | false, _ -> None

The Active Pattern name now includes an extra component. The underscore (wildcard) indicates that this is a partial Active Pattern. Not every string that is passed to this pattern can be turned into a Number. We can use this in a match expression as follows.

let IsItANumber (str: string) =
    match str with
    | Number n -> sprintf "That was number %d" n
    | _ -> sprintf "Not a number"

Option Types are still valid types. You can return an option from a SingleTotal active pattern.

let (|Number|) (str: string) =
    match Int32.TryParse(str) with
    | (true, n) -> Some(n)
    | false, _ -> None

let IsItANumber (str: string) =
    match str with
    | Number (Some n) -> sprintf "That was number %d" n
    | _ -> sprintf "Not a number"

The remainder of the Active Pattern is identical, but, because we used the SingleTotal form of the Active Pattern we have to unpack the value n from the option type using the ‘Some’ keyword. By using the Partial Form of the active pattern we get that for free.

I’ll be honest I find that a little confusing because the signatures of both forms of the pattern are the same (string -> int option). Don’t worry too much about it (I don’t), if you are writing Single case Active Patterns that can’t match all possible inputs then use the Partial form.

The Infamous FizzBuzz
Let’s take another example of a Total Active Pattern and convert it to a Partial, and see what happens. Here is the infamous FizzBuzz

let (|Multiple|) m n =
    if n%m=0 then true
    else false

let (|Fizz|) = (|Multiple|) 3
let (|Buzz|) = (|Multiple|) 5

let FizzBuzz n =
    match n with
    | Fizz true & Buzz true -> "FizzBuzz"
    | Fizz true -> "Fizz"
    | Buzz true -> "Buzz"
    | _ -> n.ToString()

The Active Pattern (|Multiple|) returns a boolean indicating whether parameter ‘n’ is a multiple of ‘m’. Because it returns true or false, our match expression needs to specify those literals in order to catch the various cases.

Here’s the same code rewritten using Partials

let (|Multiple|_|) m n =
    if n%m=0 then Some Multiple
    else None

let (|Fizz|_|) = (|Multiple|_|) 3
let (|Buzz|_|) = (|Multiple|_|) 5

let FizzBuzz n =
    match n with
    | Fizz & Buzz -> "FizzBuzz"
    | Fizz -> "Fizz"
    | Buzz -> "Buzz"
    | _ -> n.ToString()

The booleans are gone, the Active Patterns now return Multiple, Fizz, Buzz and None leading to a cleaner match expression. Both those examples also use Currying and the ‘&’ pattern from the last post.

An Expression Evaluator
Let’s finish this post with one last example, a little more ambitious this time. We’ll start with a match expression and see if we can figure out the Active Patterns to make the magic happen.

let rec Eval str =
    match str with
    | Number x -> x
    | Addition (l, r) -> Eval(l) + Eval(r)
    | Subtraction (l, r) -> Eval(l) - Eval(r)
    | _ -> raise (System.ArgumentException("Invalid Expression " + str))

This function evaluates expressions. It seems to only handle Numbers, Addition and Subtraction so we’ll need Active Patterns for each of those.

It looks like the expression is represented as a string, but the pattern matching would be basically identical even if expression were represented in another way. That’s one of the perks at coding at a higher level of abstraction.

Number looks like the example we’ve already seen, let’s do that first.

let (|Number|_|) (str: string) =
    match Int32.TryParse(str) with
    | (true, n) -> Some(n)
    | false, _ -> None

Incidentally if that syntax for the TryParse function is throwing you a little, have a look at this post.

Both Addition and Subtraction accept strings and return what look like tuples representing the left and right subexpressions.

let (|Addition|_|) (str: string) =
    let SplitAt (op: string) (str: string) =
        let pos = (str.IndexOf op)
        (str.Substring(0, pos),str.Substring(pos + 1, str.Length - pos - 1))

    if str.Contains("+") then 
        Some (SplitAt "+" str)
    else
        None

let (|Subtraction|_|) (str: string) =
    let SplitAt (op: string) (str: string) =
        let pos = (str.IndexOf op)
        (str.Substring(0, pos),str.Substring(pos + 1, str.Length - pos - 1))

    if str.Contains("-") then 
        Some (SplitAt "-" str)
    else
        None

Some code duplication there, but it will work. Both patterns check the incoming string. If it contains the right operator the patterns split the string and returns either side as the elements of a tuple. The Eval function then takes those two subexpressions, recursively evaluates them and applies the right operator to bring the two expressions back together.

The next post will be very short and will show how to use parameters with Partial Active Patterns. This won’t need much explaining because it’s the same process as adding parameters to Total Active Patterns which you’ve already seen. We’ll use parameters to rewrite this expression evaluator and get rid of the duplicated code.

Active Patterns: Partial Application

This entry is part 4 of 8 in the series Active Patterns

This post was supposed to be about Partial Active Patterns, but before we get to that, I want to take a small diversion to cover Partial Application of Active Patterns (which is a completely different thing). Confused? Don’t worry. Read on.

Partial Application
I’ve described Partial Application in detail here and here, so I’m going to assume that you know how it works for regular functions. Please read those two posts if you are in any doubt.

Partial Application was raised in a question from Shawn Martin regarding this post.

what might be the best way(s) to turn SpecialCharacterCount in this post into the hard-coded SpecialCharacterCount from the previous post? In other words, do partial application.

Coincidentally Anthony Brown (@bruinbrown93) had tweeted on the same topic.

You can also partially apply your active patterns. E.g. let (|ExclamationMarkCount|) = (|SpecialCharacterCount|) “!”

So, let’s cover partial application of active patterns.

Recall our active pattern for counting occurrences of characters in a string.

let (|SpecialCharacterCount|) (characters: string) (str: string) =
    str.ToCharArray()
    |> Array.filter (fun c -> characters.Contains(c.ToString()))
    |> Array.length

In addition to the parameter ‘str’ for the string that we’ll search, we have a parameter ‘characters’ containing the characters that we’ll search for. We can use this, and the magic of partial application to create other Active Patterns that have the characters baked in, so we don’t need to provide them as an extra argument.

let (|CountDollars|) = (|SpecialCharacterCount|) “$”

We can use CountDollars just like any Active Pattern, but it’s hardwired to search for the ‘$’.

let describeString (s: string) =
    match s with
    | CountDollars d when d > 5 -> "%d is more than 5 Bucks" 
    | CountDollars 4 -> "That's 4 Bucks" 
    | CountDollars d -> "Just %d Dollars" d 

Creating more patterns that search for different characters is trivial

let (|CountStars|) = (|SpecialCharacterCount|) "*"

Now instead of counting dollars, we’ll be counting stars.
Yeah, I went there. Don’t judge me.

And, of course the argument to the original Active Pattern can contain multiple characters, and that still applies.

let (|CountCurrencies|) = (|SpecialCharacterCount|) "£$"

We can mix and match our original and newly minted patterns.

let describeString (str: string) =
    match str with
    | CountCurrency c when c > 3 -> "More than three currency symbols"
    | CountDollars d when d > 0 -> "There's at least one Dollar"
    | CountStars 2 -> "There are exactly two Stars "
    | SpecialCharacterCount "!%^&" s -> sprintf "I found %d special characters" s
    | _ -> str 

Patterns
The second topic I wanted to touch on before moving forward is Patterns. In the first post in the series I gave an introduction to Pattern Matching which has served us well in understanding the examples. It was however just the briefest of introductions, let’s dig a little deeper.

In the (|IsValid|) active pattern in this post I quietly slipped in something a little unusual. I used multiple Patterns within the same clause.

  | UpperCaseCount u & LowerCaseCount l & SpecialCharacterCount s -> ...

For that clause to match all three of those patterns need to match. This makes sense, the ‘&’ represents ‘and’.

All of the patterns that you can use are described here so I won’t go into each in detail. I will briefly mention the ‘or’ pattern denoted by the ‘|’ operator, to give you a sense of what these patterns can do.

Take a look at this function.

let describeString (str: string) =
    match str with
    | CountDollars c | CountStars c when c > 5 -> sprintf "%d is more than 5 Dollars or Stars" c
    | _ -> str 

If either CountDollars or CountStars returns a count of more than 5 then the first clause will match. If CountDollars returns more than 5 then c will hold it’s value. If not then there’s still the chance that CountStars will set the value of c. If neither are above 5 the clause in it’s entirety will fail. Note we’re not talking about the total of Dollars and Stars exceeding 5. Either Dollars or Stars must exceed 5 in it’s own right.

Literals can be used on both sides of the ‘|’ operator, but if a variable is used, it must be the same on both sides.

let describeString (str: string) =
    match str with
    | CountDollars c | CountStars c when c > 5 -> sprintf "%d Dollars or Stars, that's more than 5" c
    | CountDollars 2 | CountStars 10 -> "2 Dollars and 10 Stars"
    | _ -> str 

The following is not valid for the ‘or’ pattern.

   | CountDollars 2 | CountStars s -> sprintf "2 Dollars and %s Stars" s

I’ll leave you to play with the other patterns. In the next post we’ll get back to describing the different forms of Active Pattern.

ByRef Params: You gotta love F#

I come across this little beauty while reading up on Active Patterns.

In C# functions like TryParse return a bool, you need to declare a variable to pass to the out param to get back the parsed value.

That means creating a variable just to get a value out of a function, and doing this in F# would mean having a mutable variable. *spit*

The same Int32.TryParse function can be called from F# like this…

let t = Int32.TryParse("5")

No by ref arg. Even though that isn’t one of the overloads for the function.

F# takes care of creating the byref arg and then returns a tuple instead of a bool so that the out param is returned from the function instead of having to use a nasty mutable variable.

So, the result looks like this.

let t = Int32.TryParse("5")
val t : bool * int = (true, 5)

let t = Int32.TryParse("F")
val t : bool * int = (false, 0)

A nasty function with out args converted into a beautiful pure function, automatically by the calling language, without touching the original function.

Which of course means that you can pattern match on a function with out params in a really nice way.

match Int32.TryParse(str) with
| (true, n) -> Some(n)
| false, _ -> None

The deeper I get into F#. the more I love it.

Active Patterns: Single Total With Params (|A|) x

This entry is part 3 of 8 in the series Active Patterns

We move on to the next in our series on Active Patterns, but this time we’re really just covering a slight modification to the Single Total pattern that we covered in the last post.

All the same rules apply, we’re just adding the ability to add parameters to the Active Pattern.

I say ‘parameters’ but in reality I mean ‘additional parameters’. Every Active Pattern has at least one parameter. The ‘x’ in ‘match x with’ has to go somewhere.

Remember the Active Patterns we’ve seen so far are just functions. If you take away the banana clips they are identical to functions. Additional parameters are supported exactly the same way they are with regular functions.

All you need to remember is that the ‘x’ in ‘match x with’ will be passed to the last parameter of the Active Pattern. The other parameters are set by the individual lines in the Pattern Match expression.

An example might help.

Here’s the Active Pattern we used in the last post to count special characters in a string.

let (|SpecialCharacterCount|) (str: string) =
    let specialCharacters = "!£$%^"
    str.ToCharArray()
    |> Array.filter (fun c -> specialCharacters.Contains(c.ToString()))
    |> Array.length

Note the special characters are hard coded. This being a function it’s simple to turn that into a parameter.

let (|SpecialCharacterCount|) (characters: string) (str: string) =
    str.ToCharArray()
    |> Array.filter (fun c -> characters.Contains(c.ToString()))
    |> Array.length

You can add multiple parameters but it’s important to know how they map to the pattern matching expression that will use the Active Pattern.

Here’s code that would match against the old ‘non-parameterized’ Active Pattern

let UseThePattern (str: string) =
    match str with
    | SpecialCharacterCount c -> sprintf "That was %d special characters" c

By contrast here’s the code that uses the parameterized version

let UseThePattern (str: string) =
    match str with
    | SpecialCharacterCount "!£$%^" c -> sprintf "That was %d special characters" c

The ‘str’ in the match expression still gets passed to the last parameter of the Active Pattern, and the return value of the Active Pattern still gets assigned to ‘c’. In place of c you can still use literals just as in the last post.

The only real difference is that the extra arguments are placed between the name of the Active Pattern and the variable or literal value that we match against.

Here’s another sketch to try and hammer this home.

Apologies for spelling this out in such tedious detail but if you get what’s happening here, everything else about Active Patterns will be very simple.

Oh, and that little assignment trick we saw in the last post still works, just pass the arguments needed by the Active Pattern.

let (SpecialCharacterCount "!£$%^" c) = "ABC!"
val c : int = 1

That’s it for this post and for my nemesis the Single Total Active Pattern. Next up we discover the wonders of Partial Active Patterns. We get to rope in another interesting piece of F#, Option Types.

Active Patterns: Pattern Matching

This entry is part 1 of 8 in the series Active Patterns

After two posts here, and here complaining about the Single Case Active Pattern, it’s time to write the posts I’ve been trying to write all along about how active patterns are amazing.

This post will lay the groundwork by covering pattern matching, and introducing the concept of active patterns. Subsequent posts will cover the various types of active pattern in detail.

Destructuring Assignment
Thanks to Miles McGuire for setting me straight on the name.

FSharp is full of little nice ideas that you appreciate when you come from a C# background, and destructuring assignment is one of them. Take a look at the following.

let date = (21, 8, 2014)

let d, m, y = date
val y : int = 2014
val m : int = 8
val d : int = 21

let _, month, year = date
val year : int = 2014
val month : int = 8

That’s a tuple representing a date. To extract values from the tuple and assign them to the three variables d, m and y we can do a single assignment. The tuple gets deconstructed (think constructor in reverse).

In the second assignment we use the _ to indicate that we don’t care about the first value in the tuple. It will create two variables month and year.

That alone is pretty nice, but it gets better.

Pattern Matching
Destructuring assignment is really a form of Pattern Matching, which is common in Functional Programming languages. In FSharp the match expression allows us to match against quite elaborate data structures.

First let’s take a look at a match expression that does little more than the assignment above.

let patternMatch date =
    match date with
    | d, m, y -> sprintf "Day [%d], Month [%d], Year [%d]" d m y   

With Pattern matching we can deconstruct the date just as we did in the assignment. The match expression allows us to create multiple match clauses, with the value of the overall expression being decided by the first clause that matches.

let partialPatternMatch date =
    match date with
    | _, _, y when y < 1960 -> "Nothing before the 60's matters"
    | _, m, 1960 -> sprintf "Ah the month was %d, the 60's were just beginning" m
    | _, 12, y -> sprintf "It was Christmas, %d" y
    | d, m, y -> sprintf "Day [%d], Month [%d], Year [%d]" d m y

Clauses can match based on a ‘when’ guard as in the first example above. We can also insert literal values into the pattern as with the year 1960 in the second case and the month 12 in the third. In both of those examples we match with any day because we use the underscore to indicate that we don’t care what the day is. Also in those examples we match the month and year respectively to variables (m and y) which can be used in the results.

In the final clause we are guaranteed to match any date that fails to match on any of the first three clauses. There are no literal values or when guards that could cause the last case to fail, we just get the day month and year, whatever they may be and can use them in the result.

Match Against Abstractions
As exciting as all that is, you’ll notice that like the assignment earlier, the pattern matching in a match expression really only matches against and/or extracts data that’s already there. We’re matching here on the raw numbers that are the underlying representation of the date. It would be nice to match on things like

  • May
  • First Quarter
  • Summer
  • Month End
  • Saturday
  • Holiday

These are all abstractions that should be independent of how the date is implemented. Active Patterns allow us to pattern match against these kinds of abstraction, rather than the underlying data.

Active Patterns
What we need is the matching and extracting of pattern matching, but with the added ability to transform the data we’re working with.

We already have a really good general purpose way of transforming data, namely functions, so it shouldn’t come as any surprise that Active Patterns are special kind of function with some extra powers that make them useful in pattern matching.

Active Patterns come in a few varieties so, the next couple of posts will describe the various options. Don’t worry too much about the notation below. All will become clear as you read through the examples.

OK, I haven’t explained what Total and Partial means yet. All in good time, but if you’re a little OCD like me you’ll notice that list doesn’t look quite complete, there is no “Multiple Partial”. The reason for that is very simple, the language designers haven’t added them yet, and may not add them at all.

“For completeness our specification includes structured names with multiple cases, e.g, (|ParseInt|ParseFloat|_|). However we have yet to detect any practical benefit in doing so.”[1]

We’re getting ahead of ourselves. Next Post (at last) an explanation of the Single Case Total Active Pattern, with an example I can stand over.

Active Patterns: Single Case Total Pattern

A few weeks ago I blogged about my trouble understanding the point of Single Case Active Patterns.

At the time I intended to complete a series of posts on the various kinds of Active Patterns. I’m finally getting around to writing that series of posts.

Digging back into Active Patterns, and the Single Case in particular quickly brought back the same old frustrations, leading to this tweet

I little harsh maybe, but I’d just read countless examples that all annoyed me in exactly the same way. Let me clarify.

How I Learn
There are two things that I need to understand before I really “get it”

1. The mechanics of the feature (how to use it)
2. The point of the feature (when or why to use it)

The problem I alluded to in my tweet is that most explanations are heavy on the mechanics and light on the point.

Here’s an example from Chris Smith’s excellent book F# 3.0.

let (|FileExtension|) filePath = Path.GetExtension(filePath)

Single Case active patterns convert an input to an output, they are really just functions. In this case Chris Wraps Path.GetExtension so that it can be used in pattern matches.

let determineFileType filePath =
    match filePath with
    | FileExtension ".jpg"
    | FileExtension ".png"
    | FileExtension ".gif"
        -> printfn "It is an image file"
    |FileExtension ext
        -> printfn "Unknown file extension [%s]" ext

He suggests that the equivalent pattern match without the Active Pattern would be

    match filePath with
    | filePath when Path.GetExtension(filePath) = ".txt"
        -> printfn "It is an image file"

Which isn’t helpful because a) it isn’t equivalent, it doesn’t show how to handle the multiple file types, and
b) it isn’t even the cleanest alternative. We could do the following.

let determineFileType filePath =
    match Path.GetExtension(filePath) with
    | ".jpg"
    | ".png"
    | ".gif"
        -> printfn "It is an image file"
    |ext
        -> printfn "Unknown file extension [%s]" ext

Now that’s the non active pattern equivalent, and I prefer it.

A Better Example
Jessica Kerr has another example on Developer Fusion.

Jessica is very very smart and her explanation actually followed exactly the model I like. She provided one example to show the mechanics and another example showing why the feature is useful.

I’ll skip her first “iTron” example, it’s another perfectly good example of how a Single Case Active Pattern hangs together. Her second example shows a potential real world use, which is what I’m looking for.

let line = "MO 8.00% 10.00%"

type StateTax (s:string, i:float, p:float)= 
    member this.Abbr = s
    member this.IncomeTaxRate = i
    member this.PropertyTaxRate = p

let (|ParseLine|) (s : string) = 
    let parts = s.Split([|' ';'%'|])
    let incomeTax = float parts.[1] / 100.0
    let propertyTax = float parts.[3] / 100.0
    (parts.[0],incomeTax, propertyTax)

The rationale is that with the pattern defined “we can do parsing, transformation, and validation in one short match expression.”

let output line = 
   match line with
    | ParseLine (s, i, t) when s = "MO" || s = "TN"
          -> Some (StateTax(s, i, t))
    | wth -> printfn "Unsupported: %s" wth; None 

Which is fine, except this works too

let ParseTax (s : string) = 
    let parts = s.Split([|' ';'%'|])
    let incomeTax = float parts.[1] / 100.0
    let propertyTax = float parts.[3] / 100.0
    (parts.[0],incomeTax, propertyTax)

let output2 line =
   match ParseTax(line) with
    | (s, i, t) when s = "MO" || s = "TN"
          -> Some (StateTax(s, i, t))
    | _ -> printfn "Unsupported: %s" line; None

This is the problem I kept hitting. Every example I could find could be rewritten without the Active Pattern at no great loss that I could see. Calling these examples “Gawd Awful” was too much, they are not that bad. But there are lots and lots of very similar explanations and they either miss or avoid very basic points about active patterns and their alternatives.

I finally cracked and put the word out to twitter asking for help

And a brief discussion with Loïc Denuzière ‏@Tarmil_ let me to the following:

let (|FileExtension|) filePath = Path.GetExtension(filePath)

let (|FileName|) filePath = Path.GetFileNameWithoutExtension(filePath)

let (|FileLocation|) filePath = Path.GetDirectoryName(filePath)

let determineFileType filePath =
    match filePath with
    | FileExtension ".jpg"
    | FileExtension ".png"
    | FileExtension ".gif"
    | FileName "logo"
    | FileLocation "c:\images"
        -> printfn "It is an image file"
    | FileName "readme"
        -> printfn "It is a Read Me file"
    | ext
        -> printfn "Unknown file type [%s]" filePath

This is similar to Chris Smiths, but note we’ve defined multiple Single Case Active Patterns, and we are pattern matching across all of them. My earlier trick of putting the function call in the match statement won’t work.

Although this is a case that my earlier alternative can’t handle, it still feels a bit contrived. If this kind of situation does arise, I think it may be a bit of an edge case rather than a common situation. Maybe I’m wrong.

Active Patterns in general are pretty awesome however, more on that soon.

Learning To Think Functionally: Types, Maps and Sets

Download Sample Project 3.5 KB

In the most recent post in this series I implemented Tic-Tac-Toe using recursion to find the best moves. The point of that post was the recursion and I took the simplest approach I could think of to represent the actual board and moves.

I used two lists of ints, one for each player’s list of occupied squares. The board itself wasn’t explicitly represented at all, it could be inferred from the two lists.

One problem with this is that there are only 9 possible squares, but our lists could hold any integers, or could both hold the same integer. It was not only possible but quite easy to represent an invalid state.

For this post I’ll turn to this issue and try to use the type system to give us a more sensible model of the game.

    type Player = X | O

    type Position = TopLeft | TopMiddle | TopRight 
                    | MiddleLeft | Center | MiddleRight 
                    | BottomLeft | BottomMiddle| BottomRight

    type Board = Map<Position, Player Option>

I’ve represented a Player as being X or O, and the Position type has nine possible values, i.e. the nine squares on the board.

We move away from the idea in the last post of just storing each players squares and instead we use a Map from Position to a Player Option. This means that we can look at any square on the board and see if it is owned by X, O or by neither.

This fairly simple change has immediately solved the two invalid state issues I described above. A given square can not belong to both players simultaneously, and player can only own squares on the board, we can’t just “invent” new positions as we could by putting extra integers into the lists in the earlier example.

Let’s initialize an empty board so that we can start playing.

    let NewBoard: Board = 
            Map [ (TopLeft, None); (TopMiddle, None); (TopRight, None); 
                  (MiddleLeft, None); (Center, None); (MiddleRight, None); 
                  (BottomLeft, None); (BottomMiddle, None); (BottomRight, None) ]

I couldn’t figure out how to do a nice “For All” Positions, Map to None, other than by using Reflection which just seemed cumbersome for such a simple task.

Wins are defined in the same way as in the last post, but it’s a little more readable now because each position is named.

    let wins = set [ set [ TopLeft; TopMiddle; TopRight ] ;
                     set [ MiddleLeft; Center; MiddleRight ] ;
                     set [ BottomLeft; BottomMiddle; BottomRight ] ;
                     set [ TopLeft; MiddleLeft; BottomLeft ] ;
                     set [ TopMiddle; Center;  BottomMiddle ] ;
                     set [ TopRight; MiddleRight; BottomRight ] ;
                     set [ TopLeft; Center; BottomRight ] ;
                     set [ TopRight; Center; BottomLeft ] ; ]

Now we need a little helper function that will allow us to find all the squares with particular contents, i.e. All Empty squares, all squares for X or all squares for O.

    let FindPositions (player: Player Option) (board: Board) =
        board
        |> Map.filter (fun _ mark -> mark = player) 
        |> Map.toSeq
        |> Seq.map fst
        |> Set.ofSeq

This looks a little involved, but it’s very simple. We filter the board (which you’ll recall is a Map from Position to Player Option). We look for all squares with a mark that matches the Player we are looking for. This will work whether we pass in X, O or None.

The filter returns another Map, we want to split the Keys (Positions) from the Values (X, O, None). We convert the Map to a Sequence of Tuples and then use fst to extract the Key part of each Tuple. Don’t let Map and map confuse you. Seq.map is just the plain old map function that you know and love.

What we ultimately want out of this is a Set so our last step is to convert our Sequence of Positions into a Set of Positions. With all that written, we can do the following.

    let Available = FindPositions None

Because we’re using Sets instead of Lists, our IsWin function is a little simpler than in the previous example. We no longer have to write functions to decide if a list contains another list. We can simply use the Subset behavior of Sets.

    let IsWin (player: Player) (board: Board) =
        let playersSquares = 
            board |> FindPositions (Some player)
        wins 
        |> Set.exists (fun win -> win.IsSubsetOf playersSquares)

And our IsDraw function is also simple. If a given position isn’t a win then it’s easy to check if it’s a draw, simply check if there is no where left to move. Note that both the Available and IsDraw functions use “Point-Free Syntax“.

    let IsDraw = Available >> Set.isEmpty

Another helper function now, for a given player we need a way of knowing the opponent, this will allow us to toggle back and forth between players as we search recursively for the best move.

    let Opponent = function
        | X -> O
        | O -> X

Actually making a move is just a matter of adding a mapping from a Position to a Player (or Some Player as Options would have us say).

    let Move (player: Player) (position: Position) (board: Board) =
        board.Add(position, Some player)

Note that the last argument to Move is the Board, and the function also returns a board. This allows us to use the following syntax.

        let pos = 
            NewBoard
            |> Move X TopLeft
            |> Move O TopMiddle
            |> Move X Center
            |> Move O TopRight

After running the code above, pos will be a board containing X in the Top Left and Center and O in the Top Middle and Top Right. The rest of the positions will be empty.

And now, the big step, the functions that actually do the work of funding best moves for a given Player faced with a given Board.

    let rec Score (player: Player) (board: Board) =
        if (IsWin player board) then board |> Available |> Set.count |> (+) 1
        else if (IsDraw board) then 0
        else 
            let opponent = Opponent player
            let opponentsBestMove = BestMove opponent board
            let newBoard = Move opponent opponentsBestMove board
            -Score opponent newBoard

    and BestMove (player: Player) (board: Board): Position =
        Available board
        |> Set.toList
        |> List.maxBy (fun m -> Score player (board.Add(m, Some player))) 

Apart from changes to use Sets and the new Move Syntax, this code is like that in the previous post.

There is one small but significant change. If the earlier code had a choice between a definite win in 1 move or in 2 moves it didn’t care which it took, both were definite wins. This led to it passing up winning moves and winning on the next move instead. It looked a little odd.

To solve this we change how we value wins. Instead of assigning a score of 1 to all wins, which we did in the last version of the code, the Score is now based on how many empty squares remain when the game ends. This makes quicker wins more valuable.

I kind of liked the way the previous implementation sometimes seemed to toy with its victim, so I wouldn’t necessarily call this fix an improvement.

Learning to Think Functionally: Recursion

This entry is part 11 of 11 in the series Learning to think Functionally

This post looks at a hugely important part of functional programming, Recursion. In simple terms this means writing a function that calls itself.

There are endless examples of using recursion to figure out Fibonacci numbers, or process lists. This post will be a little more complicated but hopefully is simple enough that you’ll be able to follow along.

We’re going to teach F# to play the perfect game of Tic-Tac-Toe. The game is a favourite for kids, but it quickly becomes boring for adults. The reason for this is that it is relatively easy to look ahead a few moves and play a perfect game. Writing a program that can look ahead and play perfectly is a nice little programming challenge, so let’s get to it.

Modelling The Tic-Tac-Toe Board
The first question we need to address is how to represent the board. A nine item array? Perhaps with 1, -1 and 0 for X, O and Blank respectively. That works.

Or we could just avoid modelling the board alltogether. Instead of updating a “Board” to mark the squares occupied by the players, we could just keep two lists of the claimed squares.

If we imagine a board layout like this

1 2 3
4 5 6
7 8 9

Then the following game position

X X O
. O .
X . .

can be represented as

X's Squares: [1;2;7]  
O's Squares: [5;3]

Some Helper Functions
Once we know how a positions are represented we can write functions to reason about them. From a given position we can find the list of squares that remain available.

let Available (player: int list) (opponent: int list) =
    [1..9]
    |> ExceptList (List.append player opponent)  

We combine the player and opponent lists into one list, then exclude that from the list [1..9]. What remains are the available squares. Simple. ExceptList is just a helper function that wraps a List.filter.

let ExceptList list = List.filter (fun n -> not (list |> Contains n))

That Contains function is another helper function, It’s just a cleaner way of doing a List.exists.

let Contains number = List.exists (fun n -> n = number)

Seeing A Win
The next question is how to we know if a player has won. Each player’s squares are in their own list, so all we have to do is check their claimed squares and see if any three are connected.

Yet again there are various ways of doing this, here’s a really simple way. There are only 8 sets of winning squares. The three rows, three columns and the two diagonals. If a players list of squares contains any of these 8 patterns then it’s a win.

let wins = [[1;2;3];
            [4;5;6];
            [7;8;9];
            [1;4;7];
            [2;5;8];
            [3;6;9];
            [1;5;9];
            [3;5;7]]

The IsWin function looks at each of the 8 win patterns and checks if any of them is contained in the players squares.

let IsWin (squares: int list) = 
    wins |> List.exists (fun w -> ContainsList squares w)

It uses another helper function ContainsList that checks if a list contains all of the elements of another list.

let ContainsList list = List.forall (fun n -> list |> Contains n)

A Draw is even easier to identify. If there are no squares left then it’s a draw.

let IsDraw player opponent = List.isEmpty (Available player opponent)

What’s a good move?
So, we know how to tell if the board shows a win or a draw, but how can we make our program look at a given position and decide on a good move. Let’s start by imagining that we have a function that can assign a score to a position. If such a function existed we could just get a list of available moves and pick the one with the highest score. Like This.

let BestMove (player: int list) (opponent: int list) =
    Available player opponent
    |> List.maxBy (fun m -> Score (m::player) opponent) 

List.maxBy applies the given function to each item in the list, and selects the item that gives the largest result. Remember the list contains available squares. The function combines each available move with the players current position and gets the score for each.

Now, what might the Score function look like?

let Score (player: int list) (opponent: int list) =
    if (IsWin player) then 1
    else if (IsDraw player opponent) then 0
    else ???

If the position is a win for the player we consider it to have a score of 1. For a draw we assign a score of 0. But, what if the game isn’t over yet? How can we score that position?

This is where we get into the realm of recursion. If we assume that both players will play their best possible moves from this position forward, we can predict how the game will end, that end position can then be used to score the current position. Let’s see that in action.

let rec Score (player: int list) (opponent: int list) =
    if (IsWin player) then 1
    else if (IsDraw player opponent) then 0
    else 
        let opponentsBestMove = BestMove opponent player
        let opponentsNewPosition = opponentsBestMove::opponent
        -Score opponentsNewPosition player

There are a few things going on here so let’s take them in turn. We need to figure out the best move for the opponent. We already have a function for that, the BestMove function that we started with. If we flip the opponent and player lists of squares around, we can use BestMove to find the best move from the opponents perspective.

Knowing the best move for the opponent we can add it to their current position. Now, we have a new position to score. It may be that the opponents move won them the game, or gives a draw. Or it may be that the game is still not finished. We have a function that can score those various options, in fact it’s the function we’re writing (Score), so we simply call it, passing it the opponents potential new position.

Note that if the Score function finds a win for our opponent it will return a score of 1. We negate that because a win for our opponent is a loss for us.

The key insight here is that while scoring the opponents position, the Score function will go back and forth between moves for the player and moves for the opponent. In parallel to the moves going back and forth, that negate operation means the score will go back and forth between 1 and -1.

Notice that we’ve added ‘rec’ to the Score function to indicate that it will be called recursively.

Mutual Recursion
Notice also that the Score function calls the BestMove function, which is the function we started with and which in turn calls Score. This is mutual recursion, and it poses a particular problem in F#. A called function must defined be above the call to it. How can we do that when we have two functions that call each other?

Well, like this…

	
let rec Score (player: int list) (opponent: int list) =
    if (IsWin player) then 1
    else if (IsDraw player opponent) then 0
    else 
        let opponentsBestMove = BestMove opponent player
        let opponentsNewPosition = opponentsBestMove::opponent
        -Score opponentsNewPosition player
        
and BestMove (player: int list) (opponent: int list) =
    Available player opponent
    |> List.maxBy (fun m -> Score (m::player) opponent) 

The ‘and’ keyword allows us to define mutually recursive function. So, here’s the finished code.

	
let wins = [[1;2;3];
            [4;5;6];
            [7;8;9];
            [1;4;7];
            [2;5;8];
            [3;6;9];
            [1;5;9];
            [3;5;7]]

let Contains number = List.exists (fun n -> n = number)

let ContainsList list = List.forall (fun n -> list |> Contains n)

let ExceptList list = List.filter (fun n -> not (list |> Contains n))

let Available (player: int list) (opponent: int list) =
    [1..9]
    |> ExceptList (List.append player opponent)  

let IsWin (squares: int list) = 
    wins |> List.exists (fun w -> ContainsList squares w)

let IsDraw player opponent =
    List.isEmpty (Available player opponent)

let rec Score (player: int list) (opponent: int list) =
    if (IsWin player) then 1
    else if (IsDraw player opponent) then 0
    else 
        let opponentsBestMove = BestMove opponent player
        let opponentsNewPosition = opponentsBestMove::opponent
        -Score opponentsNewPosition player
	        
and BestMove (player: int list) (opponent: int list) =
    Available player opponent
    |> List.maxBy (fun m -> Score (m::player) opponent) 

There you have it, 37 lines of code to create the perfect Tic-Tac-Toe brain. To run the code simply call the BestMove function, passing it the two lists representing the player’s squares. For the first move those lists will be empty.

	
> BestMove [] [];;
val it : int = 1

Remember that the first list passed to BestMove is the squares occupied by the player that is about to move, the second are the opponent’s squares. So, to find the best response to the move above, you would do the following.

	
> BestMove [] [1];;
val it : int = 5

The first move may take up to 30 seconds to find a move, it has to search the complete game tree. Subsequent moves will be significantly faster as the options get narrowed down.

Learning To Think Functionally : Readability

This entry is part 10 of 11 in the series Learning to think Functionally

I’m going to be a little unethical here and disclose an answer to Project Euler problem 6.

It’s one of the easier ones, but even still, if you haven’t done it, head on over and solve it now before reading any further. It’ll only take a few minutes.

Here’s the problem:

The sum of the squares of the first ten natural numbers is: 385
The square of the sum of the first ten natural numbers is: 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Simple, right?

Here are a few C# functions that give us the answer we need.

        static int Square(int n)
        {
            return n*n;
        }

        static int SumOfSquares(int first, int count)
        {
            var total = 0;
            for (var i = first; i <= count; i++)
                total += Square(i);
            return total;
        }

        static int SquareOfSum(int first, int count)
        {
            var total = 0;
            for (var i = first; i <= count; i++)
                total += i;
            return Square(total);
        }

We get the solution to the problem by subtracting one from the other:

SquareOfSum(1,100) - SumOfSquares(1,100)

Or, we take a more functional approach to the whole problem and use LINQ:

        static int Square(int n)
        {
            return n*n;
        }

        static int SumOfSquares(int first, int count)
        {
            return Enumerable.Range(first, count).Select(Square).Sum();
        }

        static int SquareOfSum(int first, int count)
        {
            return Square(Enumerable.Range(first, count).Sum());
        }

And we get result just as before:

SquareOfSum(1,100) - SumOfSquares(1,100)

Those Enumerable ranges are cool. I think it’s easier to figure out what’s going on than with the imperative example. That said, while it’s better, I’ve never found the readability of LINQ to be anything special. It’s ok.

Let’s look at the same code in F#

let square x = x * x
let sumOfSquares range = range |> List.sumBy square
let squareOfSum range = range |> List.sum |> square

And we can get our answer as follows:

squareOfSum [1 .. 100] - sumOfSquares [1 .. 100]

I think that reads a little better. You need familiarity with the concept of ‘mapping’ a List. If you’re using the C#/LINQ example above you probably know all you need to know.

Take a look again at the SquareOfSum function in the LINQ example. Reading left to right we encounter the call to Square first even though it happens last. This is quite common in imperative languages when functions calls are nested within function calls.

In F# the Forward-Pipe operator (|>) gets around that problem quite neatly.

We can go further with the F# example.

Since all we’re doing with those ‘range’ values is piping them into a chain of functions, we can get rid of them entirely and simply compose sumOfSquares and squareOfSum directly from List.sum, List.map and square.

let square x = x * x
let sumOfSquares = List.map square >> List.sum
let squareOfSum = List.sum >> square
squareOfSum [1 .. 100] - sumOfSquares [1 .. 100]

Out sumOfSquares and squareOfSum functions are now “Point Free” in Functional Programming parlance.

Enriching Data with F#

Download Sample Project 4.1 KB

Let’s say I’ve pulled some raw data from a normalised database. It might look something like this:

type RawEmployee =
    {
        EmployeeId: int
        DepartmentId: int
        RegionId: int
        GradeId: int
    }

Lots of foreign keys, not much by way of useful information. Let’s say I’d like to turn it into something like this:

type EnrichedEmployee =
    {
        Name: string option
        Department: string
        Region: string
        Grade: string
    }

Notice Name is a string option which means it’s valid to not have one. Gotta love crazy internet examples. The rest of the fields are strings, they are mandatory.

How do I get from the raw record to the enriched record using something close to clean code?

I’ve tackled variations of this problem and seen it tackled by others, many times in many languages. The results are rarely encouraging. One common pattern is very specific complicated enrichment functions with tons of null checks and if…else littered all over the place. The other extreme (and much worse) is some kind of elaborate generalised enrichment framework with creatures like AbstractEnrichmentFactories and EnrichmentStrategyFactoryFactories lurking around every corner.

My latest effort in this area was for an FSharp project. Here’s how I wanted the finished code to work.

1. I wanted the individual enrichments to be simple functions than I can chain together, perhaps in a list.

let functions = [EnrichName; EnrichDepartment; EnrichRegion; EnrichGrade]

2. I wanted enriching a raw record to be as simple as possible. We’ll figure out how to get the enrichment functions in there later.

let e = EnrichAnEmployee rawEmployee

3. I wanted to be able to enrich a list of raw records as easily as a single record.

let e = EnrichEmployees rawEmployeesList

4. I wanted optional fields so even if their enrichment fails the overall enrichment continues.

5. I wanted mandatory fields, so, if their enrichment fails the overall result is None rather than an EnrichedEmployee.

6. I’d like to not have to completely reinvent this solution for every new type that I want to enrich, but I also don’t want tons of reusable infrastructure code that is difficult to understand.

What follows is a first stab at this, I can already see a few ways it can be cleaned up, but here you go.
Lets start with a couple of simple lookup functions for resolving IDs to values. We’ll hard code everything for the purposes of this post. A couple of Lists of Tuples should do.

let names = [1,"Richard"; 2,"Tony"; 3,"Tom"]
let departments = [1,"IT"; 2,"HR"; 3,"Finance"]
let regions = [1,"North"; 2,"South"; 3,"East"; 4,"West"]
let grades = [1,"Junior"; 2,"Senior"; 3,"Principal"]

Next we need our actual Enrichment functions, these will use the data above to resolve some field on the raw record to update the enriched record.

let EnrichName (r: RawEmployee) (e: EnrichedEmployee option) = 
    match List.tryFind (fun i -> fst i = r.EmployeeId) names with
        | Some s -> Some {e.Value with Name = Some (snd s)}
        | None -> e

let EnrichDepartment (r: RawEmployee) (e: EnrichedEmployee option)  =
    match List.tryFind (fun i -> fst i = r.DepartmentId) departments with
        | Some s -> Some {e.Value with Department = snd s}
        | None -> None 

let EnrichRegion (r: RawEmployee) (e: EnrichedEmployee option) = 
    match List.tryFind (fun i -> fst i = r.RegionId) regions with
        | Some s -> Some {e.Value with Region = snd s}
        | None -> None 

let EnrichGrade (r: RawEmployee) (e: EnrichedEmployee option) = 
    match List.tryFind (fun i -> fst i = r.GradeId) regions with
        | Some s -> Some {e.Value with Grade = snd s}
        | None -> None 

Note that for Department, Region and Grade if we don’t find a match, the result of the function is None, but for Name if we don’t find a match, the result is e which is the Enriched record, passed on, untouched.

Let’s see all this in action. First we need the ingredients. A list of the enrichment functions we want to apply. A blankEmployee which is the starting point for the enrichment process, and some raw data to enrich.

let functions = [EnrichName; EnrichDepartment; EnrichRegion; EnrichGrade]
let blankEmployee = Some {Name = None; Department = ""; Region = ""; Grade = ""}

let rawEmployees = [{ EmployeeId = 1; DepartmentId = 1; RegionId = 1; GradeId = 1 };
                    { EmployeeId = 4; DepartmentId = 2; RegionId = 2; GradeId = 2 };
                    { EmployeeId = 3; DepartmentId = 3; RegionId = 3; GradeId = 3 };
                    { EmployeeId = 1; DepartmentId = 4; RegionId = 2; GradeId = 3 };
                    { EmployeeId = 2; DepartmentId = 3; RegionId = 4; GradeId = 3 }]

Now through the magic of currying we create the actual function that will apply our list of functions to Enrich an Employee.

let EnrichAnEmployee = Enrich functions blankEmployee

Where did that Enrich function come from? What does it do? Well, that’s the function that actually does all the magic, I haven’t shown it to you yet, but for now lets press on with the cart before the horse and see what it does, we’ll see how it does it shortly.

Having used the magical Enrich function to create the EnrichAnEmployee function we can use that function as follows

let e = EnrichAnEmployee { EmployeeId = 1; DepartmentId = 1; RegionId = 1; GradeId = 1 }

We can also use it to create a function that will enrich lists of raw Employees

let EnrichEmployees rawList = List.map (fun r -> EnrichAnEmployee r) rawList
let e = EnrichEmployees rawEmployees

Let’s look at the heart of all of this, the Enrich function. It’s actually two functions

let IfSome (f:'e option->'e option) (x: 'e option) =
    match x with
    | Some n -> f x
    | None -> None

let Enrich (functions: ('r -> 'e option -> 'e option) list) (enriched: 'e option) (raw: 'r) =
    let funcs = List.map (fun f -> IfSome (f raw)) functions
    List.fold (fun acc f -> f acc) enriched funcs

Ok, it’s not the prettiest code in the world but that’s mainly down to being explicit about the types of arguments. As Infrastructure Code goes it’s not too bad. For starters there’s only about 10 lines of code to understand. Let’s break it down.

The Enrich function takes three arguments

  1. The list of enrichment functions
  2. The blank employee which is the starting point for the enrichment.
  3. The raw employee record that we want to enrich

Inside the function we do something that you can really only do when functions are truly first class citizens. We first Map the list of functions to essentially bolt on some extra behaviour and turn them into other slightly modified functions, and then we do a Fold to execute the functions in turn and produce a result.

The extra behaviour we bolted on when we mapped the functions is to handle the fact that the output of these functions is an option and so might be a None. If that is the case we don’t want subsequent functions trying to enrich it further.

We basically stick a proxy IfSome function in front of each of our enrichment functions so that it
can intercept any None’s and not bother calling the function.

If you’re having any trouble untangling how the Enrich or IfSome fuctions do their work then drop me a comment below and I’ll go into it in more detail.

You can also download the code and play with it.

Download Sample Project 4.1 KB

A next step that we could take would be to have the enrichment function return more than just an enriched employee. It could return a tuple containing both the enriched Employee and a list of strings or exceptions to capture problems.

E.g instead of getting None we could get (None, [“Department 4 does not exist”]).

This means we can tag the results of the enrichment without polluting the results themselves with exceptions and warnings.