Navigate / search

One Less Thing To Worry About

In the closing scene of the movie Forrest Gump, we learn that Lt. Dan helped Forrest invest in some kind of “Fruit” company (Apple Corp.).

“So then I got a call from him, saying we don’t have to worry about money no more. And I said, that’s good! One less thing.”

That quote comes to mind whenever I think about immutability.

Let’s make a list of Int’s and display it.

    var numbers = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    Console.WriteLine(string.Concat(numbers));

    Result: 123456789

Now, let’s reverse the list. In CSharp lists are mutable so we can do the following:

	var numbers = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	numbers.Reverse();
    Console.WriteLine(string.Concat(numbers));

    Result: 987654321

If we just wanted to show the numbers in reverse order, but keep the underlying list in order, this wouldn’t work. The Reverse method screws with our underlying data. The following would be nice.

	var rev = numbers.Reverse();

It’d be great if rev now pointed to a reversed list while numbers was still in order. That would be how an Immutable List would work, the Reverse method wouldn’t change anything, it would create a new List.

The result of the List object does the same, if you Sort, you sort the underlying data, you don’t get a new list. Add or Remove items, you change the underlying list.

There is a solution. There is an ImmutableList, just find Microsoft.Bcl.Immutable in Nuget and use System.Collections.Immutable, and you’re all set.

Except that’s a little problematic too. You lose that nice initialisation syntax that the old mutable list had.

	var numbers = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

Under the hood CSharp relies on mutability to make that magic work.

So, you need to use NuGet and you need to write extra code, and all to stop you accidentally mutating a list. This is never going to be the default choice for CSharp developers.

IEnumerable
There is another choice, if we call the Reverse method as follows, we get the behavior we want.

	 rev = numbers.AsEnumerable().Reverse();

Problem solved. Well no. There’s an even bigger problem. Thanks to Jonas Elfström for writing up this post on IEnumerable.

Take a look at this code and see if you can figure out where the result comes from.

    var numbers = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    var rev = numbers.AsEnumerable().Reverse();
    numbers.Reverse();
    Console.WriteLine(string.Concat(rev));
    Console.ReadKey();

    Result: 123456789

As Enumerable isn’t really giving you immutable behavior. The variable ‘rev’ is still pointing to the same underlying data, just through the lens of a lazy operation. The AsEnumerable().Reverse() won’t happen until we use the results. Which means reversing the underlying numbers will cause them to be reversed back again when we eventually use the IEnumerable view of it.

This is why I would prefer data structures that are immutable by default. You avoid this kind of silliness. I’m sure many will have no problem whatsoever with the example above, but I find it annoying, unintuitive and confusing.

In CSharp I never get to put mutability aside as one less thing to worry about. You have to work really hard to make anything immutable, really immutable.

There is a place for mutable data structures and a place for immutable data structures. It seems logical to me that if one has to be harder work than they other, immutable should be the easier of the two. It should be the default.

The challenge today is overwhelming complexity

Here’s a really great post by Tom Moertel on squeezing every last ounce of performance out of machines back in the day.

It was a time when unrolling a loop to save the few clock cycles or seeing a unique way to use the registers of a chip could take a game from clunky to classic.

Stories of making machines do the impossible are the stuff of legend. The closest we mere mortals came was rejigging our config.sys and autoexec.bat files to free up a little memory. If you’re under 30 even that may sound alien.

Tom’s post is a great read, but there is a real gem of wisdom towards the end, under the heading “To the old days!”.

“The challenge wasn’t overwhelming complexity, as it is today. The challenge was cramming your ideas into machines so slow, so limited that most ideas didn’t fit.”

Turn that quote around. The challenge today isn’t cramming your ideas into machines so slow so limited that most ideas don’t fit. The challenge today is overwhelming complexity.

The challenge today isn’t cramming your ideas into machines so slow so limited that most ideas don’t fit. The challenge today is overwhelming complexity.

I would guess that at this point less than 5% of developers ever need to sacrifice maintainability for performance. I’m probably being generous at that. If you are taking on complexity in order to speed up the execution of a method, or reduce it’s memory footprint, you’re more likely doing harm for no good reason.

But, this post isn’t about code. It’s all too easy to focus on “Clean Code”, have code reviews, refactor relentlessly etc. But, if you deploy that code into an overly complex environment, or using an unnecessarily complex infrastructure, or manage the whole thing using unnecessarily complex ceremony then your code cleaning efforts may be wasted.

