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

## Tuesday, 2. June 2009

### F# BootCamp – Questions and Answers – part I – Introduction

Filed under: .NET,F#,Informatik,Mathematik,Steffen,TechTalk,Tools — Steffen Forkmann at 10:34 Uhr

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.

Tags: , , ,

## Thursday, 7. May 2009

### Wettbewerb zu “wettbehalle” bei der “Langen Nacht der Wissenschaften” in Halle

Filed under: Informatik,Lustiges,Steffen,Wettbewerbe — Steffen Forkmann at 17:36 Uhr

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.” ­¤śē

Tags: ,

## Thursday, 2. April 2009

### Adding FxCop to a “FAKE” build script

Filed under: C#,English posts,F#,FAKE - F# Make,NaturalSpec,Tools — Steffen Forkmann at 18:19 Uhr

This post has been moved to┬Āhttp://fsharp.github.io/FAKE/fxcop.html

Tags: , , , , , ,

## Wednesday, 1. April 2009

### Getting started with “FAKE – F# Make” – Get rid of the noise in your build scripts.

Filed under: C#,English posts,F#,FAKE - F# Make,Informatik,NaturalSpec,Tools — Steffen Forkmann at 21:02 Uhr

Tags: , , , , , , ,

## Sunday, 1. March 2009

### Testing Quicksort with NaturalSpec

Filed under: F#,NaturalSpec — Steffen Forkmann at 11:42 Uhr

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.

Tags: , ,

## Saturday, 28. February 2009

### Parameterized Scenarios with NaturalSpec

Filed under: F#,NaturalSpec — Steffen Forkmann at 16:46 Uhr

I wrote a lot about NaturalSpec in my last articles. This time I will show how we can use parameterized scenarios.

##### 1. Using predefined scenarios

By writing predefined parameterized scenarios we can easily create a scenario suite with lots of different test cases:

```// predefined scenario
let factorialScenario x result =
Given x
|> When calculating factorial
|> It should equal result

[<Scenario>]
let When_calculation_factorial_of_1() =
factorialScenario 1 1
|> Verify

[<Scenario>]
let When_calculation_factorial_of_10() =
factorialScenario 10 3628800
|> Verify```

If we run these scenarios with NUnit we will get the following output:

Scenario: When calculation factorial of 1

– Given 1

– When calculating factorial

=> It should equal 1

==> OK

==> Time: 0.0093s

Scenario: When calculation factorial of 10

– Given 10

– When calculating factorial

=> It should equal 3628800

==> OK

==> Time: 0.0018s

##### 2. Using the ScenarioTemplate attribute

The second and shorter option is to use the ScenarioTemplate attribute, which is inherited from NUnitŌĆÖs new TestCase attribute:

```// with ScenarioTemplate Attribute
[<ScenarioTemplate(1, 1)>]
[<ScenarioTemplate(2, 2)>]
[<ScenarioTemplate(5, 120)>]
[<ScenarioTemplate(10, 3628800)>]
let When_calculating_fac_(x,result) =
Given x
|> When calculating factorial
|> It should equal result
|> Verify```

This code will create 4 different scenarios, which NUnit will display and report separately: ##### 3. Using ScenarioSource

The third option is to use the ScenarioSource attribute. Here we define a function which generates TestData:

```/// with a scenario source
let MyTestCases =
TestWith 12 3 4
|> And 12 4 3
|> And 12 6 2
|> And 1200 40 30
|> And 0 0 0 |> ShouldFailWith (typeof<System.DivideByZeroException>)```

And then we have to tell NaturalSpec which TestData a scenario should use:

```[<Scenario>]
[<ScenarioSource "MyTestCases">]
let When_dividing a b result =
Given a
|> When dividing_by b
|> It should equal result
|> Verify```
` `
##### Summary

Sometime it makes sense to test a scenario with a bunch of different parameters. We can use the ScenarioTemplate attribute to easily parameterize our scenarios. If we want more flexibility we can use predefined scenarios with custom parameters or the ScenarioSource attribute.

