What on earth has happened to NuGet?

After several months away from NuGet, I had to use it again recently in VS2015. I’m completely and utterly gobsmacked at how poor the current experience is. It’s confusing, inconsistent and hard to use. Worse than that, it enables workflows that should never, ever be permitted within a package management system.

First experiences with the NuGet dialog

When I first saw the previews of VS2015, I thought that the non-modal, integrated dialog into VS would be a good thing. Unfortunately, it suffers from not making it clear enough what the workflow is. You’re bombarded with dropdowns that sometimes have only one option in them, search boxes in non-intuitive positions, installation options that you don’t want to see etc.

Let’s start by adding a package to a solution. This is a common task so should be as easy as possible. Here I’m adding my old friend Unity Automapper to two projects in a solution (note that I’ve deliberately downgraded to an earlier version of the Automapper) :-

nuget1Why so many options? Why a dropdown for Action that only has one item in it? What does the “Show All” checkbox do – looks like nothing to me at this point. Are there projects hidden from the list? Why?

Working with packages

Next let’s try to do something to the package e.g. uninstall or update. You go to Manage Packages for Solution. You don’t see the packages that you’ve already – instead, you see all packages available, ordered by (I assume) most popular download. My installed package is nowhere to be seen. How do I find installed packages only? Oh. You have to click “Filter” and then select “Installed”. That’s not what I thought of doing when I selected the menu option. I thought it would just show it to me – it took me a good few seconds to realise what had happened!

Also notice that the default dependency behaviour is “lowest” – I don’t like this. Highest should be the default, or maybe Highest Minor. Nine out of ten times you’ll just have to upgrade them all immediately afterwards anyway. Which brings me nicely onto the subject of upgrading NuGet packages…

Upgrading dependencies

So now I’ve found my package, I want to upgrade it. So I choose to manage packages for solution, and change the action from Uninstall to Update. It picks the latest version available (good).

nuget2But then notice in the screenshot above it allows me to uncheck some of the projects within the solution. What?? Why would you want to explicitly upgrade only some of the projects within the solution! I can maybe think of some corner cases, but generally this is a definitely no-no – a recipe for absolute disaster. At best you’ll muddle on with some binding redirects, at worst you’ll get a runtime error at some indeterminate time in the future when you try to call a method that doesn’t exist. What happens if you have a breaking change between the two? Which version will get deployed? Can you be sure? Don’t do this. Ever. I can’t even understand why NuGet offers you as the user to do this.

Even worse, if you choose to update a NuGet dependency at the project level (by e.g. right clicking the references node in VS), VS will upgrade it on that project alone. The other projects that have that dependency will be left untouched. You’ll end up with different versions of a dependency in a solution without you even realising it.

But let’s see what happens if we decide to live dangerously and go ahead anyway. Firstly, NuGet will happily upgrade half our solution and leave the other half in an old state – no warnings of impending doom, no nothing. Your code might work, it might not. Maybe it’s work fine for some weeks, and then you’ll realise that the upgrade has a breaking change, but you only notice this when project A tries to call a method that no longer exists.

The next time you next enter the NuGet panel to work with your dependencies – e.g. to uninstall the dependency, you’ll see the following: –

Nuget3Why is only one of my two projects showing in the list of projects that I want to uninstall? Because it’s filtering it on that specific version of the dependency (1.1.0). I have to choose the version that I want to uninstall. I don’t want that – I just want to uninstall the entire dependency. But no, we have to do it version by version. If we now change the Action to “Update”, the Version dropdown suddenly has a different meaning. It no longer acts as a filter – it’s now stating what version we’ll upgrade to. Instead, you now filter based on the projects checked in the list below. So the meaning of each user control has changed based on the action you’re performing. This is not good UI design.

UI Thoughts

In fact, the UI as a whole is really, really confusing. There are also other issues – it’s slow. You can’t upgrade all projects through the UI yet, so either you have to fall back to the Package Manager console, or upgrade each package one by one. Of course, after you do any single update, the UI reverts back to showing “All” packages which involves loading the top results from NuGet. This takes a few seconds. Then you need to change the dropdown to show “Installed” packages, and start all over again.


I’m really worried having seen the new NuGet now. It’s been in VS2015 for a while – and developers are putting up with this? It’s slow. It’s not a well designed UI – even I can tell that. You don’t feel like you know what is actually going to get deployed. The workflows don’t really work. It’s not good.

And it’s not just the UI that concerns with me NuGet. It’s also the fundamental structure underneath it that is unchanged and needs to be fixed. NuGet should be managing dependencies across an entire solution as the default and ensuring that dependencies across projects are stable. Instead, we have individual package.config files on each project, each with their own versions of each dependency. This is not what you want! As illustrated above, it’s very possible – and in fact quite likely on a larger project – that you’ll quickly end up with dependencies across projects with different versions. I’ve seen it lots of times. You run the risk of getting runtime bugs or crashes, and worse still, ones that might only be identified when you go down a specific code path in your app, probably the day after it goes live.

I was hoping that NuGet in VS2015 would start to address these issues, but unfortunately it seems like a large step backwards at the moment.

MBrace, CloudFlows and FSharp.Data – data analysis made easy

In case you’ve not seen it before, MBrace is a simple programming model for scalable cloud data scripting and programming with .NET. It’s written in F#, but has growing support for C# and VB .NET. Over the past year or so, I worked closely with the MBrace team to help get it working smoothly on Microsoft Azure, using features such as Service Bus and Storage to provide an excellent development and deployment experience. As MBrace gears up for a v1 release, the design of the API is looking extremely positive.

I’m going to demonstrate here a simple example that illustrates how easy it is to start working with a large CSV file available on the internet in an MBrace cluster, parsing and querying data easily – we’re going to analyse UK house prices over the past year (this file is freely available on the gov.uk website).

I’m going to assume that you have an MBrace cluster up and running – if you don’t, you can either use a local development cluster or download the latest source code and deploy a full cluster onto Azure using the example MBrace Worker Role supplied in the MBrace Azure source code.

Type Providers on MBrace

We’ll start by generating a schema for our data using FSharp.Data and its CSV Type Provider. Usually the type provider can infer all data types and columns but in this case the file does not include headers, so we’ll supply them ourselves. I’m also using a local version of the CSV file which contains a subset of the data (the live dataset even for a single month is > 10MB): –

In that single line, we now have a strongly-typed way to parse CSV data. Now, let’s move onto the MBrace side of things. I want to start with something simple – let’s get the average sale price of a property, by month, and chart it.

A CloudFlow is an MBrace primitive which allows a distributed set of transformations to be chained together, just like you would with the Seq module in F# (or LINQ’s IEnumerable operators for the rest of the .NET world), except in MBrace, a CloudFlow pipeline is partitioned across the cluster, making full use of resources available in the cluster; only when the pipelines are completed in each partition are they aggregated together again.

Also notice that we’re using type providers in tandem with the distributed computation. Once we call the ParseRows function, in the next call in the pipeline, we’re working with a strongly-typed object model – so DateOfTransfer is a proper DateTime etc. All dependent assemblies have automatically been shipped with MBrace; it wasn’t explicitly designed to work with FSharp.Data – it just works. So now that we have an array of int * float i.e. month * price, we can easily map it on a chart: –


Persisted Cloud Flows

Even better, MBrace supports something called Persisted Cloud Flows (known in the Spark world as RDDs). These are flows whose results are partitioned and cached across the cluster, ready to be re-used again and again. This is particularly useful if you have an intermediary result set that you wish to query multiple times. In our case, we might persist the first few lines of the computation (which involves downloading the data from source and parsing with the CSV Type Provider), ready to be used for any number of strongly-typed queries we might have: –

So notice that the first query takes 45 seconds to execute, which involves downloading the data and parsing it via the CSV type provider. Once we’ve done that, we persist it across the cluster in memory – then we can re-use that persisted flow in all subsequent queries, each of which just takes a few seconds to run.


MBrace is on the cusp of a 1.0 release – it’s ready for you to start using now, and offers not only a powerful and flexible set of abstractions for distributed computations, but as you can see from above, if you’ve used the collection libraries in F# before it’s a very smooth transition to make the leap to distributed collection queries. In less than ten lines of code, you can start writing distributed queries against live datasets with the minimum of effort.

Stateless services on Azure Service Fabric in F#

In my previous posts, I discussed the use of the Service Fabric (SF) actor framework (which is loosely based on Orleans) and F#, and how we can use FP features within an actor model, even one designed for OO languages.

Exposing Services with Service Fabric

Ironically, the actor framework with SF is one of its more complex features – you can use SF to host literally any .NET code you want. There are a number of features within SF designed to allows you to rapidly host scalable systems, with support for state replication out-of-the-box. In this post, I want to illustrate the steps needed to host the F#, FP-first web server Suave in Service Fabric. It turns out that there’s really not much code needed at all.

  1. We create an F# executable that is compatible with Service Fabric.
  2. We create a service that inherits from the StatelessService class (we’ll discuss Stateful Services in another post).
  3. We override the CreateCommunicationListener method. This is important – essentially this method’s responsibility is to create an object that can handle incoming traffic from external sources. We also make a note of the port that Suave will be running on.
  4. We configure an endpoint in the Service Fabric configuration for that same port. This tells SF to allow inbound traffic in. This is roughly analogous to opening up an endpoint in Cloud Services. This is something you should have also specified when creating the cluster itself in Azure (if not, you’ll need to manually configure the load balancer to allow traffic through).
  5. In our Main program, we register the service with SF.

The key part is (3), where we implement the functionality that should get called to handle incoming requests. It’s pretty basic really: –

So CreateCommunicationListener() expects an instance of ICommunicationListener that will create the web server for us. Luckily with F#’s object initializers we don’t even have to declare a formal type – we can simply create the object on the fly. As you can see, all it does is start up Suave using default settings. You might elect to supply the port that it starts on from the endpoint configuration in Service Fabric – this is done in the Initialize method, and is included in the full sample.

Once done, you can configure the scalability of the service in config – if you want three instances, just set the instance attribute to 3 in the ApplicationManifest file of your hosting Service Fabric application. If you want it on every node, you set the attribute to -1 (because we all know that -1 is the universal standard for “absence of a number” – we don’t need no option types ;-). Note that running this locally with multiple instances won’t work, since they all try to run on the same port, but in the real world it’d work fine I’m sure.

As an aside, if you want any arbitrary service that doesn’t necessarily need incoming traffic e.g. something subscribing to service bus or writing to a DB, you don’t have to implement anything regarding ICommunicationListener. There’s simply a RunAsync() method that you can put any code inside that you want.

So, there you have Suave in Service Fabric with a minimal amount of code. For this you’ll get an auto-load balancing, scalable and automatically healing service. In my next post, I’ll demonstrate StatefulServices and how we can use them to automatically manage state across a cluster of services.

Building Azure Service Fabric Actors with F# – Part 2

In Part 1, I provided an overview of what Service Fabric (SF) is, and provided some step-by-step guidance on how to get up and running with the Service Fabric local installation. In this post, I want to move from the infrastructure to the code, and show how we can use F# with an Actor model designed primarily for C# and VB .NET, whilst still retaining an idiomatic F# feel where possible.

All code for the full sample used as the basis for this series is available here.

Actors in Service Fabric

Firstly, I’ll show you some elided examples of how we modelled some features of my cat as an Actor in Service Fabric. Every cat has some state which is affected by actions it does, and needs to be persisted across calls. In Service Fabric, we call this a “stateful” actor. After every “state-updating” action (in SF terms, this equates to a method call on the actor), SF will automatically persist your state back to disk and automatically replicate to other nodes in the SF cluster (typically at least two others); if your primary node goes down, one of the secondaries will immediately take over and the failed node will be silently replaced in the background. You can also have so-called “read only” actions, which do not modify state but typically return some payload to the caller. You can typically think of these as “getter” methods / properties on a class. You’ll normally have a mix of both state-mutating and read-only methods on a given actor.

Implementing Stateful Actors in F#

Every stateful Actor in SF inherits from the type Actor<T>, where T is the state that needs to be persisted. It shows up as a member property on the actor, State. Service Fabric will automatically create one of these when starting every given actor, and silently persist / load it across calls etc.

We’ll start by modelling the state on the Actor by default with a standard OO class in F# – see below. Notice the DataContract and DataMember attributes – these are used by the persistence layer of SF to de/re-hydrate state to an Actor. Personally I’m not particularly fond of these attributes – there are plenty of serialization frameworks out there that seem to work just fine without decorating every single property, so why are we stuck with this old-school approach? Perhaps there’s a way to replace the serialization in SF – I haven’t tried yet.

Anyway, here’s an example method on Cat, called Jump(). It takes in a destination of where the cat is jumping to, and depending on the destination, this affects the cat – and the owner’s – Happiness (in a more fully featured model, the owner themselves would probably be an actor with their own state). The cat will also work up an appetite by Jumping(). Hunger can be alleviated by Feeding() the cat.

On the one hand, F# works nicely with interfaces – we still don’t have to specify types, as they are inferred from the interface we’re implementing. However, this sample is still somewhat unsatisfactory to me as an F#-first person: I’m used to creating copies of data from other data, not mutating it. I also don’t like this approach of modifying state in several places arbitrarily – I feel uneasy when seeing code like this. It seems very statement oriented, with side effects everywhere – something I struggle to reason about easily. There must be something better!

Use immutable data structures on Actors

As it turns out, there is. Notice that up until now we’ve basically written everything in an OO style, using standard C#/ VB constructs like classes etc. – we’ve not used any F# types. We can actually use many F# features without too much fuss, and they can quickly help us out in our quest to getting back to sane and easy-to-reason-about code.

Firstly, we can change the way we model our state from a class to an F# record. This actually works without any problem, once you do the same WCF-style attribute decoration, and add the [<CLIMutable>] attribute – this is necessary as although Records boil down to standard Classes, by default there’s no public setter on any properties, so SF can’t rehydrate state by default. We can also add in other F#-only features, like units of measure, if we want – as these are a compile-only feature, there’s no issue with serialization of them.

On their own, using records within SF only works up to a point – we’re forced to make copies of state, rather than mutating the single attributes of the State member multiple times, which is a good thing. However, it still looks undesirable – we’re now just mutating the State member property on the Actor instead! Plus it’s not clear when and where we should replace the contents of the State member within the method – every time? Once at the end of the method call? Something in between?

Adapting functional patterns into Actors

Let’s take a step back and think about the two types of methods I mentioned earlier on – state-updating and read-only calls. The former intends to do some processing, and update the State of the actor. The latter typically reads from the State and returns some data to the caller (I’m setting aside things like calling external dependencies etc. which for simplifies’ sake we can ignore – plus it really doesn’t affect us here as we would partially apply our functions with dependencies). We can formally specify such actions and implement them with something like this: –

Notice how now our functions are much simpler – Jump is made up of a single expression that generates the new State of the Actor, based on the input state and distance – we’re no longer mutating state multiple times, or even once. And because State is an immutable record, it’s impossible to modify the supplied input State ever.

Plugging pure functions into Actors

Now that we’ve formalised how we see our actor methods working, we can re-write our earlier code from the anything-goes, mutate-everywhere C# style to one that is easier to test, easier to reason about and more idiomatic from an FP, F# point of view. You’ll notice that the implementation code above is back in a module – so how do we plug this into our OO Actor model?

There are a few ways, but the easiest one is with the help of a couple of shim functions that tightly control the mutation of the Actor State, whilst delegating control to our purely functional code for business logic. Our core code is kept free from worrying about the mutation of state and is performed in a consistent manner; our SF Actor model simply delegates to them.

A word on Read-Only Service Fabric methods

Another point worth mentioning are Read Only methods in Service Fabric. These are methods that you, as the developer, tell the SF runtime “I will never amend state in this method – don’t try to persist state at the end of the call”. This is achieved in SF simply by placing the [<Readonly>] attribute on the method. I don’t like this much for two reasons. Firstly, the attribute differs from the System.ComponentModel [<ReadOnly>] attribute simply by virtue of the fact that it has a different casing on one of the characters in the type. Use the wrong one accidentally and things will quickly go pop with your actor (believe me – I did it during the creation of the code referenced in this post; the error that you get isn’t helpful either). The other, more dangerous issue is that there is no compile time safety around the use of the [<Readonly>] attribute. If you decide to start changing state in one of these calls – tough. You won’t get any support from the compiler, nor from the runtime. Your method simply won’t update state and you’ll be left wondering why your application isn’t behaving correctly.

With the “adapt to a functional style” approach, whilst we don’t eliminate the issue completely – you still have to decorate the methods appropriately – we at least get compile-time checking on read-only functions, because they don’t allow us to return state; you therefore can’t accidentally modify the state of an actor. In addition, because we’re now using records, which are themselves immutable, it’s impossible for us to modify the state that was supplied to us.

For a simple example like the one supplied, one could argue that the extra delegation and modules etc. complicates matters compared to e.g. C# / OO. However, once you start writing even mildly complicate business logic, it quickly becomes a tiny cost compared to the simplification you benefit from through immutability, records etc.. as well as the usual other benefits of F#.

Taking it further

You can take this approach even further – in other actor frameworks, rather than adopting the “method-per-action” approach, a more functional approach is to have a single message which is itself a discriminated union containing all the different messages ; we then pattern match on this in order to process the message appropriately. We can apply this sort of pattern for updating-state messages, although it isn’t exactly idiomatic SF actor code (I’ve supplied an example in the source code).

Another alternative might be to create a custom Computation Expression (perhaps similar to the Writer monad that Tomas Petricek blogged about many moons ago) in order to make this modification to state even more succinct. Perhaps someone could write one ;-)


We’ve seen how we can marry up some features inherent to the F# type system in order to enforce a cleaner way of reasoning about the code that our actors have to implement, through a couple of simple function signatures and some simple adaptors. We’ve also seen how F#, and typical FP paradigms, can be used in an reliable and distributable framework designed for a mutable-first OO consumer.

In part three, I want to illustrate how we can quickly and easily host arbitrary services on top of Service Fabric in F# for just about any code you might want to write, and how we can easily scale it to large volume.

Building Azure Service Fabric Actors with F# – Part 1

This post is the first part of a brief overview of Service Fabric and how we can model Service Fabric Actors in F#. Part 1 will cover the details of how to get up and running in SF, whilst Part 2 will look at the challenges and solutions to modelling stateful actors in a OO-based framework within F#.

What is Service Fabric?

Service Fabric is a new service on Azure (currently in preview at the time of writing) which is designed to support reliable, scalable (at “hyper scale”) and maintainable distributed applications and services – with automatic support for things like replication of state across nodes, automatic failover & recovery and multi tenanting services on the same instances. It supports (currently) both stateful and stateless micro-services and actor model architectures (more on this shortly). The good thing about Service Fabric (SF) from a risk/reward point of view is that it’s not a new technology – it actually underpins a lot of existing Azure services themselves such as Azure SQL, DocDB and even Cortana, so when Microsoft says it’s a reliable and scalable technology, they’ve been using it for a while now with a lot of big services on Azure. The other nice thing is that whilst it’s still private preview for running in Azure, you can get access to a locally running SF here. This isn’t an emulator like with Azure Storage – it’s apparently the “full” SF, just running locally. Nice.

Actors on Service Fabric

As mentioned, SF supports an Actor model in both stateful and stateless modes. It’s actually based on the Orleans codebase, although I was pleasantly surprised to see that there’s actually no C# code-generation whatsoever in SF – the only bit that’s auto-generated are some XML configuration files which I suspect will be pretty much boilerplate for most people and rarely change.

Why would you want to try SF out? Well, simply put, it allows you to focus on the code you write, as opposed to the infrastructure side of things. You spin up an SF cluster (or run the local version), deploy your code to it, and off you go. This is right up my alley, as someone who likes to focus on creating solutions and sometimes has little patience for messing around with infrastructural challenges or difficulties that prevent me from doing what I’m best at.

Getting up and running with Service Fabric

I’ve been using Service Fabric for a little while now, and spent a couple of hours getting it up and running in F#. As it turns out, it’s not too much hassle to do aside from a few oddities, which I’ll outline here: –

  • Download and install VS2015. Community edition should be fine here. You’ll also need WIndows 8 or above.
  • Download and install the SDK.
  • Create a new Service Fabric solution and an Stateful Actor service. This will give you four projects: –
    • A SF hosting project. This has no code in it, but essentially just the manifest for what services get deployed and how to host them.
    • An Actors project. This holds your actor classes and any associated code; it also serves as a bootstrapper that deploys the appropriate services into SF; as such, it’s actually an executable program which does this during Main(). It also holds a couple XML configuration files that describe the name of the package and each of the services that will be hosted.
    • An Interfaces project. This holds your actor interfaces. I suspect that this project could just as easily be collapsed into the actors one, although I suppose for binary compatibility you might want to keep the two separate so you can update the implementations without redeploying the interfaces to clients.
    • A console test project. This just illustrates how to connect to the Service Fabric and create actors. In the F# world these projects serve zero purpose since we can just create a script file to interact with our code, so I deleted this immediately.
  • Convert to Paket (optional). If you use Paket rather than Nuget for dependency management, change over now. The convert-from-nuget works first time; you’ll end up with a simplified packages file of just a single dependency (Microsoft.ServiceFabric.Actors), plus you’ll get all the other benefits over Nuget.
  • Create F# project equivalents. The two core projects, the Actors and Interfaces projects, can simply be recreated as an F# Console App and Class Library respectively. The only trick is to copy across the PackageRoot configuration folder from the C# Actors project to the equivalent F# one. Once you’ve done this, you can essentially disregard the C# projects.
  • Configure the F# projects. I set both projects to 4.5.1 (as this is what the C# ones default to) – I briefly tried (and failed) to get them up and running in 4.5.2 or 4.6. Also, make sure that both projects target x64 rather than AnyCPU. This is more than just changing the target in the project settings – you must create a Configuration (via Configuration Manager) called x64!
  • Create an interface. This is pretty simple – each actor is represented by an interface that inherits from IActor (a marker interface). Make sure that all arguments in all methods all have explicit names! If you don’t do this, your actors will crash on initialisation.
  • Create the implementation. Here’s an example of a Cat actor interface and implementation.

  • Update the Hosting project. Reference the implementation from the Hosting project and update the configuration appropriately.

Luckily, I’ve done all of this in a sample project available here.

Running your project

Once you’ve done all this, you can simply hit F5 (or Publish from the Host project) and watch as your code is launched into the Fabric via the UI.

SFEYou can then also call into your actors via e.g. an F# script:-

I’m looking forward to talking more about the coding side of this in my next post, where we can see how code that is inherently mutable doesn’t always fit idiomatically into F#, and how we can take advantage of F#’s ability to mix and match OO and FP styles to improve readability and understanding of our code without too much effort.

Inventing new measures of time with F#

A short interlude from my little “solving games in F#” series today.

I’ve recently moved house and was trying to figure out how long it would take to get to work. I started thinking about this problem in terms of minutes until I realised that I really wanted to calculate it in a much more important measure of time – Dream Theater songs. This is a new unit of time I have recently devised. Each unit represents the average time to listen to a single Dream Theater song. So a journey to the shops might be 2 Dream Theaters, whilst going to work might be a few more of them (If you’ve ever listened to Dream Theater, you’ll know that a typical piece might last anywhere from 3 or 4 minutes up to some 25 minutes epics).

I started by defining some common units augmenting the inbuilt units supplied with F#, along with some simple conversions: –

I didn’t want to just guess what a DT really is, so of course it’s F# to the rescue. First thing, let’s calculate the average duration of a single Dream Theater song. Where do we get that data? Wikipedia, of course. A short while later, and we have the DT wikipedia page saved locally, which contains a nice HTML table with all songs, and their lengths. After a tiny bit of cleaning up the HTML to remove some extraenous elements, we can now do use the HTML type provider in FSharp.Data to do something like this: –

So, now that we’ve determined that the average length of a Dream Theater song is 8.44 minutes, let’s calculate my journey to work in DTs:

On average I can listen to just over 5 Dream Theater epics on my way into work. Or in other words, my door-to-door journey from home to work takes around 5.33 DTs :)

Determining graph sizes efficiently with F#


Continuing on with my gaming-in-F# post, this week’s post is derived from this challenge. The initial challenge is, for each node, to determine the “efficiency” of a node within a network, that is, to calculate the maximum number of hops it takes to reach all edges of the graph starting from that node. So given the graph below, starting from node 3, it’s 2 hops (in this case, to all edges i.e. 1, 5, 6 and 8). However, if you were to start at, say, node 2, it’d be 3 hops (1 hop to node 1, but 3 hops to nodes 5, 6 and 8). Therefore, node 3 is considered a more “efficient” node. Secondly, you should determine the most efficient node in the whole network – the objective being to calculate the most effective starting spot in a graph from which to reach all other nodes in the entire network.


Disclaimer: I should mention that, whilst I’ve been writing coding for a number of years, the degree I took was not heavily computer-science related – so things like big O notation, complexity theory etc. – all these are things I’ve learned over the year but never formally studied. So some of things below may seem second nature to you if you come from more of a maths background!