It’s interesting how many books are available on how to write “good code”, or how to refactor “bad code”, but there are relatively few if any books about refactoring “bad environments”.

Refactoring should extend to the entire development process. If you can refactor away an unneeded Class, but can’t get rid of an unneeded tool, you’re on the road to ruin. No amount of intention revealing Interfaces or SOLID code will save you.

The phrase “Technical Debt” has been coined to mean the deliberate taking on of subpar “code”, with a view to fixing that problem later. I don’t believe it’s a satisfactory definition.

All too often “Technical Debt” means “We have this one line fix, we’ll come back later and implement it correctly in all of the Controllers, Views and Models that should be affected. I wonder about the logic of treating a change in multiple places as preferable to making a change in one place.

I also wonder whether that one liner change is where time will be lost in maintenance. Even if there is a more “correct” way of fixing an issue, is the code really where your team is losing productive hours?

Or, is it the time needed to set up a development environment? Or figure out how to find a test environment that’s “close enough” to production to be useful. Perhaps you have so many tools that nobody really understands how everything fits together any more.

If there is a “Knack” to getting your code base to build, then clean code is the least of your problems.

When the complexity of the solution exceeds the complexity of the problem, THAT’s technical debt. By “solution” I mean the WHOLE package. Code, Tools, Frameworks, Process, Infrastructure, Documentation, Planning, Review.

Very few of us need to find “clever” solutions any more. The capabilities of machines far exceed almost anything we could possibly want to do. The challenge now is complexity and we should be devoting a lot more of our attention to it.

Active Patterns : Choices and Nesting

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

And so, we arrive at the last post of the series. I’ll show you the F# ‘Choice’ type and show how it relates to active patterns. I’ll explain how to add additional parameters to a multi-case active pattern, and introduce some complex pattern matching using nested active patterns.

Look Ma! No Params
In the previous post I mentioned that Multi-Case active patterns can’t accept additional arguments beyond the one that all active patterns must accept. Here’s what the code might look like if they could.

let (|Smaller|Equal|Bigger|) (compareWith: int) (n: int) =
    if n < compareWith then Smaller
    elif n > compareWith then Bigger
    else Equal

let DescribeNumber (n: int) =
    match n with
    | Smaller 10 -> "Small"
    | Bigger 10 -> "Bigger"
    | Equal 10 -> "Equal"

On the face of it that looks like reasonable code. To see why it’s invalid, let’s change the DescribeNumber function slightly.

let DescribeNumber (n: int) =
    match n with
    | Smaller 5 -> "Small"
    | Bigger 10 -> "Bigger"
    | Equal 10 -> "Equal"

Assuming we could do this, what should happen if we pass the number 7 to DescribeNumber?

The first clause won’t match, because 7 is not smaller than 5. The second and third clauses won’t match either because 7 isn’t bigger than or equal to 10. So, we’ve taken a multi-case pattern, where they whole point is the completeness of the pattern matching, and we’ve broken that completeness by parameterizing each clause separately.

If you try this code out you’ll find that the error isn’t in the Pattern Recognizer, it’s in DescribeNumber. In other words, it’s fine to define a multi-case active pattern, as long as you don’t try to pattern match on it. That offers us a clue as to how to proceed.

let (|SmallerThan10|EqualTo10|BiggerThan10|) = (|Smaller|Equal|Bigger|) 10

If we partially apply the Active Pattern, locking in a value for the additional parameter, we’re back to a multi-case active pattern with one parameter. And our pattern match now looks like this.

let DescribeNumber (n: int) =
    match n with
    | SmallerThan10 -> "Small"
    | BiggerThan10 -> "Bigger"
    | EqualTo10 -> "Equal"

The original function has the values Smaller, Equal and Bigger and the partially applied version has SmallerThan10, EqualTo10 and BiggerThan10. Which begs the question, how does one map to the other? Is it just their positions?

Well, yes, that’s exactly how it works, but for an interesting reason that explains a lot about Multi-Case Active Patterns. Go back and take a look at the signature of the original active pattern.

val (|Smaller|Equal|Bigger|) :
  compareWith:int -> n:int -> Choice<unit,unit,unit>

It returns a Choice

Give me Choice
Just as the Option type allowed us to write functions that can return either ‘Some value’ or ‘None’. The Choice type allows us to return one of up to seven values (remember that seven item limit on multi-case active patterns?).

Forget about Active Patterns for a moment and look at this plain old function.