Tags: , , , ,

## Wednesday, 25. February 2009

### Mocking objects with NaturalSpec

Filed under: F#,NaturalSpec — Steffen Forkmann at 16:56 Uhr

In my last articles I gave an introduction in NaturalSpec, showed how to get started and demonstrated how we can use NaturalSpec to write automatically testable scenarios for C# projects. This time I will use the same ŌĆ£Car-DealerŌĆØ-sample to show how we can mock objects in NaturalSpec.

Mocking objects is an important technique in Test-driven development (TDD) and allows us to simulate complex behavior.

ŌĆ£If an object has any of the following characteristics, it may be useful to use a mock object in its place:

• supplies non-deterministic results (e.g. the current time or the current temperature);
• has states that are difficult to create or reproduce (e.g. a network error);
• is slow (e.g. a complete database, which would have to be initialized before the test);
• does not yet exist or may change behavior;
• would have to include information and methods exclusively for testing purposes (and not for its actual task).ŌĆØ

Wikipedia

In our sample we want to mock the Dealer.SellCar() functionality. The first step is to create an C#-Interface for the Dealer:

```namespace CarSellingLib
{
public interface IDealer
{
Car SellCar(int amount);
}
}```

NaturalSpec is using Rhino.Mocks as the underlying mocking framework, so we have to create a reference to Rhino.Mocks.dll in our spec library.

Now we can modify our spec to:

```// 1. open module
module CarSpec```
```// 2. open NaturalSpec-Namespace
open NaturalSpec

// 3. open project namespace
open CarSellingLib

// define reusable values
let DreamCar = new Car(CarType.BMW, 200)
let LameCar = new Car(CarType.Fiat, 45)

// 4. define a mock object and give it a name
let Bert = mock<IDealer> "Bert"

// 5. create a method in BDD-style
let selling_a_car_for amount (dealer:IDealer) =
printMethod amount
dealer.SellCar amount

// 6. create a scenario
[<Scenario>]
let When_selling_a_car_for_30000_it_should_equal_the_DreamCar_mocked() =
As Bert
|> Mock Bert.SellCar 30000 DreamCar  // 7. register mocked call
|> When selling_a_car_for 30000
|> It should equal DreamCar
|> It shouldn't equal LameCar
|> Verify```

As you can see we changed part 4 (in order to get a mocked IDealer instead of the concrete Dealer). In part 7 we register our mocked behavior. We want that whenever Bert.SellCar is called with parameter 30000 the DreamCar should be returned.

The Verify-function checks if the mocked function has been called. If not the scenario will fail.

If we verify our spec with a NUnit runner we get the following output:

Scenario: When selling a car for 30000 it should equal the DreamCar mocked

– As Bert

– With Mocking

– When selling a car for 30000

=> It should equal BMW (200 HP)

=> It should not equal Fiat (45 HP)

==> OK

Tags: , , ,

## Monday, 23. February 2009

### Using NaturalSpec to create a spec for C# projects (Updated 08.11.2009)

Filed under: F#,NaturalSpec — Steffen Forkmann at 18:07 Uhr

In my last two articles I gave an introduction in NaturalSpec and showed how to get started. This time I will show how we can use NaturalSpec to write automatically testable scenarios for C# projects.

Like the TDD principle ŌĆ£Write the tests firstŌĆØ we should write our spec first and use the ŌĆ£Red-Green-RefactorŌĆØ method.

##### "Red" ŌĆō Create a spec scenario that fails

At first I created a F# class library project called ŌĆ£Spec.CarSellingŌĆØ and added project references to NaturalSpec.dll and nunit.framework.dll (see ŌĆ£Getting startedŌĆØ for further explanations).

Now I can write my first scenario:

```// 1. define the module
module CarSpec```
```// 2. open the NaturalSpec namespace
open NaturalSpec

// 3. open project namespace
open CarSellingLib

// 4. define a test context
let Bert = new Dealer("Bert")

// 5. create a method in BDD-style
let selling_a_car_for amount (dealer:Dealer) =
printMethod amount
dealer.SellCar amount

// 6. create a scenario
[<Scenario>]
let When_selling_a_car_for_30000_it_should_equal_my_DreamCar() =
As Bert
|> When selling_a_car_for 30000
|> It should equal (new Car(CarType.BMW, 200))
|> Verify```

At this stage the scenario is ready but doesnŌĆÖt compile. This means we are ready with the "Red"-stage.

##### "Green" ŌĆō Make the test the pass

In order to get the test green we have to create a C# class library called CarSellingLib and define the enum CarType and the classes Dealer and Car. Sticking to the YAGNI-principle we implement only the minimum to get the spec green (and ToString()-members for the output functionality).

```namespace CarSellingLib
{
public enum CarType
{
BMW
}
}```

```namespace CarSellingLib
{
public class Car
{
public Car(CarType type, int horsePower)
{
Type = type;
HorsePower = horsePower;
}

public CarType Type { get; set; }
public int HorsePower { get; set; }

public override string ToString()
{
return string.Format("{0} ({1} HP)", Type, HorsePower);
}

public override bool Equals(object obj)
{
var y = obj as Car;
if(y == null) return false;
return Type == y.Type && HorsePower == y.HorsePower;
}
}
}```
```using System;

namespace CarSellingLib
{
public class Dealer
{
public Dealer(string name)
{
Name = name;
}

public string Name { get; set; }

public Car SellCar(int amount)
{
return new Car(CarType.BMW, 200);
}

public override string ToString()
{
return Name;
}
}
}```

When we add a project reference to our spec-project the UnitTests should pass and we have completed the "Green" step. (See "Getting started" if you donŌĆÖt know how to run the spec.) Now we can add some more scenarios to our spec:

```// 1. define the module
module CarSpec```
```// 2. open NaturalSpec-Namespace
open NaturalSpec

// 3. open project namespace
open CarSellingLib

// 4. define a test context
let Bert = new Dealer("Bert")

// define reusable values
let DreamCar = new Car(CarType.BMW, 200)
let LameCar = new Car(CarType.Fiat, 45)

// 5. create a method in BDD-style
let selling_a_car_for amount (dealer:Dealer) =
printMethod amount
dealer.SellCar amount

// 6. create a scenario
[<Scenario>]
let When_selling_a_car_for_30000_it_should_equal_the_DreamCar() =
As Bert
|> When selling_a_car_for 30000
|> It should equal DreamCar
|> It shouldn't equal LameCar
|> Verify

[<Scenario>]
let When_selling_a_car_for_19000_it_should_equal_the_LameCar() =
As Bert
|> When selling_a_car_for 19000
|> It should equal LameCar
|> It shouldn't equal DreamCar
|> Verify```

```// create a scenario that expects an error
[<Scenario>]
[<Fails_with "Need more money">]
let When_selling_a_car_for_1000_it_should_fail_with_Need_More_Money() =
As Bert
|> When selling_a_car_for 1000
|> Verify```

Now we are in the ŌĆ£RedŌĆØ-Phase again.

##### "Refactor" – rearrange your code to eliminate duplication and follow patterns

After making the spec "Green" and doing some refactoring the project code could look like this:

```namespace CarSellingLib
{
public enum CarType
{
Fiat,
BMW
}
}```

```namespace CarSellingLib
{
public class Car
{
public Car(CarType type, int horsePower)
{
Type = type;
HorsePower = horsePower;
}

public CarType Type { get; set; }
public int HorsePower { get; set; }

# region ToString, Equals

public override string ToString()
{
return string.Format("{0} ({1} HP)", Type, HorsePower);
}

public override bool Equals(object obj)
{
var y = obj as Car;
if(y == null) return false;
return Type == y.Type && HorsePower == y.HorsePower;
}

#endregion
}
}```

