Rash thoughts about .NET, C#, F# and Dynamics NAV.

Letzte Woche habe ich im Rahmen der F# Gruppe der .NET Online User Group einen Vortrag zu “Higher-Order-Functions in C#” gehalten. Unter http://vimeo.com/17048170 ist die Aufzeichnung nun zu finden.

Funktionale Programmiersprachen nehmen seit geraumer Zeit einen hohen Stellenwert in der Wissenschaft ein. Mittlerweile ziehen viele der funktionalen Konzepte bereits in den Mainstream ein. Bei diesem Treffen wollen wir einen Einblick in funktionale Konzepte und deren Umsetzung in C# gewinnen. Insbesondere soll auf "Funktionen höherer Ordnung", "Pattern Matching", "Unveränderlichkeit" und parallele Programmierung eingegangen werden.

Vortragsabstract

Today I’m starting a new blog post series about solving code katas in F# and with the help of my NaturalSpec project. A code kata is a programming exercise which helps to improve your skills through practice and repetition. In this series we want to use the Test Driven Development TDD approach which means in the context of NaturalSpec that we have to write our specs before we implement the algorithm.

Problem Description

“The game of yahtzee is a simple dice game. Each round, each player rolls five six sided dice. The player may choose to reroll some or all of the dice up to three times (including the original roll). The player then places the roll at a category, such as ones, twos, sixes, pair, two pairs etc. If the roll is compatible with the score, the player gets a score for this roll according to the rules. If the roll is not compatible, the player gets a score of zero for this roll.

The kata consists of creating the rules to score a roll in any of a predefined category. Given a roll and a category, the final solution should output the score for this roll placed in this category.”

[codingdojo.org]

Category 1 – Ones, Twos, Threes, Fours, Fives, Sixes

“Ones, Twos, Threes, Fours, Fives, Sixes: The player scores the sum of the dice that reads one, two, three, four, five or six, respectively. For example, 1, 1, 2, 4, 4 placed on "fours" gives 8 points.”

After reading this category description we could come up with the following spec:

Since we really want to implement six different categories we should also add some more scenarios like this one:

Now we have some specs but they will all fail since we don’t have anything implemented yet. So we have to come up with a model of dice rolls and categories. As the specs suggests we model the dice roll as a tuple of ints and the category as a discriminated union:

The tuple is a natural choice for the dice roll, but for easier calculation we add a helper function which converts it into a list. This allows use to use the standard list functions and therefore summing the values becomes trivial:

Now we can run our scenarios with any NUnit runner. I’m using the default NUnit GUI runner here, which gives me a picture like this:

Category 2 – Pair

“Pair: The player scores the sum of the two highest matching dice. For example, 3, 3, 3, 4, 4 placed on "pair" gives 8.”

The kata description gives us some new scenarios. As seen above we should specify them before writing the code.

Since we use a new category we now have to extend our model and the calcValue function:

Category 3 – Two pairs

“Two pairs: If there are two pairs of dice with the same number, the player scores the sum of these dice. If not, the player scores 0. For example, 1, 1, 2, 3, 3 placed on "two pairs" gives 8.”

Implementing this category is a little bit tricky but with the help of our Pair function and some more standard sequence combinators we can get our spec green:

Category 4 – Three of a kind

“Three of a kind: If there are three dice with the same number, the player scores the sum of these dice. Otherwise, the player scores 0. For example, 3, 3, 3, 4, 5 places on "three of a kind" gives 9.”

Now it is time to refactor our code. The sumAsPair function should be extended to a sumAsTuple function:

Category 5 – Four of a kind

“Four of a kind: If there are four dice with the same number, the player scores the sum of these dice. Otherwise, the player scores 0. For example, 2, 2, 2, 2, 5 places on "four of a kind" gives 8.”

With the help of the takeBestTuple function this becomes trivial:

type Category =

| Ones

  // …

| FourOfAKind

let calcValue category roll =

      // …

    | FourOfAKind  -> takeBestTuple 4 list

Category 6 – Small straight

“Small straight: If the dice read 1,2,3,4,5, the player scores 15 (the sum of all the dice), otherwise 0.”