let Divide (by: int) (this: int) =
    if by = 0 then Choice1Of3 "You can't divide by zero, are you mad?"
    elif this % by = 0 then Choice2Of3 (this/by)
    else Choice3Of3 (decimal this/decimal by)

It’s type is as follows

val Divide : by:int -> this:int -> Choice<string,int,decimal>

Depending on the numbers you try to divide, this function will return one of three choices. A string (an error message for divide by zero), an int (numbers divide evenly), or a decimal (doesn’t divide evenly.)
We can pattern match on this function just like we do with Multi-Choice Active Patterns.

let DescribeDivide (this: int) (by: int) =
    match Divide this by with
    | Choice1Of3 error -> error
    | Choice2Of3 n -> sprintf "%d divides evenly by %d and the result is %d" this by n
    | Choice3Of3 n -> sprintf "%d doesn't divide evenly by %d and the result is %f" this by n

It may be starting to dawn on you now that the Multi-Case Active Pattern is a way of assigning names to those choices. In fact, if you take any function that takes a single argument and returns a Choice you can turn it into a Multi-Case Active Pattern, and call the various possibilities anything you like.

The following example partially applies the Divide function, the result is a Choice which can be turned into a multi-choice active pattern, and used immediately in a pattern match, all within a single function.

let DescribeDivide (by: int) (this: int) =
    let (|ByZero|Evenly|NotEvenly|) = Divide by
    match this with
    | ByZero error -> error
    | Evenly n -> sprintf "%d divides evenly by %d and the result is %d" this by n
    | NotEvenly n -> sprintf "%d doesn't divide evenly by %d and the result is %f" this by n

With all that in mind look again at the partially applied Multi-Case Active Pattern from above.

let (|SmallerThan10|EqualTo10|BiggerThan10|) = (|Smaller|Equal|Bigger|) 10

The signature of the original Active Pattern is

compareWith:int -> n:int -> Choice<unit,unit,unit>

Partially applying it we get a new function with the following signature

int -> Choice<unit,unit,unit>

One input parameter, and the out put is a Choice Of 3, so we can assign this to any Multi-Case Active Pattern name as long as it has 3 cases, in our example (|SmallerThan10|EqualTo10|BiggerThan10|).

Code Quotations
For this final example I need a reasonably elaborate domain model. Instead of creating a phony one, I’m going to use F# itself. Code Quotations provide a model for working with F# code as Data. The point of this example is to convey that even after 8 posts explaining Active Patterns in detail, there is still enormous scope to combine and use Active Patterns in interesting ways.

let model = <@ fun (x: int) -> x * x @>
val model : Expr<(int -> int)> = Lambda (x, Call (None, op_Multiply, [x, x]))

The quoted expression is a lambda that takes an integer x and squares it. The quotation determines that we have an int->int expression. Without getting too bogged down in the syntax, you should be able to see that it’s a Lambda that accepts a variable x and calls a multiply operation, passing two arguments, both of which are x.

OK, now you’re up to speed on Code Quotations, or as up to speed as you’re going to get from this post. It might be worth having a quick read of this page before continuing.

Here are some Namespaces we’ll make use of.

open Microsoft.FSharp.Quotations
open Microsoft.FSharp.Quotations.Patterns
open System.Reflection

That Patterns namespace will come in handy. Code Quotations come with a set of ready made Active Patterns. The following example uses two supplied patterns. ‘Call’ matches method calls, and ‘Value’ matches values. Both are Single Partial Active Patterns.

let rec Describe (expr: Expr) =
    match expr with
    | Call (_,f, left :: right :: []) -> sprintf "%s %s %s" (Describe left) f.Name (Describe right)
    | Value (v, t) when t.Name = "Int32" -> sprintf "%A" v
    | _ -> "?"

This function matches on method calls and values. It will fail to match on any other expression. The Call active pattern returns a three part tuple. We don’t care about the first part, the second part is the function that is called, which we bind to the name f. The third part of the tuple contains the list of arguments. We’ll match on calls that have exactly two arguments, and we bind them to the names left and right.

We’ll also match on values. The Value Active Pattern returns a tuple containing the value and the type. We bind the names v and t to those respectively, and we’ll only match if the type is ‘Int32’.

We add printing of the results and we get the following.

let desc = Describe <@ 2 - 1 * 5 - 3 @>
val desc : string = "2 op_Subtraction 1 op_Multiply 5 op_Subtraction 3"

OK, it ain’t pretty, but hopefully you can see how the Active Patterns are working. If we throw something other than integers at it, we won’t match the values.

let desc = Describe <@ 2.0 - 1.0 * 5.0 - 3.0 @>

val desc : string = "? op_Subtraction ? op_Multiply ? op_Subtraction ?"

Nesting
Now let’s have some fun. We’ll need to create two Active Patterns.

let (|MethodWithName|_|) (s:string) (m: MethodInfo) =
    if s = m.Name then Some() else None

let (|TypeWithName|_|) (s:string) (t: System.Type) =
    if s = t.Name then Some() else None

The first pattern accepts a string and a MethodInfo and matches if the method has the name we provide. The second does the same, but with the name of a Type.

Here’s where things get interesting, the second element of the Tuple returned by the Call Active Pattern is a MethodInfo, which means we can pass it to this new Active Pattern. Like this.

let rec Describe (expr: Expr) =
    match expr with
    | Call (_,MethodWithName "op_Multiply", [left; right]) -> sprintf "%s %s %s" (Describe left) "*" (Describe right)
    | Call (_,MethodWithName "op_Subtraction", [left; right]) -> sprintf "%s %s %s" (Describe left) "-" (Describe right)
    | Value (v, TypeWithName "Int32") -> sprintf "%A" v
    | _ -> "?"

We’ve nested a match on specific method names within matches on method Calls. This will now only match on calls to op_Multiply and op_Subtract. Knowing this we can describe the methods with their operators ‘*’ and ‘-‘ rather than the ugly full method names.

I did the same with the ‘TypeWithName’ active pattern and removed the ‘When’ clause in the process.
Let that sink in. You can use an active pattern to match on values returned from another active pattern. You don’t need a whole separate ‘match .. with’ expression.

I’ve only scratched the surface of nested types, for a much more detailed discussion this talk by Ross McKinlay is heavy going in places but really showcases the power of Active Patterns.

That’s all folks
That’s it for this series. I hope you found it worthwhile. We’ve covered an enormous amount of information. If you’ve managed to work through the entire series of posts you should be fully comfortable with Active Patterns. All that remains is the put them to good use.

Thanks for reading.

Active Patterns: Multi-Case (|A|B|)

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

Playing Cards are a commonly used example of discriminated unions in FSharp. I’m not presuming that you already understand Discriminated Unions, but I’m also not going to explain them. You should be able to follow along and get a sense of how they work. If you’d like to read up on them try here.

A Rank is something that can have one of 13 values Ace through King. A Suit can have one of 4 values Hearts, Clubs, Diamonds or Spades. A Card can be represented as a Tuple of Rank and Suit.

type Rank = Ace|Two|Three|Four|Five|Six|Seven|Eight|Nine|Ten|Jack|Queen|King
type Suit = Hearts|Clubs|Diamonds|Spades
type Card = Rank * Suit

As a brief aside take a look at the ‘*’ which indicates a tuple. Tuples are known as ‘product types’ their range of values are the product of the ranges of values of the types that make them up.

Let me try that again in English. 13 Ranks * 4 Suits = 52 Cards. I’ll pretend Jokers don’t exist, this series is long enough already.

(Two, Clubs)
(Queen, Hearts)
(Ace, Spades)

Cards have an interesting characteristic, every single one of them is either Red or Black. So, here’s a little challenge. Using what you’ve learned so far, write a function takes a card and returns a message like the following

(Two, Clubs) -> "The Two of Clubs is Black"
(Queen, Hearts) -> "The Queen of Hearts is Red"
(Ace, Spades) -> "The Ace of Spades is Black"

If you’re having trouble with that the following easier version will get you a passing grade.

(Two, Clubs) -> "Black"
(Queen, Hearts) -> "Red"
(Ace, Spades) -> "Black"

There are lots of ways we can approach this using the Single Active Patterns (both the Total and Partial varieties). All have drawbacks of one kind or another.

Single Total

Here’s how we could do it with a Single Total Active Pattern

let (|Red|) (card: Card) =
    match card with
    | (_, Hearts) | (_, Diamonds) -> true
    | _ -> false

let DescribeCard (card: Card) =
    match card with
    | Red true -> sprintf "Red" 
    | Red false -> sprintf "Black"

That’ll get us the passing grade but it’s pretty lousy. Black has vanished as a concept, all we have is “Not Red”, and within our match expression we’ve lost the details of the card, all we have is the boolean that tells us if it’s Red or not.

Partials
We can do better with two partials.

let (|Black|_|) (card: Card) =
    match card with
    | (_, Clubs) | (_, Spades) -> Some card
    | _ -> None

let (|Red|_|) (card: Card) =
    match card with
    | (_, Hearts) | (_, Diamonds) -> Some card
    | _ -> None

let DescribeCard (card: Card) =
    match card with
    | Black (rank, suit) -> sprintf "The %A of %A is Black" rank suit 
    | Red (rank, suit) -> sprintf "The %A of %A is Red" rank suit 

That’s better, but if you try that example you’ll see FSharp throws a warning in the DescribeCard function. It claims that we have an incomplete match pattern. FSharp is concerned that a card might come along that doesn’t match either Black or Red.

We know we’ve got our bases covered, but the use of Partials hides that fact from FSharp. What happens if a card comes along that gets ‘None’ from both (|Black|) and (|Red|). I knew those damn Jokers would bite us in the ass.

We could throw in a dummy catch all case that would get rid of the warning, but where’s the fun in that?

This, as it happens is an ideal scenario for a Multi-Case Active Pattern. We know that the full range of possible values for a card (i.e. all 52 cards) must map to one of a small set of possibilities (Red and Black). We can make that fact explicit using a Multi-Case active pattern and kill off a compiler warning in the process.

Multiple

let (|Red|Black|) (card: Card) =
    match card with
    | _,Hearts|_,Diamonds -> Red card
    | _ -> Black card

let DescribeCard (card: Card) =
    match card with
    | Red (rank, suit) -> sprintf "The %A of %A is Red" rank suit
    | Black (rank, suit) -> sprintf "The %A of %A is Black" rank suit

The partials are gone. There’s no more ‘Some card’ or ‘None’. Every card is classified as either a ‘Black card’ or a ‘Red card’. Our match expression doesn’t throw a warning any more because FSharp can understand that Red and Black are the Only possibilities for cards, and we handle them both.

Bringing It All Together
Let’s finish with a nice meaty example that brings together the various types of pattern we’ve covered. We’ll use Single and Multiple Active Patterns to pattern match and describe a hand of Blackjack cards. To keep things simple Ace will count as 11 only, it won’t also count as 1.

The points attached to each card are determined by the Rank. We’ll start with a function that scores a card.

let CardScore (card: Card ) = 
    match fst card with
    | Two -> 2
    | Three -> 3
    | Four -> 4
    | Five -> 5
    | Six -> 6
    | Seven -> 7
    | Eight -> 8
    | Nine -> 9
    | Ten | Jack | Queen | King-> 10
    | Ace -> 11

Our Active Patterns are going to look at hands and tell us something about them. Every hand has a Score so (|Score|) can be a Single Total Active Pattern. And, it’s really easy to write.

let (|Score|) (hand: Card List) =
    hand
    |> List.sumBy CardScore

The number of cards is also a Single Total Active Pattern, and a useful piece of information, as we’ll see in a moment.

let (|Cards|) (hand: Card List) =
    List.length hand

We now have everything we need to fit a hand of cards into one of five possibilities. A Multiple Active Pattern will work. Notice how the code is about as close to a description of the rules as you can get. We literally list the various types of hands. Blackjack is when we have 2 cards with a combined score of 21, A Pair is when we have two cards with the same Rank and we don’t care about the Suits.

let (|Bust|Blackjack|TwentyOne|Pair|Under|) (hand: Card List) =
    match hand with
    | Score s when s > 21 -> Bust
    | Cards 2 & Score 21 -> Blackjack
    | Score 21 -> TwentyOne
    | [(r1,_); (r2,_)] when r1 = r2 -> Pair r1
    | Score s -> Under s

Some of the cases simply identify the type of hand Bust, Blackjack, TwentyOne. Others package some information with the hand type. Pair tells us the Rank of the pair. Under tells us the score. This Multi-Case active pattern is working with Single Case Active Patterns, and together they make the following function really easy to write.

let DescribeHand (hand: Card List) = 
    match hand with
    | Bust -> "You're over 21, you're bust"
    | Blackjack -> "BLACKJACK!!! Yeah!!!"
    | TwentyOne -> "TwentyOne, you should probably stick"
    | Pair r -> sprintf "A pair of %As You can split" r
    | Score s -> sprintf "You have %d, want me to hit you?" s

And here’s where it gets really fun, if for any reason someone goes and adds a new value to the Active Pattern, a new type of hand, then our DescribeHand function will fail to compile. We would no longer be covering all of the possibilities.

You don’t get that kind of protection when you use partials and catch-alls.

Caveats
There are one or two things to note about Multi-Case active pattern.

  • They can have a maximum of 7 values. Our example above had only 5, but there are 10 named Poker Hands, so for Poker we’d need take a slightly different approach. Typically if you are looking at a lot of values putting them in separate Single Partial Active Patterns may make more sense, despite the concerns expressed above.
  • They can not be Partial. Multi-Case Patterns exist precisely to give the exhaustive pattern matching. If you are going to require catch all clauses then you might as well use Single Partial Patterns.
  • They can not have additional arguments beyond the one argument that they match on. You can define a multi case active pattern function with additional arguments but you will receive an error if you attempt to use it. That may seem odd, but as we’ll see in the next (and final) post, you can partially apply a Multi-Case pattern to create one that accepts one argument, and that can then be used.

We’ve now covered all of the different types of Active Patterns, we’ve also touched on a number of other areas within FSharp from Option Types to Currying, Tuples to Discriminated unions. If you’ve stayed with me then you should feel like you “get” active patterns, and you may have picked up some extra FSharp along the way.

Active Patterns are incredibly flexible, we haven’t even scratched the surface of all the way’s they can be used. That’s down to you.

There is one more post to go, it will cover some strange and wonderful things you can do with what you’ve learned. We’ll partially apply the Multi-Case patterns, and we’ll nest active patterns to match over complex hierarchical data structures.

Active Patterns: Single Partial With Params (|A|_|) x

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

We close out the discussion of Single Active Patterns by adding parameters to the partial active pattern. If you’ve read the post on adding parameters to the Single Total Active Pattern then there is absolutely nothing new here, it works in exactly the same way.

For that reason I’m not going to use this post to explain how to do it, I’m just going to work through an example and leave it at that.

In the last post I created some active patterns that we could use to evaluate a rudimentary arithmetic expression. There was a lot of duplicated code between the Addition and Subtraction cases.

Here’s a first stab at eliminating some of that by extracting the underlying behavior and using Partial Application. This has all been covered already in this post.

Parsing numbers is handled just like it was before, no change here.

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

Now instead of fully implementing Addition and Subtraction independently of each other, we have a more general purpose pattern called (|BinaryOp|_|). Note that the operator (the text to look for in the expression) is an argument to this function.

let (|BinaryOp|_|) operator (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(operator) then 
        Some (SplitAt operator str)
    else
        None

Now creating our Addition and Subtraction patterns is simple.

let (|Addition|_|) = (|BinaryOp|_|) "+"
let (|Subtraction|_|) = (|BinaryOp|_|) "-"

And the Match works just like it did before, no change here.

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))

That’s all fine, but notice how our match expression needs to know how to respond to the Addition and Subtraction cases, this isn’t ideal.

    | Addition (l, r) -> Eval(l) + Eval(r)
    | Subtraction (l, r) -> Eval(l) - Eval(r)

We could do the following.

type Operator = string * (int->int->int)

The type ‘Operator’ consists of a string (the token) and a function int->int->int (I’m keeping things simple here, int only). Now our underlying BinaryOp pattern just doesn’t take a string to search for, it also takes a function to perform when that string is found.

let (|BinaryOp|_|) (operator: Operator) (str: string) =
    let token, operatorFunction = operator
    let SplitAt (op: string) (str: string) =
        let pos = (str.IndexOf op)
        (operatorFunction, str.Substring(0, pos),str.Substring(pos + 1, str.Length - pos - 1))

    if str.Contains(token) then 
        Some (SplitAt token str)
    else
        None

We use destructuring assignment to extract the token and the function from operator. The token is used to split the string, but the function is simply passed back from the pattern so that the calling match expression can use it.

Defining the Addition and Subtraction patterns is now slightly different, we need to include both the token and the function.

let (|Addition|_|) = (|BinaryOp|_|) ("+", (+))
let (|Subtraction|_|) = (|BinaryOp|_|) ("-", (-))

As mentioned above our match expression needs to be modified to get the function back from the active pattern so that it can apply it to the left and right subexpressions. Now that both Addition and Subtraction are handled identically, we can combine them using an or ‘|’ pattern.

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

And that’s it for Single Case Active Pattern both the Total and Partial variety. We’ve covered a lot of ground. In the next post we’ll move on the Active Patterns that have Multiple results. If you’ve managed to stay with me this far nothing that remains will phase you.

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

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

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.