Navigate / search

Active Patterns: Partial Application

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

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: Single Total (|A|)

Part 1 of this series was mainly sharpening the axe by covering some basics like Pattern matching. I also gave a general sense of what active patterns are (functions that can be used when pattern matching, such as in match expressions). Now it’s time to dig into the details.

As I mentioned previously there are arguably 5 variations of active patterns. This post will cover the first of those, the Single Total Active Pattern.

When we looked at plain old pattern matching we extracted and matched against values that were already there, by which I mean matching against a tuple like (21, 8, 2014) allowed us to match on the values 21, 8 and 2014 or any combination of them, but we couldn’t match against a values like ‘August’ or ‘Leap Year’.

Active Patterns allow us to do just that, we can take an input, transform it in some way and then match against the result of that transformation.

Let’s try a simple example.

let (|UpperCaseCount|) (str: string) =
    str.ToCharArray()
    |> Array.filter (fun c -> c.ToString() = c.ToString().ToUpper())
    |> Array.length

let UseThePatternLuke (str: string) =
    match str with
    | UpperCaseCount 4 -> "Bingo 4 is the magic number"
    | UpperCaseCount u -> sprintf "Nah %d upper case characters is no good" u

Active Recognizers
The first thing to note is the highlighted line. In particular those funny parenthesis around (|UpperCaseCount|). Those (|…|) are “banana clips” and they denote a special kind of function known as an ‘Active Recognizer’. These functions do the heavy lifting for Active Patterns. They accept the source data, break it up, transform it and output it in a form that can be matched against.

From the perspective of match expressions and assignments the pattern matching works exactly like the plain old pattern matching we saw in the last post. The difference with Active Patterns is that the Active Recognizer function has gotten in and transformed the data before the matching happens.

The”banana clips” above only enclose one value so this is a Single Total Active Pattern.

The significance of this will become more apparent when we look at the remaining kinds in subsequent posts.

We’re matching against a string, but the property of the string we’re interested in is the number of upper case characters. So, we define an active recognizer that takes a string, and returns the number of upper case characters.

Apart from those Banana Clips it looks like an ordinary function. I’ve mentioned in previous posts that the Single Total Active Pattern can be a little hard to explain because simply using a function almost always seems like a better idea. If you’re skeptical, stay with me (I’ve been there).

For simple pattern matching, there’s just the “match x with” code, or the destructuring assignment. For Active Patterns you define the active recognizer separate from the pattern match. Basically you pull some logic out into it’s own function. Nothing magical.

Here’s the same code with some scribbles to try and convey the relationship between the active recognizer and the pattern matching.

And here, after much head-scratching is an attempt at an example which is simple enough for anyone to understand, but where just using functions might not have been as clean.

let (|IsPalindrome|) (str: string) =
    str = String(str.ToCharArray() |> Array.rev)

let (|UpperCaseCount|) (str: string) =
    str.ToCharArray()
    |> Array.filter (fun c -> c.ToString() = c.ToString().ToUpper())
    |> Array.length

let (|LowerCaseCount|) (str: string) =
    str.ToCharArray()
    |> Array.filter (fun c -> c.ToString() = c.ToString().ToLower())
    |> Array.length

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


let (|IsValid|) (str: string) =
    match str with
    | UpperCaseCount 0 -> (false, "Must have at least 1 upper case character")
    | LowerCaseCount 0 -> (false, "Must have at least 1 lower case character")
    | SpecialCharacterCount 0 -> (false, "Must have at least 1 of !£$%^")
    | IsPalindrome true -> (false, "A palindrome for a password? What are you thinking?")
    | UpperCaseCount u & LowerCaseCount l & SpecialCharacterCount s -> (true, sprintf "Not a Palindrome, %d upper case, %d lower case and %d special characters. You're good to go!!!" u l s)

I’ve actually defined a couple of different Active Recognizers, each of which transform the string in different ways. The pattern match can then use any combination of the four patterns.

We can match against literal values like true and 0, or we can match against variables as in the last case.

The highlighted line shows one of the real advantages of active patterns over simple functions. We call three functions, store the returned values and use them, all in one line.

Actually I was a little cheeky, even my IsValid “function” is actually an Active Recognizer, I can use it as follows

let checkPassword (password: string) =
    match password with
    | IsValid (true, _) -> "OK"
    | IsValid (false, reason) -> reason

This would also work

let checkPassword (password: string) =
    match password with
    | IsValid (false, reason) -> reason
    | _ -> "OK"

One final quirk of the Single Total Active Pattern is that you can use it like this.

> let (IsValid result) = "$TArAT$";;

val result : bool * string =
  (false, "A palindrome for a password? What are you thinking?")

The value on the right of what looks like an assignment is sent to the Active Recognizer, and the result of the Active Recognizer is then bound to the variable ‘result’.

What’s going on here is simply the same Destructuring Assignment we saw in the first post, but using an Active Pattern instead of simple Pattern Matching. For more on this, and on the Single Total Active Pattern I strongly recommend Luke Sandell’s excellent (and concise) blog post.