```using System;

namespace CarSellingLib
{
public class Dealer
{
public Dealer(string name)
{
Name = name;
}

public string Name { get; set; }

public Car SellCar(int amount)
{
if (amount > 20000)
return new Car(CarType.BMW, 200);

if (amount > 3000)
return new Car(CarType.Fiat, 45);

throw new Exception("Need more money");
}

public override string ToString()
{
return Name;
}
}
}```

The spec output should look like the following:

Scenario: When selling a car for 1000 it should fail with Need More Money

– Should fail…
– As Bert
– When selling a car for 1000

Scenario: When selling a car for 19000 it should equal the LameCar

– As Bert
– When selling a car for 19000
=> It should equal Fiat (45 HP)
=> It should not equal BMW (200 HP)
==> OK

Scenario: When selling a car for 30000 it should equal my DreamCar

– As Bert
– When selling a car for 30000
=> It should equal BMW (200 HP)
==> OK

Scenario: When selling a car for 30000 it should equal the DreamCar

– As Bert
– When selling a car for 30000
=> It should equal BMW (200 HP)
=> It should not equal Fiat (45 HP)
>==> OK

4 passed, 0 failed, 0 skipped, took 1,81 seconds (NUnit 2.5).

##### Summary

I showed how we can use NaturalSpec for the Red-Green-Refactor process of C# projects and how easy it is to get a spec in natural language.

Tags: , , , , ,

### Introducing NaturalSpec – A Domain-specific language (DSL) for testing – Part I

Filed under: C#,F#,NaturalSpec,Tools — Steffen Forkmann at 11:31 Uhr

Test-Driven development (TDD) is a well known software development technique and follows the mantra ŌĆ£Red-Green-RefactorŌĆØ. Behavior-Driven Development (BDD) is a response to TDD and introduces the idea of using natural language to express the Unit Test scenarios.

There are a lot of popular testing frameworks around which can be used for BDD including xUnit.net ,NUnit, StoryQ, MSpec, NSpec and NBehave. Most of them can be used with fluent interfaces and therefore provides a good readability of the sources. Some of them even provide the possibility to generate a spec in natural language out of passed Unit tests.

##### What is a spec?

ŌĆ£A specification is an explicit set of requirements to be satisfied by a material, product, or service.ŌĆØ

American Society for Testing and Materials (ASTM) definition

A spec is an important document for the communication process ŌĆō it enables domain experts to communicate with developers. But how can you verify the compliance with the spec? The answer is: you have to write unit tests. Even with the mentioned frameworks there is a lot of work to do in order to translate a spec scenario into a Unit Test.

Question 7 in the famous Joel Test is ŌĆ£Do you have a spec?ŌĆØ.

The idea of NaturalSpec is to give domain experts the possibility to express their scenarios directly in compilable Unit Test scenarios by using a Domain-specific language (DSL) for Unit Tests. NaturalSpec is completely written in F# ŌĆō but you donŌĆÖt have to learn F# to use it. You donŌĆÖt even have to learn programming at all.

##### Example 1 ŌĆō Specifying a list

LetŌĆÖs consider a small example. If we want to test a new List implementation a spec could look like this:

```[<Scenario>]
let When_removing_an_3_from_a_small_list_it_should_not_contain_3() =
Given [1;2;3;4;5]              // ŌĆ£ArrangeŌĆØ test context
|> When removing 3           // ŌĆ£ActŌĆØ
|> It shouldn't contain 3    // ŌĆ£AssertŌĆØ
|> It should contain 4       // another assertion
|> Verify                    // Verify scenario```

I used BDD style here and expressed my scenario in a quite natural language. As the comments are indicating the scenario is following the Arrange Act Assert (ŌĆ£AAAŌĆØ) pattern.

With the Keyword ŌĆ£GivenŌĆØ I can create a test context (the objects I want to test). In this sample I created a list with 5 elements. With the keyword ŌĆ£WhenŌĆØ I call a function which does something with my test context. In this case I want to remove the value 3. In the Assert section (keywords ŌĆ£It shouldŌĆØ or ŌĆ£It shouldnŌĆÖtŌĆØ) I can give some observations, which should hold for my manipulated test context.