As in all the above scenarios we don’t assume any specific order in our rolls but for this category it is easier to test if the data is sorted:

Category 7 – Large straight

“Large straight: If the dice read 2,3,4,5,6, the player scores 20 (the sum of all the dice), otherwise 0.”

Of course the implementation is exactly the same as for the small straight:

Category 8 – Full house

“Full house: If the dice are two of a kind and three of a kind, the player scores the sum of all the dice. For example, 1,1,2,2,2 placed on "full house" gives 8. 4,4,4,4,4 is not "full house".”

Implementing the FullHouse category is easy if we reuse our solutions to the Two pairs category:

Category 9 – Yahtzee

“Yahtzee: If all dice are the have the same number, the player scores 50 points, otherwise 0.”

Here we can use NaturalSpec’s ScenarioTemplates in order to specify all Yahtzees:

The implementation is pretty easy:

Category 10 – Chance

“Chance: The player gets the sum of all dice, no matter what they read.”

This seems to be the easiest category as we only have to sum the values:

Conclusion

We used a lot of F#’s sequence combinators, pattern matching and discriminated unions in this kata. I think this shows that F# is very well suited for such a problem and with NaturalSpec we can easily use a TDD/BDD approach.

The complete source code can be found in the NaturalSpec repository.

If you want to know more about a specific part of the kata or NaturalSpec feel free to contact me.

In my last article (Introducing NaturalSpec – A Domain-specific language (DSL) for testing) I used NaturalSpec in two small samples. This time I will show how we can set up a NaturalSpec environment to write our first automatically testable scenarios.

1. Choosing an IDE

The first step is to choose an integrated development environment for NaturalSpec. At the current project status you should be able to use NaturalSpec with Visual Studio 2008, Visual Studio 2010 beta 2, the freely available Visual Studio 2008 Shell or the free IDE SharpDevelop 3.0.

2. Installing the testing framework

As NaturalSpec uses NUnit as the underlying testing framework we have to install NUnit 2.5. I also recommend installing TestDriven.Net in order to get a Unit Test runner within Visual Studio.

3. Installing F#

NaturalSpec is completely written in F# and all specs will also be written in F#. This doesn’t imply you have to learn programming in F# but we need the F# compiler to get things working. You can download the F# October 2009 CTP from the Microsoft F# Developer Center.

4. Downloading the latest version of NaturalSpec

You can download a .zip with the latest NaturalSpec libraries from GoogleCode.

5. Creating a spec

This part is written for using Visual Studio 2008. If you use SharpDevelop or Visual Studio 2008 Shell this might differ in some detail.

Start Visual Studio 2008 and create a new F# class library.

Rename Module1.fs in ListSpec.fs and delete script.fsx from the project:

Create a folder “Lib” and unzip the NaturalSpec libraries into it.

Add NaturalSpec.dll and nunit.framework.dll as references to your project:

Copy the following code into ListSpec.fs:

module ListSpec

open NaturalSpec

[<Scenario>]
let When_removing_an_3_from_a_small_list_it_should_not_contain_3() =
  Given [1;2;3;4;5]
    |> When removing 3
    |> It shouldn't contain 3
    |> Verify

If you have TestDriven.Net installed you can run your spec via right click in the solution explorer:

If you don’t like the TestDriven.Net test runner you might want to use the NUnit GUI runner. The output should look like:

In addition the test runner should produce a Spec output file with the name “Spec.txt” within the same folder.

Summary

In a minimal environment you need SharpDevelop, the F# compiler, NUnit and the NaturalSpec libraries for using NaturalSpec.

In the next post I will show how you can use NaturalSpec to create a spec for C# projects.

This is the third part in a “Questions and Answers”-series about the F# BootCamp in Leipzig. This time we will look at lazy evaluation.

Question 5 – What is the difference between “Lazy Evaluation” and “Eager evaluation”?

Lazy evaluation is a technique of delaying a computation until the result is required. If we use eager evaluation an expression is evaluated as soon as it gets bound to a variable.

One participant answered that lazy evaluation is used in most programming languages to calculate boolean expressions faster. For instance in the expression “x() or y()” the function y() is never called if x() returns true.

Of course this answer is correct, but this "short-circuit evaluation" is only a special case of lazy evaluation. The program would also work correctly without it. But if we want to define an infinite sequence then we can not use eager evaluation. Let’s look at an example:

// val fibs: seq<int>
let fibs = (1, 1) |> Seq.unfold(fun (n0, n1) -> Some(n0, (n1, n0 + n1)))

We do not need to understand the concrete syntax of this code here. We’ll discuss this later. Let’s just say fibs is bound to an infinite sequence (IEnumerable<int>) of Fibonacci numbers. You could also write this in C#:

/// <summary>
/// Infinite sequence of Fibonacci numbers.
/// </summary>
public static IEnumerable<int> Fibs()
{
    var n0 = 1;
    var n1 = 1;
    while(true)
    {
        yield return n0;
        var t = n1;
        n1 = n1 + n0;
        n0 = t;
    }
}

The trick is IEnumerable evaluates the elements lazy. Only at the time we take an element from the sequence the element will be computed:

fibs
  |> Seq.take 10
  |> Seq.to_list
  |> printfn "%A" // prints [1; 1; 2; 3; 5; 8; 13; 21; 34; 55]

If we would use eager evaluation then “Seq.take” would never been called. But we can go one step further. If we want to get the first 10 even-valued terms in the Fibonacci sequence, we can write this code:

fibs 
  |> Seq.filter (fun fib -> fib % 2 = 0) // lazy (via pipe)
  |> Seq.take 10                         // lazy (via pipe)
  |> Seq.to_list                         // eager
  |> printfn "%A" 
  
// prints [2; 8; 34; 144; 610; 2584; 10946; 46368; 196418; 832040]

This would be a little bit tricky if we use eager evaluation, but of course this nice laziness comes with some costs for storing intermediate results (and code). So eager evaluation is still often the better choice and sometimes (e.g. DateTime.Now()) it makes no sense to use lazy evaluation – at least not if we don’t reevaluate the function.

Yesterday I was talking about F# at the .NET Developer Group Braunschweig. It was my first talk completely without PowerPoint (just Live-Coding and FlipChart) and I have to admit this is not that easy. But the event was really a big fun and we covered a lot of topics like FP fundamentals, concurrency and domain specific languages (of course I showed “FAKE – F# Make”).

Now I have a bit time before I go to the next BootCamp in Leipzig. Today Christian Weyer will show us exciting new stuff about WCF and Azure.

In the meanwhile I will write here about another important question (see first article) from the F# BootCamp in Leipzig:

Question 4 – Try to explain “Currying” and “Partial Application”. Hint: Please show a sample and use the pipe operator |>.

Obviously this was a tricky question for FP beginners. There are a lot of websites, which give a formal mathematical definition but don’t show the practical application.

“Currying … is the technique of transforming a function that takes multiple arguments (or more accurately an n-tuple as argument) in such a way that it can be called as a chain of functions each with a single argument”

[Wikipedia]

I want to show how my pragmatic view of the terms here, so let’s consider this small C# function:

public int Add(int x, int y)
{
   return x + y;
}

Of course the corresponding F# version looks nearly the same:

let add(x,y) = x + y

But let’s look at the signature: val add : int * int –> int. The F# compiler is telling us add wants a tuple of ints and returns an int. We could rewrite the function with one blank to understand this better:

let add (x,y) = x + y

As you can see the add function actually needs only one argument – a tuple:

let t = (3,4)         // val t : int * int
printfn "%d" (add t)  // prints 7 – like add(3,4)

Now we want to curry this function. If you’d ask a mathematician this a complex operation, but from a pragmatic view it couldn’t be easier. Just remove the brackets and the comma – that’s all:

let add x y = x + y

Now the signature looks different: val add : int -> int –> int

But what’s the meaning of this new arrow? Basically we can say if we give one int parameter to our add function we will get a function back that will take only one int parameter and returns an int.

let increment = add 1      // val increment : (int -> int)
printfn "%d" (increment 2) // prints 3

Here “increment” is a new function that uses partial application of the curryied add function. This means we are fixing one of the parameters of add to get a new function with one parameter less.

But why are doing something like this? Wouldn’t it be enough to use the following increment function?

let add(x,y) = x + y       // val add : int * int -> int 
let increment x = add(x,1) // val increment : int -> int
printfn "%d" (increment 2) // prints 3

Of course we are getting (nearly) the same signature for increment. But the difference is that we can not use the forward pipe operator |> here. The pipe operator will help us to express things in the way we are thinking about it.

Let’s say we want to filter all even elements in a list, then calculate the sum and finally square this sum and print it to the console. The C# code would look like this:

var list = new List<int> {4,2,6,5,9,3,8,1,3,0};
Console.WriteLine(Square(CalculateSum(FilterEven(list))));

If we don’t want to store intermediate results we have to write our algorithm in reverse order and with heavily use of brackets. The function we want to apply last has to be written first. This is not the way we think about it.

With the help of curried functions, partial application and the pipe operator we can write the same thing in F#:

let list = [4; 2; 6; 5; 9; 3; 8; 1; 3; 0]

let square x = x * x

list
 |> List.filter (fun x -> x % 2 = 0) // partial application
 |> List.sum
 |> square
 |> printfn "%A"                     // partial application

We describe the data flow in exactly the same order we talked about it. Basically the pipe operator take the result of a function and puts it as the last parameter into the next function.

What should we learn from this sample?

1. Currying has nothing to do with spicy chicken.
2. The |> operator makes life easier and code better to understand.
3. If we want to use |> we need curryied functions.
4. Defining curryied functions is easy – just remove brackets and comma.
5. We don’t need the complete mathematical theory to use currying.
6. Be careful with the order of the parameter in a curryied function. Don’t forget the pipe operator puts the parameter from the right hand side into your function – all other parameters have to be fixed with partial application.

Last Friday we had a fantastic LearningByTeaching F# BootCamp in Leipzig. Each attendee got homework and had to solve one theoretical question and one programming task. For this two questions they had to present their results to the rest of us and after this I gave my solution in addition.

It was very interesting to see the different strategies and solutions. In this post series I will discuss the questions and some of the possible solutions.

Question 1 – What is “Functional Programming” in contrast to “Imperative Programming”?

This seems to be an easy question but in fact, the attendees had some problems to give a short definition of both functional and imperative Programming.

I didn’t find a formal definition of the terms so my intention was to clarify things with an informal description like the one from Wikipedia:

“In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state. Functional programming has its roots in the lambda calculus, a formal system developed in the 1930s to investigate function definition, function application, and recursion.”

Wikipedia

I think the main aspect here is: avoiding state and mutable data. Maybe the words “side-effect”, recursion and “higher-order functions” could also be used, but they will be discussed in later questions.

On my slides I covered the following aspects:

• Functional programming is a paradigm
• FP tries to avoid shared state
• Functions are first class citizens, enabling higher-order functions
• Pure functions
• no side-effects
• Results calculated only on the basis of input values
• No information storage
• Deterministic
• ==> Debugging and testing benefits
• ==> Thread-safe without locking of data

For further reading I recommend "Conception, evolution, and application of functional programming languages" (Paul Hudak) or “Functional Programming For The Rest of Us” (Slava Akhmechet).

Question 2 – Explain the keyword “let”. In F# we are talking about “let-bindings” and not “variables”. Why?

Basically you use the let keyword to bind a name to a value or function. It won’t change any more, so a binding is immutable at default and not “variable”.

I was glad to see the presenter showing the problem with an imperative assignment like
x = x + 1, which from a mathematical view is paradoxical. There is no x which equals x plus one. I think choice of the F# assignment operator is better than equality sign. The statement x <- x + 1 shows the real intention. I want to put the old value of x plus one into the memory cell where x was before.
So we discussed some basic terms like scope and mutability here and I showed how we can explicitly tell the compiler to use mutable data using reference cells or mutable variables.

Maybe it wasn’t that good idea to discuss “Imperative F#” at such an early point (without knowing any functional concepts), but it showed the contrast to immutable let-Bindings.

Question 3 – What is a recursion? Try to explain why we often want recursions to be tail-recursive. Hint: Look at the following C# program. What is the problem and how could you solve it?

public static Int64 Factorial(Int64 x)
{
    if (x == 0) return 1;
    return x*Factorial(x - 1);
}
…
Factorial(10000);

It was interesting to see that nearly nobody expected a real problem in such a short code snippet. Some attendees thought this program might have an integer overflow – but only the presenters (they tested the program) gave the right answer (stack overflow). In fact they gave a very good and deep explanation about recursion and the problem on the stack.

As the question hinted, a possible solution was adding a accumulator variable and using tail-recursion:

public static BigInt FactorialTailRecursive(BigInt x, BigInt acc)
{
    if (x == BigInt.Zero) return acc;
    return FactorialTailRecursive(x - BigInt.One, x*acc);
}

Unfortunately this "trick" doesn’t work in C# (the compiler doesn’t use tail calls), but it leads to the correct idea – converting it to a while-loop. Of course I would prefer the tail-recursive F# solution:

/// Tail recursive version
let factorial x = 
  let rec tailRecursiveFactorial x acc =
    match x with
      | y when y = 0I -> acc
      | _ -> tailRecursiveFactorial (x-1I) (acc*x)           

  tailRecursiveFactorial x 1I

We didn’t cover continuation passing here. I think this could be something for an advanced session.

Next time I will discuss the rest of the introduction and show some of the first programming tasks.

Eben bin ich beim Lernen für die Datenbankenprüfung auf einen Wettbewerb mit dem merkwürdigen Namen “wettbehalle” gestoßen. Dabei soll für einen Vortrag meines Professors bei der Langen Nacht der Wissenschaften 2009 in Halle eine Seite möglichst gut für diesen Begriff bei Google gelistet sein.
Ich habe auch schon interessante / riskante Versuche im Netz dazu gesehen, allerdings glaube ich, dass diese konsequent abgestraft werden dürften.

Bei besonders umkämpften Suchbegriffen (die ich hier aus gutem Grund nicht aufzähle), wird jede Form der Manipulation erfahrungsgemäß von den Suchmaschinen-Betreibern schnell entdeckt. Bei einem so seltenen Wort wie wettbehalle, nach dem vermutlich nur zur Langen Nacht der Wissenschaften gesucht wird, bin ich mir jedoch nicht so sicher.
Möglicherweise (bzw. sehr wahrscheinlich) wird da auch etwas automatisiert unternommen. Fakt ist aber, dass der Wettbewerb nicht unter echten Marktbedingungen ausgetragen wird.

Obwohl es um Optimierung geht, werde ich für den Wettbewerb nur diesen einen Artikel hier und einen Tweet “einreichen”. Es wird zwar schwierig damit gegen eine Parteienseite und die Uni Halle zu bestehen, aber vielleicht wird ja zu starke Optimierung auch auf diesem  Level schon abgestraft.

PS: Ok, das ging erstaunlich schnell – schon 9 Minuten nach dem Posten des Artikels hat Google ihn ganz oben gelistest. Wer will kann den Artikel aber trotzdem gerne verlinken.

PS 2: Vielleicht sollte ich noch etwas flamen – das hilft in der Regel immer um Links zu bekommen. Also bald findet ja das BootCamp zu “Funktionaler Programmierung mit F#” in Leipzig statt – in diesem Sinne: “Objektorientierte Programmierung wird völlig überschätzt.”

In the last article I showed how we can use “FAKE – F# Make” to set up a build script which

1. Cleans up old build outputs
2. Compiles our main projects
3. Compiles test projects
4. Uses NUnit to test our assembly
5. Zips the assemblies to a deploy folder.

This time we will improve the same Calculator sample (download here) with a task for FxCop, so please make sure you succeeded with the last article.

“FxCop is a free static code analysis tool from Microsoft that checks .NET managed code assemblies for conformance to Microsoft’s .NET Framework Design Guidelines.”

[Wikipedia]

Setting up FxCop

Open build.fsx from your Calculator sample folder and add a new target “FxCop” to the targets section:

In the dependencies section modify the build order to:

That’s it. If you run your build script you will get new *.xml file in the .\test\-folder:

There are a lot of parameters for the FxCop task. Some are described on the project page.

Letting the build fail

If you were using MSBuild before you might know how hard it is to let MSBuild fail your build if FxCop reports any errors or warnings.

With FAKE the only thing you have to do is setting the “FailOnError” parameter:

If you activate this option FxCop errors will cause your build to fail. Possible values are:

• FxCopErrorLevel.Warning
• FxCopErrorLevel.CriticalWarning
• FxCopErrorLevel.Error
• FxCopErrorLevel.CriticalError
• FxCopErrorLevel.ToolError
• FxCopErrorLevel.DontFailBuild

The values are cummulative. If you choose FxCopErrorLevel.CriticalWarning the build will fail for critical warnings, errors, critical errors and FxCop tool errors but not for simple warnings. The default is FxCopErrorLevel.DontFailBuild.

[Last updated: Jan 9, 2013]

In this tutorial I will describe how you can set up a complete build infrastructure with “FAKE – F# Make”. You will learn how to:

• install the latest FAKE version
• automatically compile your C# or F# projects
• automatically resolve nuget dependencies
• automatically run NUnit UnitTests on your projects
• zip the output to a deployment folder

Install F#

“FAKE – F# Make” is completely written in F# and all build scripts will also be written in F#, but this doesn’t imply that you have to learn programming in F#. In fact the “FAKE – F# Make” syntax is hopefully very easy to learn. But if you need to you can use the complete power of F# and the .NET Framework.

Download Calculator Sample

Now download the latest FAKE-Calculator.zip from the FAKE project site. This sample includes 3 tiny projects and has basically the following structure:

• src\app
  • Calculator (Command line)
  • CalculatorLib (Class library)
• src\test
  • Test.CalculatorLib
• tools
  • NUnit
  • FxCop
• build.bat
• build.fsx
• completeBuild.bat
• completeBuild.fsx
• Calculator.sln

Getting “FAKE – F# Make” started

In the root of the project you will find a build.bat file:

If you run this batch file from the command line then the latest FAKE version will be downloaded via nuget and your first FAKE script (build.fsx) will be executed. If everything works fine you will get the following output:

Now open the build.fsx with Visual Studio. It should look like this:

As you can see the code is really simple. The first line includes the FAKE library and is vital for all FAKE build scripts.

After this header the Default target is defined. A target definition contains of two important parts. The first is the name of the target (here “Default”) and the second is an action (here a simple trace of “Hello world”).

The last line runs the “Default” target – which means it executes the defined action of the target.

Cleaning the last build output

A typical first step in most build scenarios is to clean the output of the last build. We can achieve this by modifying the build.fsx to the following:

We introduced some new concepts in this snippet. At first we defined a global property called “buildDir” with the relative path of a temporary build folder.

In the Clean target we use the CleanDir task to clean up this build directory. This simply deletes all files in the folder or creates the directory if necessary.

In the dependencies section we say that the Default target has a dependency on the Clean target. In other words Clean is a prerequisite of Default and will be run before the execution of Default:

Building the application

In the next step we want to compile our C# libraries, which means we want to compile all csproj-files under /src/app with MSBuild:

We defined a new build target named “BuildApp” which compiles all csproj-files with the MSBuild task and the build output will be copied to buildDir.

In order to find the right project files “FAKE – F# Make” scans the folder src/app/ and all subfolders with the given pattern. Therefore a similar FileSet definition like in NAnt or MSBuild (see project page for details) is used.

In addition the target dependencies are modified again. Now Default is dependent on BuildApp and BuildApp needs Clean as a prerequisite.

This means the execution order is: Clean ==> BuildApp ==> Default.

Building Test projects

Now our main application will be built automatically and it’s time to build the test project. We use the same concepts as before:

This time we defined a new target “BuildTest” which compiles all C# projects below src/test/ in Debug mode and we put the target into our build order.

If we run build.bat again we get an error like this:

The problem is that we didn’t download the NUnit package from nuget. So let’s fix this in the build script:

With this simple command FAKE will use nuget.exe to install all the package dependencies.

Testing the test assemblies with NUnit

Now all our projects will be compiled and we can use Fake’s NUnit task in order to let NUnit test our assembly:

Our new Test target scans the test directory for test assemblies and runs them with the NUnit runner. The mysterious part (fun p –> …) simply overrides the default parameters of the NUnit task and allows to specify concrete parameters..

Deploying a zip file

Now we want to deploy a *.zip file containing our application:

The new Deploy target scans the build directory for all files. The result will be zipped to /deploy/Calculator.zip via the Zip task.

What’s next?

Now you are ready to write your own “FAKE – F# Make” build scripts. If you have any questions or suggestions feel free to comment on this post.

In the next article I will show how we can add FxCop to our build in order to check specific naming rules.

In my last article I showed two ways to use parameterized scenarios in NaturalSpec. This time I will show how we can combine both to test a small Quicksort function.

First of all we define a scenario for sorting:

/// predefined sorting scenario
let sortingScenario f list =
  Given list
    |> When sorting_with f
    |> It should be sorted
    |> It should contain_all_elements_from list
    |> It should contain_no_other_elements_than list

/// predefined Quicksort scenario
let quicksortScenario list = sortingScenario QuickSort list

Now we define some concrete test cases:

[<Scenario>]
let When_sorting_empty_list() =
  quicksortScenario []
    |> Verify
    
[<Scenario>]
let When_sorting_small_list() =
  quicksortScenario [2;1;8;15;5;22]
    |> Verify      
    
[<ScenarioTemplate(100)>]
[<ScenarioTemplate(1000)>]
[<ScenarioTemplate(2500)>]
let When_sorting_ordered_list n =
  quicksortScenario [1..n]
    |> Verify  
    
[<ScenarioTemplate(100)>]
[<ScenarioTemplate(1000)>]
[<ScenarioTemplate(2500)>]
let When_sorting_random_list n =
  quicksortScenario (list_of_random_ints n)
    |> Verify  

After we defined our spec the task is now to implement the sorting function. I am using a very short (and very naïve) Quicksort implementation in F#:

/// naive implementation of QuickSort - don't use it
let rec quicksort = function
  | [] -> []
  | pivot :: rest ->
     let small,big = List.partition ((>) pivot) rest
     quicksort small @ [pivot] @ quicksort big
     
let QuickSort x =
  printMethod ""
  quicksort x   

If we run the scenario, we get the following output (I shortened a bit):

Scenario: When sorting empty list

- Given []
– When sorting with QuickSort
=> It should be sorted
=> It should contain all elements from []
=> It should contain no other elements than []
==> Result is: []
==> OK
==> Time: 0.0355s

Scenario: When sorting small list

- Given [2; 1; 8; 15; 5; 22]
– When sorting with QuickSort
=> It should be sorted
=> It should contain all elements from [2; 1; 8; 15; 5; 22]
=> It should contain no other elements than [2; 1; 8; 15; 5; 22]
==> Result is: [1; 2; 5; 8; 15; 22]
==> OK
==> Time: 0.0065s

Scenario: When sorting ordered list

[…]  100 elements
==> OK
==> Time: 0.0939s

Scenario: When sorting ordered list

[…]  1000 elements
==> OK
==> Time: 0.7130s

Scenario: When sorting ordered list

[…]  2500 elements
==> OK
==> Time: 3.0631s

Scenario: When sorting random list

[…]  100 elements
==> OK
==> Time: 0.0485s

Scenario: When sorting random list

[…]  1000 elements
==> OK
==> Time: 0.1878s

Scenario: When sorting random list

[…]  1000 elements
==> OK
==> Time: 0.8713s

As you can see the function is much faster if we sort a random list. This is because of the naïve choice of the pivot element.

I don’t want to give better implementations here (use LINQ or PLINQ). I just wanted to show how we can easily verify a test function with NaturalSpec.