I identified three main elements in solving this challenge.

Representing the data

Relations are provided as as a simple int * int tuple i.e. (1,3) means that there’s a (bi-directional) connection between nodes 1 and 3. So I build a simple Map<int, int []>, which is essentially a lookup that says “for a given node, give me the list of connected nodes”. Note that I decided not to use a “proper” representation of the graph here – an idiomatic way might have been a discriminated union with Node and Leaf etc. etc… – a simple Map proved enough for me.

Implementing the algorithm

Firstly, implement the logic to calculate the maximum distance to all edges, for every starting point in the graph. I solved this with (allegedly) what is essentially a recursive depth-first search. In other words, navigate from the starting point as far outwards as you can; then, walk back in until you find another branch, and go out there. Once you start walking back in, start counting how many steps it is until you reach a branch point. Once you have calculated the distance all of branches, take the largest one.  Repeat this until you have exhausted all points in the graph and walked back to the starting point.

It should be now a simple task to simply apply this algorithm to all nodes in the graph, and then take the smallest one – this is the most efficient point in the graph from where to start.

Improving efficiency

Note that this wasn’t my first solution! The biggest challenge came when one of the exercises in the website provided a large set of connections in the graph – say, 30,000. At this point, my algorithm simply didn’t perform, so I had to look at some ways to improve performance. I tried a load of different things, each of which yielded some performance improvement, but not enough: –

  1. Moving from Sequences to Arrays. Sequences are flexible and sometimes very useful, but Arrays generally will outperform it for maps and filters etc., particularly if you are repeating an operation over the same sequence many times (although there is Seq.cache).
  2. Added state tracking. For each starting point, I would record the efficiency, and then provide that number to the next starting point. Whenever I encountered a graph that had a size at least equal to the score of the “most efficient node” found so far, I would immediately stop looking at that node and backtrack all the way out. This provided a good boost in performance, but not enough.
  3. I also experimented with either minor algorithmic improvements, such as prematurely exiting a particular route of the graph if we identified any single route that exceeded the current best size rather than iterating all children nodes and evaluating them together.

None of these solutions gave an optimal solution – all they did was increase the complexity of the solution at the cost of moderate performance gains. I realised that there must be another approach that I was missing that would provide the solution. Eventually I realised how I could probably largely improve efficiency – because when you start from two separate nodes, there’s usually a large amount of repeated traversals across them both. Take the above graph – you can view the network efficiency of e.g. node 3 as either described above, or as (the highest efficiency of all adjacent nodes for that subset of the graph) + 1.

In the image below, we know that Node 3 has an efficiency of 2 because the efficiency of Node 4 is 1, Node 7 is 1 and Node 2 is 1. Take the maximum of these (1), add 1, and we get 2.

fileservlet4So, given this, why not simply cache the results for every backtrack score from each pass? We can modify our above traversal code with some memoization backed by a simple Dictionary (apologies for using a mutable Dictionary – you could probably use an immutable Map if you wanted, although performance would probably suffer a bit) and then before making any outward facing movement in the graph, we check if that movement has already been made – if so, we can just use that result. This is why the final algorithm counts inwards from the edges rather than outwards – in order to allow caching of distances.

You can see from the logging messages above that although it should take 7 steps to calculate the efficiency of any given starting node, it only takes two calculations + one cache hit when calculating efficiency the second time, and two calcs + three cache hits the third time. Notice also the simplicity of the caching layer – types are (as usual) inferred by the compiler, and automatic generalization is used here too (e.g. notice that the Dictionary never has type arguments supplied) – it just works.

In terms of performance, you can observe the effect that the caching has for varying network sizes below. Notice that the graph is scaled logarithmically – for more than around 20 relationships, the cost of not caching becomes enormous as a single cache hit can save literally thousands of steps walking the graph.


I found this to be a stimulating challenge to solve. It wasn’t necessarily because of the challenge of some specific domain solving issue but rather one regarding optimising a solution in a specific manner i.e. caching. What I particularly liked was that F# allowed us to retain the overall feel of the algorithm, but add in the caching layer very easily. In addition, adding in caching allowed me to simplify the overall algorithm – I didn’t need to worry about making four or five small, specific improvements – instead, a single optimisation allowed me to combine it with a simpler algorithm, yet still get a massive performance boost.