When I run this scenario via a NUnit runner (i am using TestDriven.Net) I get the following output:

Scenario: When removing an 3 from a small list it should not contain 3

– Given [1; 2; 3; 4; 5]
– When removing 3
=> It should not contain 3
=> It should contain 4
==> OK

##### Example 2 ŌĆō Specifying a factorial function

If you implement factorial function the spec could look like this:

```[<Scenario>]
let When_calculating_fac_5_it_should_equal_120() =
Given 5
|> When calculating factorial
|> It should equal 120
|> Verify

[<Scenario>]
let When_calculating_fac_1_it_should_equal_1() =
Given 1
|> When calculating factorial
|> It should equal 1
|> Verify

[<Scenario>]
let When_calculating_fac_0_it_should_equal_0() =
Given 0
|> When calculating factorial
|> It should equal 1
|> Verify```

And the output of NaturalSpec would look like this:

Scenario: When calculating fac 0 it should equal 0

– Given 0
– When calculating factorial
=> It should equal 1
==> OK

Scenario: When calculating fac 1 it should equal 1

– Given 1
– When calculating factorial
=> It should equal 1
==> OK

Scenario: When calculating fac 5 it should equal 120

– Given 5
– When calculating factorial
=> It should equal 120
==> OK

##### Getting started

Of course you can use NaturalSpec to specify C# objects. I see my post "Using NaturalSpec to create a spec for C# projects" for a small sample.

I am very interested in your feedback. Do you like the syntax? What should I change? Do you consider using a spec tool like NaturalSpec?

Tags: , , , , , , , , , , ,

## Monday, 9. February 2009

### Finding the m smallest elements in a collection in F#

Filed under: English posts,F#,Informatik — Steffen Forkmann at 11:56 Uhr

Sometimes we need a function which finds the m smallest elements in a list or array.

We can use the idea of bubble sort to maintain an sorted array of the m smallest elements so far. This idea gives us a O(m*n) algorithm which solves our problem:

```let bubble array element =
let rec bubbleStep i =
if i < (array |> Array.length) then
match array.[i] with
| None ->
if i = array.Length - 1 || array.[i+1] <> None then
array.[i] <- Some element

bubbleStep (i+1)
| Some x ->
if element < x then
if i = 0 then
array.[i] <- Some element
else
array.[i-1] <- Some x
array.[i] <- Some element
bubbleStep (i+1)

bubbleStep 0
array

let mMin seq m =
Seq.fold bubble (Array.create m None) seq```

We can easily generalize this function to compute maximum and minimum:

```let bubble f array element =
let rec bubbleStep i =
if i < (array |> Array.length) then
match array.[i] with
| None ->
if i = array.Length - 1 || array.[i+1] <> None then
array.[i] <- Some element

bubbleStep (i+1)
| Some x ->
if f element x then
if i = 0 then
array.[i] <- Some element
else
array.[i-1] <- Some x
array.[i] <- Some element
bubbleStep (i+1)

bubbleStep 0
array

let mBubble f seq m =
Seq.fold (bubble f) (Array.create m None) seq

let mMin seq m = mBubble (<) seq m
let mMax seq m = mBubble (>) seq m```

If we donŌĆÖt want to store Option-Values we can use this simplification:

```let bubble f m array element =
let rec bubbleStep i =
if i < (array |> Array.length) then
let x = array.[i]
if f element x then
if i = 0 then
array.[i] <- element
else
array.[i-1] <- x
array.[i] <- element
bubbleStep (i+1)

if Array.length array < m then
let newArray = Array.append [|element|] array
newArray
|> Array.sort
(fun a b ->
if a = b then 0
elif f a b then 1 else -1)
newArray
else
bubbleStep 0
array

let mBubble f seq m =
Seq.fold (bubble f m) Array.empty seq

let mMin seq m = mBubble (<) seq m
let mMax seq m = mBubble (>) seq m```
Tags: