Navigate / search

Azure WTF#

This is my contribution to the 2015 F# Advent Calendar.

I recently set myself a challenge. Build a web-service in F#, and make it run on Azure. Nothing too fancy, just serve up some resources as Json, and allow me to add, update and delete them.

How hard could that be?

Well, as it turns out, hard.

I scavenged body parts from a few blog posts and talks. Beginning with Tamizhvendan Sembiyan’s excellent and detailed post on building web-services with

Suave is a really neat web framework that lets you work with HTTP Requests and Responses using idiomatic functional code. Which, Tomas Petricek points out is how it should be. The web is essentially a functional model. It is ideally a stateless function that accepts a Requests as input, and produces a Responses as output.

Tamizhvendan showed some nice handlers for serialising to and from Json, and for mapping urls to functions. I’m not going to go into all the details that he has covered. Seriously, read his post.

I do want to mention one place where I took a slightly different approach to his. He represented a resource as a record containing functions for the typical CRUD methods. The signatures are nice, like the ‘a -> ‘a option for Update, signifying that the resource in question may not exist to be updated.

type RestResource<'a> = {
  GetAll : unit -> 'a seq
  Create : 'a -> 'a
  Update : 'a -> 'a option
  Delete : int -> unit

I’m not a fan of the ‘record of functions’ approach to implementing interfaces. But the point of the post was to demo Suave and it did that. I was up and running and quickly had a basic webservice working locally. That word, ‘locally’ is about to get really significant.

The First Problem
In line with Tamizhvendan’s post, I built my first web service as a console app, ran it locally and it worked. Then, I tried to get it running on Azure.

I’m sure this is possible, but every example I could find for F#/Suave on Azure involved using Scripts instead of an App. Chief among them this one by Scott Hanselman.

Ok, I’ll just convert my Console app to a script for now.

How hard could that be?

Well, as it turns out, hard.

Hello Scripts
Before I actually try to convert my existing code, let’s see if I can get a simple hello world web service running as a script on an Azure Website. Let’s start with Scott’s post, mentioned above.

Ok, there’s a lot of new ground for me to cover here. Suave, Fake, Kudu, Paket, heck even F# scripting was pretty new to me, I don’t think I’d ever used it for anything that required more than one fsx file.

I have deployed a C# ASP.Net MVC app to Azure from github and each push triggers a new deploy. Setting that up was simplicity itself. Getting an F# script to deploy and run on Azure was starting to look like an ordeal by comparison.

And keep in mind, a Script isn’t even what I want. That’s a temporary compromise because I couldn’t get a console app to work. I thought F# was supposed to make life simpler.

The Second Problem
Now, what I should have done is just deploy Scott’s code directly from his repo, or forked his code and deployed it. But where’s the fun in that. No, I tried to recreate his work from scratch, to really understand it. And that cost me in the short term. But I think it was worth it.

I’ll do a separate post on the things I managed to get wrong just trying to recreate and deploy his simple example. Basically if you have any extra files in your repo like .sln or .fsproj files, you’ll get some confusing errors. And if you’re missing any, like oh say the .deployment file then weird stuff happens or doesn’t happen.

Sometimes nothing happens and it’s not your fault. You try to deploy and everything just hangs. I’ve noticed that three separate nights from about 11pm until after 1am (Irish Time). And then it works itself out. I need to investigate that more, but it’s really annoying when you’re already unsure of the code you’re deploying.

Now that I had something running, it was time to expand it to host my full Web Service.

How hard could that be?

Well, as it turns out, hard.

The Third Problem
Remember, I have to build my full Web Service as a script. The thing is, F# scripts are fine for building small scripts. If you’re building an app, with types and modules, you really want to be using the compiler and making real apps and libraries.

The reason for this is that when scripts reference each other, you can end up loading the same file more than once, because it’s a dependency of more than one other script. When this happens FSharp loads the file into two different namespaces. See the FSI_0006 in the following example.

[Loading /Users/richarddalton/Projects/EloRateApi/site/Model.fsx]
namespace FSI_0006.EloRateApi.Model

What this means is that the same ‘Type’ can exist in memory as two different incompatible types.

To put it bluntly, you can’t build complex apps as F# scripts. And on the off chance that you manage to, you probably shouldn’t. But, for now I wanted to get something running, so scripts would have to do.

I have good news, and bad news. The good news is I did manage to build a Web Service that serves up Json and lets me Create, Update and Delete resources.

The bad news is it only has two resources, Players and Games, and because it’s fsx files I don’t see it as a viable approach for a real web service with any more resources or any more logic.

So, I need to get back to the drawing board and either get console apps running on Azure, or put the bulk of the code in a Library, and use a single, simple Script to launch the Web Service. Which means I have to learn a little more about Fake so that I can build the Library and Deploy it.

The Code
The code in full is available here

Forgive me, it doesn’t yet have a nice welcome readme, but it will. The code also isn’t quite the way I like it. Partly because of the limitations of scripts, and mostly because I haven’t finished simplifying it yet.

The code does run locally, just clone the repo and run webserver.fsx using fsharp interactive. The Azure deployment is still a little hit and miss.

If you read Scott’s post mentioned above, you’ll understand how the deployment works, but for now, let me mention one or two pieces of interesting code.

webserver.fsx defines the routes and runs the server. It’s the starting point for the project.

restful.fsx is basically a stolen and slightly modified version of Tamizhvendan’s code, which allows me to be a little more flexible in the methods I define for a resource, because I don’t use an ‘interface’ as such.

model.fsx contains my types representing Players, Games and the State of the service. It also relies on a script called CQAgent that I’ve written and which I reference directly from Github using Paket.

CQAgent uses F#’s MailboxProcesser to provide a generic agent for managing State, and querying it using query methods, or modifying it using commands. It’s worth a blog post in it’s own right, and I’m indebted to Tomas Petricek for getting me over the line in writing it.

Here we see the power of suave. We compose handlers for incoming requests, so if a request is a HTTP.DELETE to the “games” resource, it will fail to match on any of the Player routes, and it will fail on all but the last game route.

let PlayerRoutes = choose [
                        Get "players" (Player.GetAll model)
                        GetById "players" (Player.GetItem model)
                        Post "players" (Player.Create model)
                        Delete "players" (Player.DeleteItem model)
                        Put "players" (Player.Update model)
                        PutById "players" (Player.UpdateById model)

let GameRoutes = choose [
                        Get "games" (Player.GetAll model)
                        GetById "games" (Player.GetItem model)
                        Post "games" (Player.Create model)
                        Delete "games" (Player.DeleteItem model)

let routes = choose [
              (NOT_FOUND "Huh?")

Each of those choices aren’t just a way of matching, they are calls to functions in restful.fsx that
will get the work done. If we look at the Delete function in restful.fsx, it’s a bit intimidating.

let Delete resourceName delete =
    let resourcePath = "/" + resourceName
    let resourceIdPath =
        new PrintfFormat<(int -> string),unit,string,string,int>(resourcePath + "/%d")

    let deleteResourceById id =
        delete id

    DELETE >>= pathScan resourceIdPath deleteResourceById

Don’t worry about how the function works, let’s just look at the signature. It takes a string resourceName. As you
can see we pass “players” or “games” to that. The third argument ‘delete’ is actually a function that will do the work of deleting the resource.

It’s signature isn’t annotated but it is ‘a -> unit, which is exactly the signature Tamizhvendan used.

We pass the following to that argument

(Player.DeleteItem model)

Let’s look at the Player module.

let public DeleteItem (model: CQAgent<State>) id =
    model.Command (fun (s: State) ->
        ((), { s with Players = removePlayer id s.Players }))

We can see now that what actually happens is we partially apply the DeleteItem method, passing it just the model,
producing an int -> unit function that matches the required signature of a Delete method.

Json etc.

All of the serializing to and from Json, and the parsing of urls us handled by restful.fsx. All of the handling of system state is handled by CQAgent.fsx.

The Ghost of Christmas Future

Where to from here?

This has been a really frustrating project because with Suave and with some of the other code, it really feels like F# is a great language for building web services. But the tooling and infrastructure either isn’t there or my ambition is writing cheques my knowledge can’t cash.

I’ll stick with it. But I’m really hoping I get a comment saying, I’m doing it all wrong, and it’s really simple when you know how.

Pride and Prejudice

My last post was in support of functional programmers. This post tries to get to the nub of the ‘Arrogance’ issue. Where does it come from? What sustains it? Why Functional Programmers in Particular?

There are real problems. There are enthusiasts who are hostile to newcomers. There are newcomers who are hostile to functional programming. I’m going to ignore these extremes. I’m interested in people who engage in good faith, but don’t manage to connect.

There’s seems to be a kind of dual reality happening. Newcomers and the enthusiasts can have different perspectives of the same interaction. Some of this confusion plays out in a world of anonymous forums and 140 character tweets. We are not designed to deal with complex issues through these new media. Things escalate, fast.

Here are a few of the more common disagreements.

Functional Programmers moralise about side effects and purity.

Functional programmers are cast as the vegetarians of programming. Side effects and mutable variables are off the menu. Some go full vegan and learn Haskell.

To a newcomer this can seem a bit puritanical. “Thou Shalt Not” lectures don’t sit well with programmers.

This is where we touch on the difference between easy and simple. Easy is a close cousin of familiar. Adding a lock around mutable state is easy if that’s what you know how to do.

Simplicity is the absence of complexity. Learning new skills to eliminate mutable state is hard, but the resulting solution can be simpler. As familiarity increases, difficulty decreases and you get simple AND easy.

If you learn a new paradigm, you are by definition ok with the unfamiliar. You have a different perspective than some of the newcomers that you are trying to convince.

That difference may lead newcomers to see you as puritanical, and may lead you to see newcomers as lazy. In that situation, everybody loses.

Functional Programmers Dismiss OO, which has served us well.

Every functional programming enthusiast I know has a background in Object Oriented programming. Many will admit to having struggled to do OO well.

The deeper they get into functional programming the simpler it seems by comparison. That is one of it’s big attractions.

It’s not uncommon to equate OO with the familiar complex solutions I describe above. And to think of functional programming as the unfamiliar but simpler alternative.

I’ve been guilty of thinking in those terms. It’s understandable. You’ve struggled with OO. You find a paradigm that seems to address your specific issues. It’s all too easy to think you’ve found ‘a better paradigm’.

Presenting functional as a better alternative to OO doesn’t sit well with people who know and like OO. It’s hostile, and it’s wrong in any case. Just as it’s wrong for newcomers to claim that OO is better or more intuitive.

I think of OO and functional as the longitude and latitude of software development. When you learn both you don’t explore two different paths, you explore an entire area mapped out by two axes.

Functional programmers obsess over clever unreadable code

Some programmers enjoy exercises like ‘Code Golf’. They cram entire algorithms into a single tweet. These recreational programming challenges are popular with with both functional and imperative/OO programmers.

Functional code does tend to be terse. If it’s unfamiliar to you, it can look a lot like a code golf exercise. The gleeful reactions of programmers to such code don’t help.

Idiomatic functional code is at a level of abstraction above imperative code. It tends to avoid loops, conditionals and temporary variables. It has unfamiliar concepts like pattern matching, sum types and partial application.

It can be a shock to see actual abstraction done well. Most of what we call abstraction is just indirection.

Object Oriented code done well should also offer abstraction over imperative code. That’s a story for another day.

Yes, code golf happens, there’s nothing wrong with it. But, not all programmers cackling over some terse code are playing code golf. They are not all smug and obsessed with their own cleverness.

Sometimes they’re writing good production code. They’re delighted to see abstraction working like it should. Every programmer, regardless of paradigm should celebrate that.

I just don’t get it / Functional Programmers are smug because they “get it”

Most programmers with a bit of experience can pick up a new language in a few days. It’ll take longer to understand it’s peculiarities. But you should see progress in days, if not hours.

We can do this because languages have common roots. This won’t happen if you try to learn a new paradigm.

Learning a new paradigm is akin to learning programming all over again. You’ll feel lost. For some, that is evidence that functional programming is “not intuitive”.

There is debate about whether OO is ‘intuitive’ because it models the real world? Or whether it’s just ‘familiar’ after years as the dominant paradigm?

For me, the lost feeling is the best part. I’m back to the days when new knowledge came in BIG jumps. When unconnected ideas joined together and unlocked completely new ideas.

It can be hard to articulate “how” you learned functional programming. It’s easy to give newcomers the impression that it is something that you just “get”. Try not to do that. There are eureka moments, but they come after working though that lost feeling.

Functional Programmers ramble on about maths and lambda calculus

I missed two years of school which left me with some big gaps in my maths knowledge.

Trust me when I say, you don’t need maths to grasp functional programming. But, functional programming can be a gateway drug to maths.

If functional programmers seem enthusiastic about maths it’s because maths is cool. When mathematical ideas start to make sense, it’s the same rush that we get from programming.

To work in a new paradigm and see it not only make sense, but tie back to mathematical underpinnings. It’s exciting.

Getting Involved

If you are interested in learning functional programming, the one piece of advice I would offer above all others is make contact with real people. Stay away from forums.

Watch talks, read blogs, follow people on twitter, see who they follow in turn. Get a sense of the personalities, the sense of humour etc.

People who are enthusiastic about functional programming will be glad to help anyone who shows a genuine interest. They will also be able to suggest others who can also help you.

We all tend to mirror the people we interact with. If you are enthusiastic and genuine in your enquiries you will find people who are enthusiastic an genuine in their efforts to help.

Some Functional Programmers Are Arrogant

On Sunday, I was preparing to fly home after Progressive .Net Tutorials in London. The conference had seen a big chunk of F# content. I’d spent a couple of days chatting with amazing people. Recharging the enthusiasm battery pack.

Apart from some heavy breathing on the mic for the first few minutes of my talk, and my inexplicably saying immutable when I meant mutable (multiple times), I was ok with how my talk went, feedback had been good.

The F# sessions were well attended, spirits were high, and to top it all, it emerged that Don Syme was to be awarded the prestigious Silver Medal by the Royal Academy of Engineering, for his work on C# Generics and the creation of F#.

It was a great week.

Then, a tweet.

Not this again. Functional Programmers are arrogant. Functional programmers drive newcomers away from functional programming.

It reminded me of Bill Hicks’ story about turning on CNN and seeing WAR, FAMINE, DEATH then going outside and hearing birds chirping. Where is all this stuff happening? Where are these arrogant functional programmers attacking people eager to learn, driving them away.

It reminded me of Bill Hicks’ story about turning on CNN and seeing WAR, FAMINE, DEATH then going outside and hearing birds chirping.

I’ve been programming since 1984 and professionally since 1996. So, yes, I’m a noob compared to Bob Martin, but dammit I’ve been around a while and nothing I’ve experienced in programming comes close to Functional Programming for sheer fun and a supportive community.

We started the Functional Kats monthly meetup in Dublin and specifically kept it non language specific to make it as welcoming as possible, and to allow users of different languages to learn from each other. Sceptical of Functional Programming? Then come along and use C#, Java or Javascript, or whatever. All welcome here.

Here’s the thing about people who are enthusiastic about functional programming. Most of them are just so relieved to find someone showing a genuine interest that they will bend over backwards to help you. To build you up. To make YOU feel smart.

I know this because I was on the receiving end of this generosity from the moment I showed an interest. This is why it’s frankly baffling when this charge of arrogance is levelled. Why functional programming? Of all the areas of software development, why is the arrogance of functional programmers a thing?

If it’s just a comment on the internet, a random tweet with no specific details, like this one

Then I just ignore it. I really don’t have the time or energy to deal with all the people that I think are wrong on the internet.

But this wasn’t some random tweet. This was Robert C. Martin. This was someone with a following, a reputation. This was someone speaking with authority. Worse than that, this was someone with a foot at least partially inside the world of FP. He has given talks on Clojure and even (I hope jokingly) suggested that we should all switch to Clojure and call programming languages done.

Worse than that, this was someone who has been on the receiving end of exactly these kinds of remarks. Craftsmanship is elitist. TDD’ers are arrogant. And not even random unsubstantiated claims. When Ted Neward (rightly in my opinion) raised questions about the link between Craftsmanship and the treatment of Heather Arthur, Bob took to his blog to defend Craftsmanship and swat back Ted.

At least Ted cited a specific incident. At least he called out specific bad behaviour, and it was bad.

Here’s the thing about people who are enthusiastic about functional programming. Most of them are just so relieved to find someone showing a genuine interest that they will bend over backwards to help you.

Bob issued a general tweet saying that arrogance is a “significant barrier to entry”. And I couldn’t believe it. He was legitimising random nonspecific comments about arrogance, with a random nonspecific comment about arrogance. (Yay..Recursion!)

Bob is better than this I thought. Bob should be better than this. Bob has to know that this tweet can be called on any time someone wants to lazily accuse functional programmers of being especially arrogant, without giving an example. More arrogant than OO programmers, more arrogant than DBA’s or DevOps advocates. More arrogant than C++ programmers or Agile Coaches.

Bob didn’t say some programmers are arrogant. He said some “functional” programmers are. He didn’t say some software craftsmen (or women) are arrogant. Actually he said they’re a great bunch helpful welcoming people. The Manifesto says they are.

Uncle Bob has jumped on the “Functional Programming/Arrogance” bandwagon, rather than use his considerable knowledge of computing history, and his considerable reputation within the industry to say, hold on, let’s all take a second and see if there really is a special arrogance problem in this particular field, or is this just received wisdom that people repeat without question.

Bob knows that arrogance and ego has been a feature of virtually every discussion in programming, from getting rid of GOTO to Static vs Dynamic typing. From how or whether to TDD, to how or whether to automate deployments. From Waterfall to Agile. From Pragmatism to Craftsmanship to Just Ship It. Hell the Javascript community almost imploded into an argument about semi-colons.

So, THAT is why I tweeted a reply

And that is why Bob asked me to elaborate, and that is why this post exists.

Is there arrogance in Functional Programming? Sure there is. Why? Because it’s programming.

Fred Brooks nailed it in the year I was born.

We work “only slightly removed from pure thought-stuff”

We build “castles in the air, from air, creating by the exertion of the imagination. Few media of creation are so flexible, so easy to polish and rework, so readily capable of realizing grand conceptual structures….”

Of course all of us are arrogant some of the time, and some are arrogant all of the time. Of course. How could it be otherwise?

Google ‘Functional Programming Arrogant’. You’ll see some examples. Nothing really bad I have to say. I’d even posit that a lot of people dismissing FP as a fad or a bandwagon, or a bad idea without ever looking into it are showing as much or more arrogance.

Google ‘My Little Pony Arrogant’ there are far more results.

I’ll write another (much shorter) post about why I think this arrogance issue really exists, and what we can do about it, but tweets like that one from Uncle Bob are not part of the solution. They are part of the problem.

That’s for another day.

Fun with Charts and the REPL

PUBLIC SERVICE ANNOUNCEMENT: This post uses WinForms to display charts. It’s fine, but might pose some cross platform issues. You might like to consider XPlot as an alternative.

Apart from immutable by default, expressions instead of statements, easier parallel code, less noise, higher order functions, expressive type systems and borderline magic type inference what has functional programming ever done for us?

My new favourite part of the whole story is the REPL, and the freedom it (and the features above) gives us to experiment with code.

Power up an FSharp script file and use NuGet to get FSharp.Charting and FSharp.Collections.ParallelSeq. Once you’ve installed the packages, load them in the script file, and open the necessary namespaces.

#load "packages/FSharp.Charting.0.90.10/FSharp.Charting.fsx"
#r "packages/FSharp.Collections.ParallelSeq.1.0.2/lib/net40/FSharp.Collections.ParallelSeq.dll"

open System
open System.IO
open FSharp.Charting
open FSharp.Collections.ParallelSeq

Now we’re ready to go. We’re going to throw various numbers of dice and then chart the results. Let’s focus first on throwing one dice.

let random = System.Random()
let randomDice = Seq.initInfinite(fun _ -> random.Next(1,7))

This is an infinite sequence of individual dice rolls. For Monopoly we’d roll two dice at a time, for Yahtzee we’d roll 5. So our next job is to roll a number of dice at the same time. We can use Seq.take for this.

let throwAtATime n = Seq.initInfinite(fun _ -> (Seq.take n randomDice) |> Array.ofSeq)

We’ll be adding the ability to save dice rolls to file and load them again, so here are a few helper functions that’ll make things a little easier later.

let NumsToText (nums: int[]) =  nums |> (fun d -> d.ToString())
let Join (separator: string) (array: string[]) = String.Join(separator, array)
let TextToNums (text: string) =  text.Split(',') |> Int32.Parse

NumsToText converts the throws (integers) into an array of strings. Join wraps the String.Join function to allow us to partially apply it (and use it with pipelining). TextToNums splits a comma separated string of throws (read from a file) and converts it back into an array of ints. I’ve also wrapped the File.WriteAllLines and File.ReadLines so that we can use them in pipelined code.

let WriteToFile file lines = File.WriteAllLines(file, lines)

let ReadFromFile file =
    |> TextToNums

Whether we generate throws randomly or load them from a file, we have them in the same format, a Sequence of Arrays of integers. Lets write a function that takes that data structure and plots it as a chart. Here’s a function to plot the throws using FSharp Charting. Note that we use a ParallelSeq to speed things up a little.

// Plot To Screen
let Plot (throws: seq<int[]>) =
    |> Array.sum
    |> PSeq.countBy id
    |> PSeq.sortBy fst
    |> Chart.Line

We sum the dice in a given throw. Then we group by the total, sort by total and Chart the results.

As expected the result is a bell-curve, although this little experiment shows how easy it is to visualise data in situations where you might not necessarily know the pattern in advance. We’ll see some more charting shortly, but lets quickly look at how the same data structure can be persisted to a file.

// Save To File
let Save file (throws: seq<int[]>): Unit =
    |> NumsToText
    |> (Join ",")
    |> Seq.toArray
    |> WriteToFile file

And that’s it, we now have a suite of function that will allow us to do some cool things with very little effort. I love being able to use a simple data structure and a few helper functions and then use the REPL to “play” with the data. It allows us to answer questions about the data more quickly, but more importantly than that, the experimentation suggests questions we might not have otherwise thought to ask. Here are a few examples of getting stuff done in the REPL in just a few lines of code.

//Generate 1000000 random throws of 6 dice and save to file
throwAtATime 6
|> Seq.take 1000000
|> Save @"C:\Temp\dice.txt"

// Generate 1000000 random throws of 6 dice and plot a graph
|> Seq.take 1000000
|> Plot

// Read From file and plot a graph
ReadFromFile @"C:\Temp\dice.txt"
|> Plot

// Read From file and save to another file (No, I don't know why you would either).
ReadFromFile @"C:\Temp\dice.txt"
|> Save @"C:\Temp\dice2.txt"

As you play with data, questions come to mind. Like, can we visually see what more dice does to the bell curve? Of course we can.

let threeDice = throwAtATime3 |> Seq.take 100000
let tenDice = throwAtATime10 |> Seq.take 100000
Chart.Combine [Plot threeDice; Plot tenDice]

Are you pondering what I’m pondering? Could we just use to generate a whole slew of samples and plot them all together? Let’s see.

// Generate samples for 1 to 10 dice and plot them all 
|> (fun n -> throwAtATime |> Seq.take 1000000) 
|> Plot |> Chart.Combine 

Here we’ve seen a simple use of FSharp Charting. We’ve covered reading from and writing to a file. We’ve also seen how a couple of helper functions and paying attention to function signatues allow for some very readable code.

Minimize mental overhead for code readers

This week at our FunctionalKats meetup in Dublin, tackled the Luhn checksum algorithm.

This is a simple programming task, the challenge was to try and make the code readable.

I rattled off some code that worked, but I wasn’t at all happy with it. It implemented the problem as described. Partitioning the numbers into two groups and dealing with each group in turn.

let Luhn s =
    let double x = x*2

    let sumDigits = function
        | 18 -> 9
        | n when n > 9 -> n%9
        | n -> n

    let odds, evens =
        |> (string >> int)
        |> Array.ofSeq
        |> Array.rev
        |> Array.partitioni (fun i -> i%2 = 0)

    let oddSum = Array.sum odds
    let evenSum =
        |> double
        |> sumDigits
        |> Array.sum
    (oddSum + evenSum) % 10 = 0

The Array.partitioni function doesn’t exist, I had to write that too.

module Array =
    let partitioni f a =
        let first, second =
            |> Array.mapi (fun i x -> f i, x)
            |> Array.partition (fun (i, _) -> i)
        ( snd first, snd second)

I didn’t like the idea of partitioning the numbers. That may match the problem description but I think we can do better. I like functions that take in something and transforms it, perhaps through many transformations, but without splitting or branching the logic.

If a function splits the data and does separate transformations, there’s mental overhead involved. Every variable in a function is an extra concept for the reader to understand.

My second attempt tried to rectify this

let Luhn s =
    let double x = x*2

    let sumDigits = function
        | 18 -> 9
        | n when n > 9 -> n%9
        | n -> n

    let mapOdd = id
    let mapEven = (double >> sumDigits)
    let mapNumber i = if i%2=0 then mapOdd else mapEven

    let total =
        |> (string >> int)
        |> Array.ofSeq
        |> Array.rev
        |> Array.mapi mapNumber
        |> Array.sum

    total % 10 = 0

Instead of partitioning the data we map the entire array. The function used in the mapping is different for odd and even positions. The mapNumber function handles the toggling of the two functions.

This is better, but it’s still not right. Those mapOdd and mapEven functions, that IF expression selecting between them. It still feels like two trains of thought. We can do better.

let sumDigits n = Math.DivRem(n, 10) ||> (+)
let isMultipleOf x y = y % x = 0

let Luhn: string->bool = (string >> int) 
    >> Seq.rev
    >> Seq.map2 (*) (Seq.cycle (seq[1;2])) 
    >> sumDigits
    >> Seq.sum
    >> isMultipleOf 10

Now we’re getting much closer to the ideal. The function accepts a string, produces a bool. It gets from string to bool through series of simple transformations. No IF expressions, no splitting of the numbers into groups, no toggling of functions.

The trick lies in generating a cycle of 1’s and 2’s. When you multiply a sequence by 1,2,1,2,1,2…. You double every second item in the sequence. With that done, the rest of the function falls into place.

There are a few other subtle improvements. The sumDigits function is simpler thanks to the use of Map.DivRem and ||>.  The Luhn function itself is a composition of transformations. I also created the Seq.cycle and Seq.rev.

module Seq =
    let rec cycle s = seq { yield! s; yield! cycle s}

    let rev s = s |> Array.ofSeq |> Array.rev |> Seq.ofArray

I’m happy with the function as it stands. The ideas I wanted to get across with this post are

  • Don’t let the description of a problem constrain your thinking. It’s often possible to find solutions that are simpler than the problem would imply.
  • Try to reduce the moving parts, the “concepts” in your functions. Aim for functions that read straight through. A reader should have to push as little as possible onto their mental stack.
  • Try to avoid splitting your data and working on different subsections of it. A function should only accept the data it needs to work on. Keeping that data together as you transform it isn’t always possible. If you can achieve it, your code will usually be simpler.

Decorating Immutable Christmas Trees


This post is the fifth in the 2014 F# Advent Calendar series.

As much as I love having a real Christmas tree, I hate buying it and dragging it home. I hate decorating it. I hate taking it down again. Untangling lights, tinsel and baubles.

The problem with Christmas trees is that once you’ve decorated them, there’s no easy way to get back to the bare tree that you bought. You have to get in there and undo all the work.

An immutable tree sounds appealing.

“Sorry kids, we can’t decorate the tree. Don’t shoot the messenger, I don’t make the rules.”

That’s all fine until one of the kids discovers that if you do decorate the tree you get a new tree. “TWO TREES” they scream, then, “THREE TREES” and the whole thing descends into a Dr Seuss story.

How I learned to reject change and love immutability

Not too long ago if you asked me to create a data structure like a binary tree, it would be written in C# and it would look like this.

    class BinaryTree<T> where T : IComparable
        public T Value { get; private set; }
        public BinaryTree Left { get; private set; }
        public BinaryTree Right { get; private set; }

        public BinaryTree(T value)
            Value = value;

        public void Add(T value)
            if(value.CompareTo(Value) == -1)
                if(Left == null)
                    Left = new BinaryTree(value);
                if (Right == null)
                    Right = new BinaryTree(value);

Notice that the Add method doesn’t return anything. It “changes” the tree. You use it like this:

    var t = new BinaryTree<int>(5);

Back then, creating immutable data structures seemed like more trouble than it was worth. I knew how to do it, but it was easier to convince myself that I had the discipline to not need immutability.

I still see that push back against immutability in many of my C# colleagues. They’re not wrong. If you look at software development through a C# or Java lens immutable data structures can seem like a bit of an indulgence.

The Path Of Least Resistance

The thing is, immutability is easy. The problems I had were down to the tools and the path of least resistance that they encouraged.

If you asked me to build a binary tree today it would be immutable unless there was a good reason for it not to be. A big part of that change is down to language choice and the switch to Functional Programming.

Here is the same data structure and functionality as the C# code above, but this is F#. There isn’t much extraneous code here. We are immutable by default.

module BinaryTree

type BinaryTree<'a> =
    | Tree of 'a * BinaryTree<'a> * BinaryTree<'a>
    | Empty

let rec add value tree =
    match tree with
    | Empty -> Tree(value, Empty, Empty)
    | Tree (x, left, right) when value < x ->
        Tree(x, add value left, right)
    | Tree (x, left, right) ->
        Tree(x, left, add value right)

With this implementation we can use our binary tree as follows

    let t = Empty
    let u = BinaryTree.add 5 t
    let v = BinaryTree.add 3 u

And t, u and v will each represent different trees.

The second argument of the add method is the tree to add to, so we can pipe the output of one call into another, as follows:

    let t = Empty
            |> BinaryTree.add 3
            |> BinaryTree.add 4
            |> BinaryTree.add 2

Immutable is Easy

Lets see how you add something to an immutable tree. The result of adding a value to a tree is always a new tree. That’s important so keep it in mind, we are all about creating new trees here.

If we have an empty tree and we want to add a number like 5 then it’s easy, the new tree has one node containing the value 5 and no sub-trees.

    | Empty -> Tree(value, Empty, Empty)

If we add a value to an existing tree, we have two possibilities. The new value is less than the root of the existing tree, or it isn’t. In both cases we create a new tree, but what will it look like?

In both cases the new and old tree will have the same root value. Remember the new value gets added to either the left or right sub-tree.

If the new value is less than the existing value, we add it to the left sub-tree. This means the right sub-tree will be the same as that of the original tree.

    | Tree (x, left, right) when value < x ->
        Tree(x, add value left, right)

Look at that. Create a new tree with the same value as the old tree, the same right sub-tree, and with the new value added on the left sub-tree.

Of course that’s a recursive call so it will compare the new value with whatever values exist down the left sub-tree.

The only remaining scenario is a new value that’s equal to or greater than the value in the existing value. As you might expect it’s the mirror of the previous case.

    | Tree (x, left, right) ->
        Tree(x, left, add value right)

As you can see with a handful of lines of code we not only get immutable binary trees but we get trees that share common nodes. The new tree doesn’t need to copy the unchanged sub-tree of the original, it can just point to it, safe in the knowledge that it is immutable.

Expressions vs Statements

Look again at the Add method in the F# example. All we have is a 1:1 mapping of conditions to expressions. The expressions evaluate to the new Trees.

Compare this with the nested if…else statements in the C# example.

The imperative (statement style) code describes how to change an existing tree. It uses a few nested questions. This kind of code requires you to keep your wits about you. How did I get here? What answers to what questions brought me to this line?

The functional (expression style) code is much simpler (in my opinion). There are three conditions that map 1:1 to expressions. Each expression produces a new tree.

We don’t write code that describes how to construct the new tree, or change the old one. We just construct the new Tree and we’re done.

Gifts Under The Tree

One aspect of Christmas Trees that I do like is the gifts. Here to finish are a few random snippets, questions, and ideas that relate to the F# code above.

Folding into a Tree

We can use the add method to create a BinaryTree by folding a collection, using an Empty tree as the starting point.

    let nums = [5; 8; 3; 5; 3; 7; 4; 8; 4; 7; 89; 4;]
    let t = List.fold(fun acc n->BinaryTree.add n acc) Empty nums

As an exercise, reverse the arguments in the definition of the Add method so it looks like this:

let rec add tree value =
    match tree with
    | Empty -> Tree(value, Empty, Empty)
    | Tree (x, left, right) when value < x ->
        Tree(x, add left value, right)
    | Tree (x, left, right) ->
        Tree(x, left, add right value)

With that done, how can we simplify the List.fold above?

What impact does that have on this earlier code:

    let t = Empty
            |> BinaryTree.add 3
            |> BinaryTree.add 4
            |> BinaryTree.add 2

Proper Decorations

What kind of tree has numbers or even strings? Let’s get some Tinsel, Lights and Baubles on there.

type Decoration =
    | Bauble
    | Lights
    | Tinsel

let decorations =
    [Tinsel; Lights; Bauble; Bauble; Tinsel; Bauble; Lights; Lights; Tinsel; Bauble; Bauble; Bauble]

let t = List.fold(fun acc n->BinaryTree.add n acc) Empty decorations

That will work, but the tree won’t look good. It segregates the different decorations into their own sections of the tree.

How could you create a tree that distributes the quantities of baubles, tinsel and lights evenly around the tree?

Removing A Node

Removing a node requires a little more thought than adding. Try and write an FSharp method to remove an item from a Tree. Here’s one approach.

Now try to write a remove method in the mutable C# BinaryTree. Which did you find easier? Was there any difference at all? Have you more confidence in one or the other?

Traversing The Tree

You can use a sequence expression to traverse a tree and output the results as sequence.

let rec inorder tree =
    seq {
      match tree with
          | Tree(x, left, right) ->
               yield! inorder left
               yield x
               yield! inorder right
          | Empty -> ()

Note that calling inorder on the left and right sub-trees will produce sequences of their own. We use yield! to elevate those into the sequence we’re creating.


How would you you change the add method so that it throws away duplicate values rather than adding them to the tree? Go on, it’s easy.

This post is the fifth in the 2014 F# Advent Calendar series.

Curried vs Uncurried Functions

Over a year ago I explained Memoization in this post. If you’ve read that, you should be comfortable with the following.

open System.Collections.Generic

let negate x =
    printfn "Negating..."

let cache f =
    let cache = Dictionary<_, _>()

    fun x ->
        if cache.ContainsKey(x) then
            let result = f x
            cache.[x] <- result

let fastNegate = cache negate

We’re pretending that ‘negate’ is an expensive function that we want to avoid calling unnecessarily, so we use the ‘cache’ function to wrap ‘negate’ with some caching behaviour. Negate takes one argument. What happens when we try to cache a function that takes more than one argument, like ‘add x y’?

On first glance it appears to work.

let add x y = 
    printfn "Adding two args"
    x + y

let fastAdd = cache add

val add : x:int -> y:int -> int
val fastAdd : (int -> int -> int)

But if you try to use it the results are, disappointing.

> fastAdd 1 5;;
Adding two args
val it : int = 6

> fastAdd 1 5;;
Adding two args
val it : int = 6

The underlying ‘add’ function is called every time. We can check to see if anything is added to our cache with a ‘printfn’.

let cache f =
    let cache = Dictionary<_, _>()

    fun x ->
        if cache.ContainsKey(x) then
            let result = f x
            cache.[x] <- result
            printfn "Added Item to cache, Items now in Cache: %d" cache.Count

> fastAdd 1 2;;
Added Item to cache, Items now in Cache: 1
Adding two args
val it : int = 3

> fastAdd 1 2;;
Adding two args
val it : int = 3

> fastAdd 2 1;;
Added Item to cache, Items now in Cache: 2
Adding two args
val it : int = 3

That’s odd. The first time we call the function, something is added to the cache. The second time, using the same values, nothing is added to the cache. When we try different arguments another item is added to the cache. This suggests the cache is being used.

Remember that functions in FSharp are curried, which means that a function which takes two arguments (like add) is translated (curried) into a series of functions which each take a single argument.

So, when we try to cache

add x y

what we actually cache is the partially applied function

add x

We can test this. As long as we keep the same value for x, the fastAdd function will use the cached version. As soon as we change x, we get a new partially applied function that is different to the one in the cache. We can see this in the example above. It is the change in x from 1 to 2 that triggered the addition of a new item to the cache.

So, we’re not actually caching our *expensive* add function at all. We’re just caching the partial application of it.

We could rewrite our ‘add’ function so that it takes one argument, a tuple.

let add (x, y) =
    x + y

let fastAdd = cache add

> fastAdd (1, 2);;
Added Item to cache, Items now in Cache: 1
val it : int = 3

> fastAdd (1, 2);;
val it : int = 3

> fastAdd (1, 3);;
Added Item to cache, Items now in Cache: 2
val it : int = 4

We’ve ‘uncurried’ the function. Now everything works. But it’s still no good. We’ve duplicated our add function, and remember this all relates to functions that are a lot more complicated than addition.

We could wrap the original curried function so the logic isn’t duplicated. We’re really just putting an adapter around it to change it’s signature.

let add x y = 
    printfn "Adding two args"
    x + y

let uncurriedAdd (x, y) =
    add x y 

let fastAdd = cache uncurriedAdd

val add : x:int -> y:int -> int
val uncurriedAdd : x:int * y:int -> int
val fastAdd : (int * int -> int)

> fastAdd (1, 3);;
Adding two args
Added Item to cache, Items now in Cache: 1
val it : int = 4

> fastAdd (1, 3);;
val it : int = 4

That’s still rubbish though. The signature of ‘fastAdd’ is different to ‘add’, so it isn’t an alternative. If we think in terms of higher order functions, ‘add’ and ‘fastAdd’ have different types. We can’t pass ‘fastAdd’ to a function that is expecting ‘add’ and expect things to just work.

We could write a ‘cache2’ function that follows the same pattern as ‘cache’ but works with functions of two arguments. That will work but it’s a shame not to use the working cache function that we already have.

Feel free to stop reading and figure out a solution. What follows is one way of doing it.

The solutions above weren’t good enough, but we were on the right track. Uncurrying the ‘add’ function to make it compatible with our cache is fine, although we shouldn’t have to write a specific function each time we need to uncurry a function. Through the magic of higher order functions we can write the following.

let uncurryTwoToOne f (x, y) = f x y

That allows us to write the following.

let uncurriedAdd = uncurryTwoToOne add

That saves us doing the uncurrying individually for each function. It still leaves us with a function that isn’t compatible with the original signature of Add. So, caching it is still no good. Remember the ‘cache’ function doesn’t change the signature, it takes a function that accepts one argument and it wraps it to add caching, but it maintains the same signature. That way, the cached version can be used anywhere the original is used.

It looks like we need to wrap the cached version of ‘add’ in yet another function to convert the signature back to curried form. Another higher order function to the rescue.

let curryOneToTwo f x y = f (x, y)

And now we finally have a working solution.

let fastAdd = add |> uncurryTwoToOne |> cache |> curryOneToTwo

> fastAdd 1 3;;
Adding two args
Added Item to cache, Items now in Cache: 1
val it : int = 4

> fastAdd 1 3;;
val it : int = 4

Note that in the ‘fastAdd’ function we are not piping the result of ‘add’ through the chain of functions, the actual ‘add’ function itself is the value. Each function in the chain is passed a function which it wraps before passing it on. Like building up the layers of an onion.

It seems like we should be able to make ‘fastAdd’ into a general purpose higher order function too.

let curried2 f = f |> uncurryTwoToOne |> cache |> curryOneToTwo

Putting it all together. We get the following

open System.Collections.Generic

let uncurryTwoToOne f (x, y) = f x y

let curryOneToTwo f x y = f (x, y)

let cache f =
    let cache = Dictionary<_, _>()

    fun x ->
        if cache.ContainsKey(x) then
            let result = f x
            cache.[x] <- result
            printfn "Added Item to cache, Items now in Cache: %d" cache.Count |> ignore

let cache2 f = f |> uncurryTwoToOne |> cache |> curryOneToTwo

let add x y = 
    printfn "Adding two args"
    x + y

let fastAdd = cache2 add

> fastAdd 1 3;;
Adding two args
Added Item to cache, Items now in Cache: 1
val it : int = 4

> fastAdd 1 3;;
val it : int = 4

> fastAdd 1 4;;
Adding two args
Added Item to cache, Items now in Cache: 2
val it : int = 5

> fastAdd 1 4;;
val it : int = 5

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 ?"

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.

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.


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

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)

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)

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.