Don’t get too hung up the Single Total Active Pattern. In many cases a simple function will work and be as clear or maybe even clearer than the Active Pattern equivalent.

That said, understanding what’s going on with this type of Active Pattern will make it very easy to grasp the rest, and once you know how to use a new tool, it becomes easier to see places where it can work.

Active Patterns: Pattern Matching

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.

My 5 Biggest Mistakes

You can’t work in this business for very long before the hope, idealism and intellectual curiosity is beaten out of you and replaced with TPS Sheets, and 15 different tools for telling your colleagues how to configure IIS so that your app will actually run on their machine.

If you’re new to this business there may still be time to save yourself. Go drive a truck, or learn a bit about your city and become a tour guide. On the off chance that you are determined to stay in software development here are my top 5 mistakes, maybe you can avoid some of them.

5. Thinking that things I am unfamiliar with are Bad
Us software developers generally have a well cultivated sense of your own ability to reason about things without actually trying them. We are professional generalisers after all.

“I don’t need to install Linux to know it’s shit”

“LINQ is unreadable”

“No, I don’t use ‘var’ I need to know my types”

At one point I had very strong arguments against var. A colleague tried to make me see the light but couldn’t. Then one day, Eureka, I got it. It was never about ‘var’. In my head the debate was “Save a few keystrokes, at the cost of not having the types in your face”. I thought I needed the types and saving keystrokes wasn’t a priority.

What I didn’t get was that getting rid of the in your face types wasn’t the price, it was the point. The saved keystrokes were incidental. It was never about keystrokes, it was about abstraction. In the same way LINQ wasn’t about writing LESS code, it was about writing code at a higher level of abstraction.

This is different from the static vs dynamic types debate which is a whole other issue, but I know now that I don’t know enough to have a very strong opinion on dynamic types.

Before you reject something as useless or bad, make sure you get the point. Your preconceptions about why a technology exists might be a million miles from the reality.

4. Thinking that things I am familiar with are Good
This is the flip side of the point above but in many ways it’s more damaging. We have a tendency to think the things we are familiar with are the solution to every problem. You can waste a lot of effort and creativity trying to figure out how to press flowers with a hammer because a hammer is what you know.

3. Thinking there’s a right way
When I started building software I was convinced there was a right way to do it. If I could figure it out I could carve out a nice career following my process.

There is no right way. Give up on finding the best way to build software, or even dividing processes, tools, techniques into Good/Bad. It’s wasted effort. One persons good technique will sink another person’s project. One person’s horrible hack will save another person’s project.

2. Thinking that I could learn software development from books
I spent wasted so much money on books. I recently threw a lot of them away. In my defense when I was learning this business the internet was in it’s infancy and there wasn’t a huge amount of curated material out there. Books were how it was done.

Even still, I bought far too many.

I did read a lot of them and I learned a lot from them but I didn’t learn how to develop software. I learned some ideas that could be applied. I could have saved a lot of money by not buying and a lot of time by not reading quite so many books. I could have spent that time actually building more software and more varied software.

Blogs, Screencasts, Online Training are the new Books. I think there’s a danger of replicating similar mistakes, spending too long thinking about software development as a theoretical pursuit, and leaving too little time to build stuff.

You’re making this mistake right now. You think that maybe there’s some insight here that will make you a better software developer. There probably isn’t. Go write some code.

Hey, at least you didn’t spend 40 $/£/€ to be here.

1. Thinking it all someone else’s fault.
If you work as a software developer you will work on a lot of teams and unless you are really lucky, most of them will be terrible. At least they will be terrible from your perspective.

Most software development is terrible. It’s frustrating, it’s unreliable. It’s difficult. It’s tedious.

It’s easy to assume that this is all someone else’s fault. There are solutions if people would just adopt them.

There really aren’t. Everyone including you is trying to figure out how to build software and make things less frustrating. The problem is that one person’s solution is the very thing that frustrates the hell out of you. And it works both ways. Do you have any idea how frustrating it must be for a project manager to have a coder tell them that estimates are useless.

I’m fully conscious of how frustrating it must be to work with me.

I don’t have any magic answer on this point other than to realize that none of us really have THE ANSWERS. It’s probably better to have a team full of people who know that then a team full of people with their own ideas, all of whom think they are right.

Of course there’s no point recognizing this fact if no one else on the team does, so you may have to take yourself out of that situation, and look elsewhere, but at least you’ll know what you’re looking for.

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.

Stop focusing on Agile, fly the damn plane

Constant Learning
Being a software developer means constant learning. The technical landscape is always shifting. We have to run to stand still. We know this. We accept it. For some it’s the very thing that attracts them to the profession.

I’ve learned lots about software development in the last few years.

  • How to automate builds
  • How to automate tests
  • Object Oriented Programming/Design
  • Functional Programming/Design
  • Operating Systems
  • Programming Languages
  • Frameworks
  • Version Contol Systems

I’ve tried to embrace Agile, hell I’m even a certified Scrum Master. I attend conferences, speak at conferences, read lots and blog a little.

Despite all this I feel I am a worse “Software Developer” than I used to be. Which can be partly explained by this quote from John Archibald Wheeler.

“We live on an island surrounded by a sea of ignorance. As our island of knowledge grows, so does the shore of our ignorance.”

In other words, the more you learn, the more stupid you feel.

This, combined with the Dunning-Kruger effect suggests that feeling like we’re getting worse, even as we get better might be understandable.

But that’s not it. It would be great to explain this all away, pretend it’s all in the mind, but I don’t think it is. I believe I am actually a worse developer now than I used to be. Less productive, less focused, less comfortable.

And, I think I know why.

Fly The Plane
In an emergency pilots are trained to remember that their first priority is to “fly the plane”. It may seem odd that they need to be reminded of that fact, but it’s incredibly easy to become focused on an instrument that doesn’t work and forget to keep the plane in the air. On December 29th 1972 Eastern Air Lines Flight 401 crashed into the Florida Everglades with 101 fatalities. The flight crew were all focused on a burned out landing gear bulb and failed to notice that the autopilot wasn’t maintaining altitude.

They weren’t bad pilots, or bad people, they made a mistake, a mistake that we all make, all the time. The consequences of focusing on an immediate issue, forgetting to fly the plane, trusting that the autopilot had their back was catastrophic. They paid the ultimate price.

The consequences to the rest of us of making a similar mistake are far more benign, but there are consequences. I don’t think I’m alone in letting a focus on “building software the right way” distract from the real job of “building software”.

For me, it all started to go wrong when I started learning TDD.

Devouring everything I could read about TDD gave me a glimpse of an Agile world, of continuous integration, continuous deployment, executable specifications, distributed version control systems and feature branches. A world where the software development process worked. A magical place where you could pick requirements off the trees and working software flowed like a mighty stream.

Knowing that such a magical place existed became a curse. It made me resent the daily frustrations that have always blighted software developers. It made me feel bad every time I wrote code that didn’t have tests. It made me obsess over design and clean code to the point that sometimes I froze unable to move forward, It made me waste hours trying to automate things that absolutely needed to be automated, but not at the cost of shipping software.

Tools Tools Tools
The Agile manifesto proposes “Individuals and interactions over processes and tools”. And yet, processes and tools are deployed in ever growing numbers in an attempt to “be agile”. I’ve spent a huge chunk of my time on tools like Team City, Jenkins, Git, Subversion, Testrail, Rally, Jira, FitNesse, RSpec, NUnit, Vagrant, Puppet, VirtualBox, and all that before we even get to a programming language.

You can study all of those tools, learn about 20% of each of them and still not know a damn thing about delivering software other than it’s really hard to get tools to talk to each other.

A Call to Action
Here’s what I’ve started doing, and if my sorry tale sounds familiar you might like to join me.

Stop.

Go and build a product. Any product, but make it a complete product, it can be small but it must actually do something. I’ve started with a tool to rank the pool players in our office using Elo Ratings.

Don’t use any tools other than your IDE.

Open up Visual Studio or RubyMine or whatever and build a product.

Don’t write unit tests, don’t automate the build or the deployment. Don’t try to be agile.

When you have a fully working product, build another, and another, or built the same product again.

Forget the Red-Green-Refactor Rhythm, get into the rhythm of building working products, not functions, not programs, “Products”. Don’t just throw any old crap up and call it a product, apply a little polish. Pretend you are delivering for a client. Start by delivering the core value of the product and then improve it.

Do as much as possible manually so that you get your mind back to the bare bones of building software. What do you actually need to do?

Get faster at delivering. You should be able to build a small app in a few hours. Build the same app multiple times, Katas don’t have to be about Test Driven Development of tiny functions. Do a “Ship A Product” Kata, build a product in an hour, by hand, then throw it away and build it again.

Once you’ve got that rhythm going then, AND ONLY THEN, add in an automated build. When you’ve got that working then AND ONLY THEN add in automated tests.

For my first stab at this I didn’t even use version control, I put the code in dropbox.

Don’t do anything because “It’s the right thing to do, or it’s agile”, only do things because you can see that it makes sense, makes you faster, makes life easier, solves an ACTUAL problem.

Minimum Viable Product
Working Software is the minimum viable product from your software development process. An automated build that delivers nothing is just wasted time. You can spend a long time creating an all encompassing Walking Skeleton and never start on the product.

Focus on actually completing some small products. Figure out what you really need. Evolve your Walking Skeleton from first principles.

This isn’t an anti-agile or anti-tdd post. Quite the opposite. We need to take an agile approach to being agile. Working software is our green light, that’s the baseline. If adopting any agile practice hinders your ability to deliver working software then revert, get back to green and try again, or try something else.

Learning to Think Functionally: Recursion

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.